The extremal cover-size conjecture for unstable hypergraph Kneser colorings

About 15 years old · traced to

Let k≥5k\geq 5, and let rr and ℓ\ell be positive integers satisfying

ℓ<r<2ℓ.\ell<r<2\ell.

For a cover CC with elements tit_i, let HC,r(n)H_{C,r}(n) denote the associated hypergraph, and let κ(H,k,ℓ)\kappa(H,k,\ell) be its number of (k,ℓ)(k,\ell)-Kneser colorings. Extremal cover-size conjecture. If

κ(H,k,ℓ)=KC⁡(n,r,k,ℓ),\kappa(H,k,\ell)=\operatorname{KC}(n,r,k,\ell),

then

∣C∣=c(k)=⌈k/3⌉|C|=c(k)=\lceil k/3\rceil

and

∣ti∩tj∣=2ℓ−r−1|t_i\cap t_j|=2\ell-r-1

for every distinct ti,tj∈Ct_i,t_j\in C. The conjecture concerns the unstable range, where the previously defined hypergraph Hn,r,k,ℓH_{n,r,k,\ell} is asymptotically optimal but is not extremal for sufficiently large nn.

References

Primary source

Carlos Hoppen, Yoshiharu Kohayakawa and Hanno Lefmann, “Hypergraphs with many Kneser colorings (Extended Version)”, arXiv:1102.5543 (2011).

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.