arXiv research

New oriented matroids from simplex triangulations.

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 method uses patchworking to represent oriented matroids.

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…

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…

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…

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

Signed seminorms linked to real tropical spaces and matroids.

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.

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…

Algorithm calculates Jones polynomial from Goeritz matrix.

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

The paper categorifies matroid characteristic polynomials using cohomology.

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…

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.

The study connects matroids with torus representations and positive curvature.

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 …

We extend our generic rigidity theory for periodic frameworks in the plane to frameworks with a broader class of crystallographic symmetry. Along the way we introduce a new class of combinatorial matroids and associated linear representation results that may be interesting in their own right. The same techniques immedi…

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

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…

Maximizes determinant of vector sums under matroid constraints.

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

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

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 …

Projection maps which appear in the theory of buildings and oriented matroids are closely related to the notion of shellability. This was first observed by Bj{ö}rner. In this paper, we give an axiomatic treatment of either concept and show their equivalence. We also axiomatize duality in this setting. As applications o…

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…

Motivated by Kohno's result on the holonomy Lie algebra of a hyperplane arrangement, we define the holonomy Lie algebra of a finite geometric lattice in a combinatorial way. For a solvable pair of lattices, we show that the holonomy Lie algebra is an almost-direct product of the holonomy Lie algebra of the sublattice a…

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

For a real oriented hyperplane arrangement, we show that the corresponding Salvetti complex is homotopy equivalent to the complement of the complexified arrangement. This result was originally proved by M. Salvetti. Our proof follows the framework of a proof given by L. Paris and relies heavily on the notation of orien…

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…

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…

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 proof of trapezoidal property for Alexander polynomials of special alternating links.

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…

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 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 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…

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

Motivated by the work of Salvetti and Settepanella we introduce certain total orderings of the faces of any shellable regular CW-complex (called `shelling-type orderings') that can be used to explicitly construct maximum acyclic matchings of the poset of cells of the given complex. Building on an application of this me…