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(k2/[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.
Related
- Breakdown of Edgeworth Expansion in Finite-Blocklength Regime and Exact Absorption via q-Deformation
- Loop content of bond percolation on hyperbolic triangulations: an exact identity and a 1/λ expansion
- High-temperature expansion of the inverse-square Ising chain in a magnetic field: exact coefficients and finite-size reconstruction
- Kronecker Products, Polarity Quotients and Large Graph Constructions
- The Polarity Process for the Maximum-Volume Inscribed Ellipsoid Problem
BibTeX
@misc{kaufman2026exact,
title = {{Exact Agreement Expansion up to the Top via Non-polarity}},
author = {Tali Kaufman and Huy Tuan Pham},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03261},
eprint = {2611.03261},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03261},
}
RIS
TY - UNPB
TI - Exact Agreement Expansion up to the Top via Non-polarity
AU - Tali Kaufman
AU - Huy Tuan Pham
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03261
UR - https://arxiv.org/abs/2611.03261
AB - 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.
ER -