The general arrow-relation conjecture for finite-set traces

About 3 years old · traced to

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 F⊂2[n]\mathcal{F}\subset 2^{[n]} and Y⊂[n]Y\subset [n], write F∣Y={F∩Y:F∈F}\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 F⊂2[n]\mathcal{F}\subset 2^{[n]} with ∣F∣≥m|\mathcal{F}|\geq m has an aa-element subset Y⊂[n]Y\subset[n] with ∣F∣Y∣≥b|\mathcal{F}_{\mid Y}|\geq b.

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

(n,1+∏0≤i<ℓ⌊n+ℓ+iℓ⌋)→(ℓ+1,3⋅2ℓ−1+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.

References

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.