Papers for

matroid theorists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Exact agreement expansion achieved for complex mathematical structures

Exact Agreement Expansion up to the Top via Non-polarity

Abstract: Agreement expansion asks whether local assignments to faces of a poset that usually agree on a sampled common face must agree with a single global function on most faces. Agreement expansion is exact (approximate) if local assignments need to exactly (approximately) agree with the global function. We suggest a new proof technique for agreement expansion that enables agreement expansion in settings which were previously beyond reach, such as: exact agreement expansion for Grassmannian posets (before only simplicial complexes support exact agreement expansion); agreement expansion based on assignments to top faces of the a complex (before agreement expansion is generally proven only for assignments to low dimensional faces); agreement expansion from one-sided spectral expansion (before, two sided spectral assumption was needed in general settings). Specifically, for down-closed simplicial and Grassmannian complexes, we prove an exact agreement theorem between any two layers assuming one-sided spectral expansion in links of singletons. As an application, we show that full bases of every rank-$k$ matroid admit exact agreement with soundness $O(k^2/[h(k-h)])$ when tested through $h$-element independent sets. We also obtain exact agreement on Grassmannian posets under one-sided spectral expansion, with stronger soundness under a local distance guarantee. Our key proof ideas center around non-polarity of the distributions of local assignments, probed via a random exposure of elements.

Mon 2 NovComputational ComplexityDiscrete Mathematics
The gist
This paper focuses on a math problem called agreement expansion, which asks if local pieces that mostly agree can be combined into one global solution. The authors develop a new proof method that works in more complicated settings, including certain geometric and combinatorial shapes where previous approaches failed. They show exact agreement between different layers of these structures using weaker assumptions than before. Their ideas rely on studying distributions of local pieces in a new way through random sampling.
Open → 2611.03261v1