Exact Agreement Expansion up to the Top via Non-polarity
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.
Authors
- Huy Tuan Pham (ORCID: https://orcid.org/0000-0003-4659-4345)
- Tali Kaufman (ORCID: https://orcid.org/0009-0009-6776-8763)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-02
- DOI
- https://doi.org/10.48550/arxiv.2611.03261
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint