Sparse minimizer conjecture for induced subgraphs of the Kneser graph

About 3 years old · traced to

Let nn be sufficiently large compared to kk and ss, and let s≤λ≤s+1s\leq\lambda\leq s+1. Let Di\mathcal{D}_i denote the iith star and let F[s+1]{i}\mathcal{F}_{[s+1]}^{\{i\}} denote the members of F\mathcal{F} whose intersection with [s+1][s+1] is exactly {i}\{i\}. A minimizer is a family F⊆([n]k)\mathcal{F}\subseteq\binom{[n]}{k} of size parameter λ\lambda whose maximum degree Δ(F)\Delta(\mathcal{F}) is minimum among all families of the same size.

Sparse minimizer conjecture. There exists a minimizer F\mathcal{F} such that

F⊆D1∪D2∪⋯∪Ds+1,\mathcal{F}\subseteq\mathcal{D}_1\cup\mathcal{D}_2\cup\cdots\cup\mathcal{D}_{s+1}, Di∩Dj⊆Ffor all i,j∈[s+1],\mathcal{D}_i\cap\mathcal{D}_j\subseteq\mathcal{F}\quad\text{for all }i,j\in[s+1],

and

∣F[s+1]{i}△F[s+1]{j}∣≤1for all i,j∈[s+1].\left|\mathcal{F}_{[s+1]}^{\{i\}}\mathbin{\triangle}\mathcal{F}_{[s+1]}^{\{j\}}\right|\leq 1\quad\text{for all }i,j\in[s+1].

This is known when λ=s\lambda=s is an integer, since every minimizer is then a union of ss stars. For nonintegral λ\lambda in the stated range, the existence of a minimizer with these properties remains open.

References

Primary source

Hou Tin Chau, David Ellis, Ehud Friedgut and Noam Lifshitz, “On the maximum degree of induced subgraphs of the Kneser graph”, arXiv:2312.06370 (2024).

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.