Asymptotic uncovered-vertex probability for dense almost-regular hypergraphs

Let k3k\geq 3 be a positive integer and let 0<δ,ε<10<\delta,\varepsilon<1 be positive real numbers. There is an n0n_0 such that, for every nn0n\geq n_0, if HH is an nn-vertex kk-graph whose vertex degrees lie between (1nδ)d(1-n^{-\delta})d and (1+nδ)d(1+n^{-\delta})d for some d>nεd>n^{\varepsilon}, and whose maximum codegree is at most nδdn^{-\delta}d, then, for a uniformly random matching MM of HH, writing PH(v)\mathcal{P}_H(\overline{v}) for the probability that MM does not cover vv, the dense almost-regularity conjecture. For every vV(H)v\in V(H),

PH(v)=(1+on(1))d1/k.\mathcal{P}_H(\overline{v})=(1+o_n(1))d^{-1/k}.

This is posed in the concluding remarks as the regime in which the disproved regular-linear conjecture may still hold: the paper's counterexamples rely on fixed dd and very large constructions, while the claim concerns degrees growing faster than a power of nn.

Sources & referencesView supporting material

Primary source

Hyunwoo Lee, “Random matchings in linear hypergraphs”, arXiv:2406.06421 (2024).

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.