pith. sign in

arxiv: 2210.03064 · v4 · pith:VISYQZYSnew · submitted 2022-10-06 · 🧮 math.CO · cs.DM· math.PR

A Toolkit for Robust Thresholds

classification 🧮 math.CO cs.DMmath.PR
keywords degreeminimumresultsspanningthresholdscaseconditionfactors
0
0 comments X
read the original abstract

Consider a host hypergraph $G$ which contains a spanning structure due to minimum degree considerations. We collect three results proving that if the edges of $G$ are sampled at the appropriate rate then the spanning structure still appears with high probability in the sampled hypergraph. We prove such results for perfect matchings in hypergraphs above Dirac thresholds, for $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition, and for bounded-degree spanning trees. In each case our proof is based on constructing a spread measure and then applying recent results on the (fractional) Kahn--Kalai conjecture connecting the existence of such measures with probabilistic thresholds. For our second result we give a shorter and more general proof of a recent theorem of Allen, B\"ottcher, Corsten, Davies, Jenssen, Morris, Roberts, and Skokan which handles the $r=3$ case with different techniques. In particular, we answer a question of theirs with regards to the number of $K_r$-factors in graphs satisfying the Hajnal--Szemer\'edi minimum degree condition.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Dirac's theorem and the switch geometry of perfect matchings

    math.CO 2026-04 unverdicted novelty 7.0

    Strengthened Dirac-type minimum degree conditions guarantee that the k-switch reconfiguration graphs on perfect matchings are connected and expanders, with matching lower-bound constructions showing exponential number...

  2. Robust Hamiltonicity in families of Dirac graphs

    math.CO 2023-09 unverdicted novelty 7.0

    The paper finds the threshold probability for random subgraphs of Dirac graphs to admit Hamilton cycle transversals and derives optimal counting and packing corollaries that generalize single-graph Hamilton cycle results.