Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNatural realizations of sparsity matroids
178
0
0.0
(
0
)
Added by
Louis Theran
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A hypergraph G with n vertices and m hyperedges with d endpoints each is (k,l)-sparse if for all sub-hypergraphs G on n vertices and m edges, mle kn-l. For integers k and l satisfying 0le lle dk-1, this is known to be a linearly representable matroidal family. Motivated by problems in rigidity theory, we give a new linear representation theorem for the (k,l)-sparse hypergraphs that is natural; i.e., the representing matrix captures the vertex-edge incidence structure of the underlying hypergraph G.
rate research
Read More
We describe a new algorithm, the $(k,ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,ell)$-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special inst
ances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the $(k,ell)$-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.
We describe a new algorithm, the $(k,\\ell)$-pebble game with colors, and use\nit obtain a characterization of the family of $(k,\\ell)$-sparse graphs and\nalgorithmic solutions to a family of problems concerning tree decompositions of\ngraphs. Spe
cial instances of sparse graphs appear in rigidity theory and have\nreceived increased attention in recent years. In particular, our colored\npebbles generalize and strengthen the previous results of Lee and Streinu and\ngive a new proof of the Tutte-Nash-Williams characterization of arboricity. We\nalso present a new decomposition that certifies sparsity based on the\n$(k,\\ell)$-pebble game with colors. Our work also exposes connections between\npebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and\nWestermann and Hendrickson.\n
Motivated by a rigidity-theoretic perspective on the Localization Problem in 2D, we develop an algorithm for computing circuit polynomials in the algebraic rigidity matroid associated to the Cayley-Menger ideal for $n$ points in 2D. We introduce combinatorial resultants, a new operation on graphs that captures properties of the Sylvester resultant of two polynomials in the algebraic rigidity matroid. We show that every rigidity circuit has a construction tree from $K_4$ graphs based on this operation. Our algorithm performs an algebraic elimination guided by the construction tree, and uses classical resultants, factorization and ideal membership. To demonstrate its effectiveness, we implemented our algorithm in Mathematica: it took less than 15 seconds on an example where a Groebner Basis calculation took 5 days and 6 hrs.
We introduce delta-graphic matroids, which are matroids whose bases form graphic delta-matroids. The class of delta-graphic matroids contains graphic matroids as well as cographic matroids and is a proper subclass of the class of regular matroids. We give a structural characterization of the class of delta-graphic matroids. We also show that every forbidden minor for the class of delta-graphic matroids has at most $48$ elements.
We construct minimal cellular resolutions of squarefree monomial ideals arising from hyperplane arrangements, matroids and oriented matroids. These are Stanley-Reisner ideals of complexes of independent sets, and of triangulations of Lawrence matroid polytopes. Our resolution provides a cellular realization of Stanleys formula for their Betti numbers. For unimodular matroids our resolutions are related to hyperplane arrangements on tori, and we recover the resolutions constructed by Bayer, Popescu and Sturmfels. We resolve the combinatorial problems posed in their paper by computing Mobius invariants of graphic and cographic arrangements in terms of Hermite polynomials.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
