Exchange properties of finite set-systems

Abstract

In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the $n$-dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system $\mathcal{F}$ covering an $n$-element ground set which satisfies the following condition: For any two disjoint members $A,B\in \mathcal{F}$, there exist $a\in A$ and $b\in B$ such that either $B\cup \{a\}\in \mathcal{F}$ and $A\cup \{b\}\setminus \{a\}\in \mathcal{F}$, or $A\cup \{b\}\in \mathcal{F}$ and $B\cup \{a\}\setminus \{b\}\in \mathcal{F}$. Denoting by $f(n)$ the smallest cardinality of such a family $\mathcal{F}$, they proved that $f(n)<2^{O(\sqrt{n}\log n)}$, and they asked for a nontrivial lower bound. It turns out that the construction of Adiprasito et al. is not far from optimal; we show that $2^{(1.42+o(1))\sqrt{n}}\le f(n)\le 2^{(1+o(1))\sqrt{2n\log n}}$. We also study a variant of the above problem, where the condition is strengthened by also requiring that for any two disjoint members $A,B\in \mathcal{F}$ with $|A|>|B|$, there exists $a\in A$ such that $B\cup \{a\}\in \mathcal{F}$. In this case, we prove that the size of the smallest $\mathcal{F}$ satisfying this stronger condition lies between $2^{\Omega (\sqrt{n}\log n)}$ and $2^{O(n\log \log n/\log n)}$.