Combinatorics of unavoidable complexes

Abstract

The partition number π(K) of a simplicial complex K⊆2[n] is the minimum integer k such that for each partition A1⊎…⊎Ak=[n] of [n] at least one of the sets Ai is in K. A complex K is r-unavoidable if π(K)≤r. Simplicial complexes with small π(K) are important for applications of the “constraint method” (Blagojević et al., 2014) and serve as an input for the “index inequalities” (Jojić et al., 2018), such as (1.1). We introduce a “threshold characteristic” ρ(K) of K (Section 3) and define a fractional (linear programming) relaxation of π(K) (Section 4), which allows us to systematically generate interesting examples of r-unavoidable complexes and pave the way for new results of Van Kampen–Flores–Tverberg type.