Ahlswede–Khachatrian conjecture on hypergraphs without perfect fractional matchings

At least 12 years old · documented by

Let H(n,k)=([n],E)H(n,k)=([n],E) be a kk-uniform hypergraph, where [n]={1,…,n}[n]=\{1,\ldots,n\}, and let a perfect fractional matching be a collection of nonnegative real numbers (αe)e∈E(\alpha_e)_{e\in E} satisfying

∑e∈Eαe=1,∑e∈Eαee=(kn,…,kn).\sum_{e\in E}\alpha_e=1,\qquad \sum_{e\in E}\alpha_e e=\left(\frac{k}{n},\ldots,\frac{k}{n}\right).

Let Hf\mathcal{H}_f be the set of hypergraphs without perfect fractional matchings, and define p(n,k)=max⁡H∈Hf∣E∣p(n,k)=\max_{H\in\mathcal{H}_f}|E|. Ahlswede–Khachatrian conjecture.

p(n,k)=max⁡k≥s≥1∑i=0k−s(nsi+s)(n−nsk−s−i),p(n,k)=\max_{k\ge s\ge 1}\sum_{i=0}^{k-s}\binom{n_s}{i+s}\binom{n-n_s}{k-s-i},

where ns=⌈ns/k⌉−1n_s=\lceil ns/k\rceil-1. The conjecture gives an extremal formula for the largest number of edges in a kk-uniform hypergraph lacking a perfect fractional matching. The source states that it is proved up to finitely many cases that can be checked computationally; the remaining cases are therefore open in the supplied text.

References

Primary source

Vladimir Blinovsky, “Minimal Number of Edges in Hypergraph Guaranteeing Perfect Fractional Matching and MMS Conjecture”, arXiv:1310.0989 (2014).

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.