Half-degree conjecture for complementary tuples in balanced multipartite hypergraphs
Half-degree conjecture for complementary tuples in balanced multipartite hypergraphs
Let ) be an -balanced -partite -graph, and let be a subset of . An -tuple is an element of , and write . For an -tuple and an -tuple , let and denote their degrees in . Half-degree conjecture. If
for every -tuple and
for every -tuple , then has a perfect matching. Thus, each tuple has degree at least roughly half of its possible degree, with a strict inequality on the -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.