On the Keevash-Knox-Mycroft conjecture
Copyright policy )On the Keevash-Knox-Mycroft conjecture
Given $1\le \ell 1-(1-1/k)^{k-\ell}$ and verified the case $\ell=k-1$. In this paper we show that this problem can be reduced to the study of the minimum $\ell$-degree condition forcing the existence of fractional perfect matchings. Together with existing results on fractional perfect matchings, this solves the conjecture of Keevash, Knox and Mycroft for $\ell\ge 0.4k$. Moreover, we also supply an algorithm that outputs a perfect matching, provided that one exists.
v1 is the conference version; v2, v3 are the journal versions; v4 is the final (full) version
FOS: Computer and information sciences, Computer Science - Computational Complexity, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computational Complexity (cs.CC)
FOS: Computer and information sciences, Computer Science - Computational Complexity, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computational Complexity (cs.CC)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!