Ahlswede–Khachatrian conjecture on hypergraphs without perfect fractional matchings

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)eE(\alpha_e)_{e\in E} satisfying

eEαe=1,eEα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)=maxHHfEp(n,k)=\max_{H\in\mathcal{H}_f}|E|. Ahlswede–Khachatrian conjecture.

p(n,k)=maxks1i=0ks(nsi+s)(nnsksi),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/k1n_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.

Sources & referencesView supporting material

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.