Sparse minimizer conjecture for induced subgraphs of the Kneser graph

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

FD1D2Ds+1,\mathcal{F}\subseteq\mathcal{D}_1\cup\mathcal{D}_2\cup\cdots\cup\mathcal{D}_{s+1}, DiDjFfor 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.

Sources & referencesView supporting material

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.