The general arrow-relation conjecture for finite-set traces

Let [n]={1,2,,n}[n]=\{1,2,\ldots,n\} be the standard nn-element set and 2[n]2^{[n]} its powerset. For a family F2[n]\mathcal{F}\subset 2^{[n]} and Y[n]Y\subset [n], write FY={FY:FF}\mathcal{F}_{\mid Y}=\{F\cap Y:F\in\mathcal{F}\} for its trace on YY. The arrow relation (n,m)(a,b)(n,m)\rightarrow(a,b) means that every family F2[n]\mathcal{F}\subset 2^{[n]} with Fm|\mathcal{F}|\geq m has an aa-element subset Y[n]Y\subset[n] with FYb|\mathcal{F}_{\mid Y}|\geq b.

The general arrow-relation conjecture. For all integers n>>0n>\ell>0,

(n,1+0i<n++i)(+1,321+1).\left(n,1+\prod_{0\leq i<\ell} \left\lfloor\frac{n+\ell+i}{\ell}\right\rfloor\right)\rightarrow (\ell+1,3\cdot 2^{\ell-1}+1).

The examples preceding the conjecture show that the corresponding lower threshold with the initial 11 omitted does not force the stated trace size. The conjecture is best possible for =1\ell=1 and =2\ell=2, by the Sauer–Shelah–Vapnik–Chervonenkis theorem and the result attributed to Lovász and proved by the first author; its status for general \ell is left open.

Sources & referencesView supporting material

Primary source

Peter Frankl and Jian Wang, “Four-vertex traces of finite sets”, arXiv:2301.05830 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.