Pith. sign in

REVIEW 3 cited by

A Toolkit for Robust Thresholds

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2210.03064 v4 pith:VISYQZYS submitted 2022-10-06 math.CO cs.DMmath.PR

classification math.COcs.DMmath.PR
keywords degreeminimumresultsspanningthresholdscaseconditionfactors
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Sign in to comment.

Forward citations

Cited by 3 Pith papers

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

  1. Robustness of the Sauer-Spencer Theorem

    math.CO 2025-07 accept novelty 8.0 of 10

    A random subgraph of a graph with minimum degree at least (1 - 1/(2Δ))n contains, with high probability, any spanning n-vertex graph of maximum degree Δ, once edges are kept with probability at least C n^{-1/m1(H)} log n.

  2. Perfect Matchings in Random Sparsifications of Dense Hypergraphs

    math.CO 2025-07 conditional novelty 7.0 of 10

    A polynomial-time algorithm almost surely decides whether a random sparsification of a dense k-graph has a perfect matching, and if one exists there are exponentially many.

  3. Transversal packings in families of percolated hypergraphs

    math.CO 2025-07 accept novelty 6.0 of 10

    For any strictly 1-balanced k-graph F, k-graph systems above the transversal Dirac threshold with high probability contain a transversal F-factor after independent random sparsification at p = Ω(n^{-1/d1(F)-1} (log n)^{1/t}).

Pith tools