arXiv research

A matroid is a notion of independence in combinatorial optimization which is closely related to computational efficiency. In particular, it is well known that the maximum of a constrained modular function can be found greedily if and only if the constraints are associated with a matroid. In this paper, we bring togethe…

The study connects matroids with torus representations and positive curvature.

Maximizes determinant of vector sums under matroid constraints.

New oriented matroids from simplex triangulations.

Matroid bundles, introduced by MacPherson, are combinatorial analogues of real vector bundles. This paper sets up the foundations of matroid bundles, and defines a natural transformation from isomorphism classes of real vector bundles to isomorphism classes of matroid bundles, as well as a transformation from matroid b…

The paper categorifies matroid characteristic polynomials using cohomology.

New combinatorial model for Milnor fibration using oriented matroids.

The study explores properties and mutations in oriented matroids, proving new results on Euclidean and non-Euclidean structures.

New theorem links tropical phased matroids to higher-dimensional spheres.

The control and sensing of large-scale systems results in combinatorial problems not only for sensor and actuator placement but also for scheduling or observability/controllability. Such combinatorial constraints in system design and implementation can be captured using a structure known as matroids. In particular, the…

New method uses patchworking to represent oriented matroids.

In a recent paper Baker and Bowler introduced matroids over hyperfields, offering a common generalization of matroids, oriented matroids, and linear subspaces of based vector spaces. This paper introduces the notion of a topological hyperfield and explores the generalization of Grassmannians and realization spaces to t…

The paper tackles robust submodular maximization under matroid constraints, providing approximation algorithms for summary extraction.

We introduce dual matroids of 2-dimensional simplicial complexes. Under certain necessary conditions, duals matroids are used to characterise embeddability in 3-space in a way analogous to Whitney's planarity criterion. We further use dual matroids to extend a 3-dimensional analogue of Kuratowski's theorem to the class…

Unified solution to Goodman-Pollack transversal problem using matroids and topology.

There is a one-to-one correspondence between geometric lattices and the intersection lattices of arrangements of homotopy spheres. When the arrangements are essential and fully partitioned, Zaslavsky's enumeration of the cells of the arrangement still holds. An application of the theory shows that all minimal cellular …

New algorithm for maximizing submodular functions in real-time data changes.

We present a new direct proof of a topological representation theorem for oriented matroids in the general rank case. Our proof is based on an earlier rank 3 version. It uses hyperline sequences and the generalized Sch{ö}nflies theorem. As an application, we show that one can read off oriented matroids from arrangement…

3D analog of Whitney's planarity criterion for 2-complexes.

For a graph embedded into a surface, we relate many combinatorial parameters of the cycle matroid of the graph and the bond matroid of the dual graph with the topological parameters of the embedding. This will give an expression of the polynomial, defined by M.Las Vergnas in a combinatorial way using matroids as a spec…

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors $v_1,\ldots,v_m \in \mathbb{R}^d$ and a constraint family ${\cal B}\subseteq 2^{[m]}$, find a set $S \in \cal{B}$ that maximizes the squared volume of the simplex spanned by the vectors in $S$. A motivatin…

New method finds 198,846 toric-colorable seeds of Picard number 5.

The lattice of integer flows of a graph is known to determine the graph up to 2-isomorphism (work of Su--Wagner and Caporaso--Viviani). In this paper we give an algorithmic construction of the graphic matroid $\calM(G)$ of a graph $G$, given its lattice of integer flows $\calF(G)$. The algorithm can then be applied to …

Signed seminorms linked to real tropical spaces and matroids.

Paper tackles stochastic $k$-submodular bandits with full feedback, achieving sublinear regret.

Approximate inference via information projection has been recently introduced as a general-purpose approach for efficient probabilistic inference given sparse variables. This manuscript goes beyond classical sparsity by proposing efficient algorithms for approximate inference via information projection that are applica…

The paper develops algorithms to find a robust summary of data under deletion, achieving good approximation guarantees.

We improve the efficiency of algorithms for stochastic \emph{combinatorial semi-bandits}. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as \emph{independence}. However, while being optimal in terms of asymptotic regret, these algorithms are inefficien…

We show that there is no triangulation of the infinite real Grassmannian of k-planes in R^\infty which is nicely situated with respect to the coordinate axes. In terms of matroid theory, this says there is no triangulation of the Grassmannian subdividing the matroid stratification. This is proved by an argument in proj…

Extending work of Bielawski-Dancer and Konno, we develop a theory of toric hyperkahler varieties, which involves toric geometry, matroid theory and convex polyhedra. The framework is a detailed study of semi-projective toric varieties, meaning GIT quotients of affine spaces by torus actions, and specifically, of Lawren…

This is both an expository and research paper where we advocate a systematic study of continuous analogues of finite partially ordered sets, convex polytopes, oriented matroids, arrangements of subspaces, finite simplicial complexes, and other combinatorial structures. Among the illustrative examples are an Euler formu…

A deformation of the Orlik-Solomon algebra of a matroid M is defined as a quotient of the free associative algebra over a commutative ring R with 1. It is shown that the given generators form a Groebner basis and that after suitable homogenization the deformation and the Orlik-Solomon have the same Hilbert series as R-…

This paper proves the existence of potentials of the first and second kind of a Frobenius like structure in a frame which encompasses families of arrangements. The frame uses the notion of matroids. For the proof of the existence of the potentials, a power series ansatz is made. The proof that it works requires that ce…

We consider quotients of spheres by linear actions of real tori. To each quotient we associate a matroid built out of a diagonalization of the torus action. We find the integral homology groups of the resulting quotient spaces in terms of the Tutte polynomial of the matroid. We also find the homotopy type and homology …

It is conjectured that the Khovanov homology of a knot is invariant under mutation. In this paper, we review the spanning tree complex for Khovanov homology, and reformulate this conjecture using a matroid obtained from the Tait graph (checkerboard graph) G of a knot diagram K. The spanning trees of G provide a filtrat…

New proof of trapezoidal property for Alexander polynomials of special alternating links.

We present a novel preconditioning technique for proximal optimization methods that relies on graph algorithms to construct effective preconditioners. Such combinatorial preconditioners arise from partitioning the graph into forests. We prove that certain decompositions lead to a theoretically optimal condition number.…

Proves tropical Hodge theory for smooth projective varieties, conditional on Laplacian regularity.

The standard greedy algorithm has been recently shown to enjoy approximation guarantees for constrained non-submodular nondecreasing set function maximization. While these recent results allow to better characterize the empirical success of the greedy algorithm, they are only applicable to simple cardinality constraint…

Algorithm calculates Jones polynomial from Goeritz matrix.

Submodular functions have many applications. Matchings have many applications. The bitext word alignment problem can be modeled as the problem of maximizing a nonnegative, monotone, submodular function constrained to matchings in a complete bipartite graph where each vertex corresponds to a word in the two input senten…

The characteristic varieties of a space are the jump loci for homology of rank 1 local systems. The way in which the geometry of these varieties may vary with the characteristic of the ground field is reflected in the homology of finite cyclic covers. We exploit this phenomenon to detect torsion in the homology of Miln…

We use the theory of oriented matroids to show that any linear embedding of $K_9$, the complete graph on nine vertices, contains a non-split link with three components.

Improved regret bounds for contextual combinatorial semi-bandits with linear payoffs.

We propose an algebraic combinatorial method for solving large sparse linear systems of equations locally - that is, a method which can compute single evaluations of the signal without computing the whole signal. The method scales only in the sparsity of the system and not in its size, and allows to provide error estim…

Differentially private algorithms for submodular maximization under various constraints.

The paper creates a deformation retraction for homeomorphisms of the projective plane.

We introduce and study the notion of the $G$-Tutte polynomial for a list $\mathcal{A}$ of elements in a finitely generated abelian group $Γ$ and an abelian group $G$, which is defined by counting the number of homomorphisms from associated finite abelian groups to $G$. The $G$-Tutte polynomial is a common generalizatio…