Half-degree conjecture for complementary tuples in balanced multipartite hypergraphs

Let HH) be an nn-balanced rr-partite rr-graph, and let II be a subset of [r]:={1,2,,r}[r]:=\{1,2,\ldots,r\}. An II-tuple is an element of ×iIVi\times_{i\in I}V_i, and write Ic:=[r]II^c:=[r]\setminus I. For an II-tuple ff and an IcI^c-tuple gg, let d(f)d(f) and d(g)d(g) denote their degrees in HH. Half-degree conjecture. If

d(f)>nrI2d(f)>\frac{n^{r-|I|}}{2}

for every II-tuple ff and

d(g)nI2d(g)\geq\frac{n^{|I|}}{2}

for every IcI^c-tuple gg, then HH has a perfect matching. Thus, each tuple has degree at least roughly half of its possible degree, with a strict inequality on the II-side. The condition would weaken the sharp minimum-degree hypothesis proved earlier in the paper; its general validity is presented as an open problem.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Agelos Georgakopoulos and Philipp Sprüssel, “Perfect matchings in r-partite r-graphs”, arXiv:0911.4008 (2009).

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.