pith. sign in

arxiv: 2604.17911 · v1 · submitted 2026-04-20 · 🧮 math.CO · cs.DM

Dirac's theorem and the switch geometry of perfect matchings

Ross J. Kang , Cl\'ement Legrand-Duchesne This is my paper

Pith reviewed 2026-05-10 04:35 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords perfect matchingsreconfiguration graphsDirac's theoremminimum degreeexpandersalternating cyclesswitchingCaccetta-Häggkvist conjecture
0
0 comments X

The pith

If a graph on n vertices has minimum degree at least floor(2n/3)+1 then its perfect matchings form a connected expander under switches of at most two edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper strengthens Dirac's theorem on the existence of perfect matchings by studying how those matchings can be transformed into one another through limited local changes. It proves that a minimum-degree threshold of roughly two-thirds the number of vertices guarantees both connectivity and good expansion in the graph whose vertices are perfect matchings and whose edges represent switches of at most k edges. For k=2 the threshold is floor(2n/3)+1; for k=3 it drops to n/2+2. Below these values, or even close to n/2, the same reconfiguration graphs can be disconnected or contain exponentially many components. The results give a precise geometric picture of the space of perfect matchings when the host graph is sufficiently dense.

Core claim

If δ(G) ≥ ⌊2n/3⌋+1 then the reconfiguration graph H_2(G) on perfect matchings of G is connected and an expander. If δ(G) ≥ n/2+2 then H_3(G) is connected and an expander. For every ε>0 there exists c>1 such that n-vertex graphs with δ(G) ≥ n/2−εkn exist for which H_k(G) has at least c^n components. If δ(G) ≥ n/2+1 then H_2(G) has positive minimum degree. For k≥3 the threshold for positive minimum degree in H_k(G) is tied to the Caccetta–Häggkvist conjecture.

What carries the argument

The reconfiguration graph H_k(G) whose vertices are the perfect matchings of G and whose edges join two matchings whenever one is obtained from the other by switching at most k edges.

If this is right

  • The set of all perfect matchings becomes a single connected component under 2-switches once the host graph meets the 2n/3 threshold.
  • The same degree condition forces the reconfiguration graph to expand, so random walks on matchings mix rapidly.
  • For 3-switches the connectivity threshold lies only two above the classical Dirac bound.
  • Even graphs whose minimum degree is only a small linear amount below n/2 can still have exponentially many isolated components in H_k(G).
  • Positive minimum degree in H_2(G) is already guaranteed by a minimum degree of n/2+1 in G.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The expander property implies that local search algorithms can efficiently move between any two perfect matchings in dense graphs.
  • The link to the Caccetta–Häggkvist conjecture suggests that directed-cycle problems may control the existence of isolated vertices in higher-k reconfiguration graphs.
  • Analogous connectivity thresholds may exist for other reconfiguration problems, such as spanning trees under single-edge swaps.
  • The exponential-component construction shows that the transition from connected to highly disconnected reconfiguration spaces occurs in a narrow window near n/2.

Load-bearing premise

The minimum degree is high enough that any two perfect matchings share enough alternating cycles or paths for a sequence of small switches to connect them.

What would settle it

An explicit n-vertex graph with minimum degree floor(2n/3)+1 whose perfect matchings cannot be joined by any sequence of 2-edge switches would disprove the connectivity claim for H_2(G).

Figures

Figures reproduced from arXiv: 2604.17911 by Cl\'ement Legrand-Duchesne, Ross J. Kang.

Figure 1
Figure 1. Figure 1: An artist’s depiction of a possible phase diagram for the guaranteed structure of [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The reconfiguration sequence of Theorem 3.3. M is represented in blue and M′ in red. γn-matchings Let M and M′ be two γn-matchings of G. We proceed by induction on |M∆M′ | by proving that we can always reduce the size of the symmetric difference by per￾forming a 4-switch in M or in M′ . We handle separately the following cases (in that order): isolated edges of M∆M′ , even alternating paths of length at mo… view at source ↗
Figure 3
Figure 3. Figure 3: The reconfiguration sequence of Lemma 3.4. M is represented in blue and M′ in red. Bipartite case For each i ∈ [8], let Ei be the set of edges xy of M ∩M′ such that either x or y is adjacent to ui . We have |Ei | = |N(ui)∩(V (G) \V (C))| = |N(ui) \ {ui−1 (mod 8), ui+1 (mod 8)}| because C contains no even chords and G is bipartite. So |Ei | ≥ deg(ui) − 2. As C has 3 If G is a balanced bipartite graph on 2n … view at source ↗
Figure 4
Figure 4. Figure 4: The reconfiguration sequence of Claim 3.7. M is represented in blue and M′ in red. Bipartite case For i ∈ {1, 2, 3}, consider Ei the set of edges of M∩M′ with opposite endpoints adjacent to ui and ui+3 respectively. Let V ′ i = Vi \ V (C) where Vi is the half of the bipartition that contains ui . Let Ai be the set of vertices of V ′ i that are not matched in M ∩ M′ to a neighbour of ui . We have |Ai | = n … view at source ↗
Figure 5
Figure 5. Figure 5: The graph Gk,p,γ,n, here with p = 3 and k = 3. Lemma 4.1. Let γ ∈ (0, 1] and k, p, n be integers with k ≥ 2, p ≥ 1 and γn/2 ≥ p(k + 1) an integer. The graph Gk,p,γ,n has minimum degree γn/2 − p(k + 1) and the k-switch graph Hk(Gk,p,γ,n, γ) of γn-matchings has exactly 2 p connected components, which have equal size. Moreover, the restrictions of the γn-matchings to X are constant within each of these connec… view at source ↗
Figure 6
Figure 6. Figure 6: The graph G (B) k,p,γ,n, here with p = 2 and k = 3. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The graph F2,n. The edges in the set E1 (defined in the proof of Lemma 4.7) are drawn in red. Lemma 4.7. Let k ≥ 2 and n ≥ 4(k + 1) be an even integer. The switch graph Hk(Fk,n) is disconnected. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The graph F (R) 2,n , i.e. a blow-up of the vertices of a 6-cycle into independent set of size n/3. The edges in the sets E1 and E3 (defined in the proof of Lemma 4.8) are drawn in red and blue respectively. Now if n is not a multiple of (k+1), we construct F (B) k,n similarly, by distributing the additional vertices one-by-one in pairs of consecutive blown-up vertices. The graph we obtain is not regular a… view at source ↗
Figure 9
Figure 9. Figure 9: Constructing Nj when Nj−1 is representative and v1 is a neighbour of v2(k+l) for some l ∈ [3] (here l = 2). The resulting Nj is also representative. |A| + |B| ≥ n − 5 because v1 and v2k+4 are not adjacent. So by the pigeonhole principle, there exists x ′y ′ ∈ Nj−1, with x ′ , y′ ∈ { / v1, v2k, . . . v2k+4}, such that x ′ is a neighbour of v1 and y ′ of v2k+4. By performing the 4-switch C = v1v2k . . . v2k+… view at source ↗
Figure 10
Figure 10. Figure 10: Constructing Nj when Nj−1 is representative and v1 has no neighbours among v2(k+1), v2(k+2) and v2(k+3). The resulting Nj is misleading. Setup for the remaining cases Now, assume that Nj−1 is misleading. Let xy be the deceptive edge of Nj−1 and k the progress index of Nj−1. We distinguish cases depending on the value of (x, y): the most generic case is when {x, y} ∩ {v2k+1, . . . v2k+4} = ∅, otherwise {x,… view at source ↗
Figure 11
Figure 11. Figure 11: Constructing Nj when Nj−1 is misleading and v1 is adjacent to v2(k+l) for some l ∈ [2] (here l = 2). The resulting Nj is representative. Cases 4b, 5b, and 6b Finally, assume that no such m exists. Let V ′ = V (G)\V (P) and A be the set of vertices of V ′ matched in Nj−1 to a neighbour of v1 5 . Since v1 is not adjacent to v2k and v2(k+l) , it has at least deg(v1)−3 neighbours among V ′ , so |A| ≥ deg(v1)−… view at source ↗
Figure 12
Figure 12. Figure 12: Constructing Nj when Nj−1 is misleading and v1 has no neighbours among v2(k+1) and v2(k+2). The resulting Nj is misleading. Note that the progress index increases at each step of our reconfiguration sequence, so the sequence between Mi and Mi+1 has length at most |Ci | = |Mi∆Mi+1|. So the canonical path between S and T has length at most n. Analysis of the congestion Given some transition M → M′ , let cp(… view at source ↗
read the original abstract

Let $G$ be a graph on an even number $n$ of vertices and let ${\cal M}_G$ be the collection of perfect matchings in $G$. Dirac's theorem says that if the minimum degree $\delta(G)$ of $G$ is at least $n/2$, then ${\cal M}_G$ is guaranteed to be non-empty, while this is not necessarily the case if $\delta(G) \le n/2-1$. Given an integer $k\ge 2$, let $\mathcal H_k(G)$ be the reconfiguration graph formed on ${\cal M}_G$ by connecting two distinct $M_1,M_2\in {\cal M}_G$ by an edge in $\mathcal H_k(G)$ if $M_1$ can be obtained from $M_2$ by switching at most $k$ edges. Besides non-emptiness, as per Dirac's theorem, what other natural properties of $\mathcal H_k(G)$ are guaranteed based on the minimum degree $\delta(G)$ of $G$? We show that if $\delta(G) \ge \lfloor2n/3\rfloor+1$, then $\mathcal H_2(G)$ must be connected and an expander, while for each $\delta\le \lfloor(2n-2)/3\rfloor$ there are $n$-vertex graphs $G$ with minimum degree $\delta$ such that $\mathcal H_2(G)$ is disconnected. We also show that, if $\delta(G) \ge n/2+2$, then $\mathcal H_3(G)$ must be connected and an expander, while for each $\delta\le n/2-C_k$ there are $n$-vertex graphs $G$ with minimum degree $\delta$ such that $\mathcal H_k(G)$ is disconnected, for some $C_k$ depending on $k\ge 3$. Furthermore, for every $\varepsilon >0$, there exists a $c>1$ such that for every $k\ge 2$ and every large enough $n$, there are $n$-vertex graphs $G$ with $\delta(G) \ge \frac{n}2-\varepsilon kn$ such that $\mathcal H_k(G)$ has at least $c^n$ components. With respect to guaranteeing that $\mathcal H_k(G)$ has positive minimum degree (or, equivalently, no isolated vertices) we show that if $\delta(G) \ge n/2+1$, then $\mathcal H_2(G)$ must have positive minimum degree. For $k\ge 3$, we show how this threshold for $\delta(G)$ is related to the notorious Caccetta-H\"aggkvist conjecture.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper extends Dirac's theorem on the existence of perfect matchings to the reconfiguration graph H_k(G) on the set of all perfect matchings of an n-vertex graph G (n even), where two matchings are adjacent if one is obtained from the other by switching at most k edges. It proves that δ(G) ≥ ⌊2n/3⌋ + 1 forces H_2(G) to be connected and an expander, with a matching construction showing that H_2(G) can be disconnected for δ(G) ≤ ⌊(2n-2)/3⌋. Analogous connectivity and expansion results hold for H_3(G) when δ(G) ≥ n/2 + 2, while for each k ≥ 3 there exist graphs with δ(G) ≤ n/2 - C_k having disconnected H_k(G). For every ε > 0 there is c > 1 such that graphs with δ(G) ≥ n/2 - ε k n can have at least c^n components in H_k(G). The paper also determines the threshold δ(G) ≥ n/2 + 1 guaranteeing that H_2(G) has positive minimum degree and relates the corresponding threshold for k ≥ 3 to the Caccetta-Häggkvist conjecture.

Significance. If the stated thresholds and constructions hold, the results give a precise combinatorial picture of the 'switch geometry' of perfect matchings, showing that Dirac-type degree conditions already guarantee not only existence but also global connectivity, expansion, and (in some regimes) exponential component counts in the reconfiguration graph. The expander property and the exponential lower bound are particularly strong, as they imply rapid mixing for random walks on the space of perfect matchings under these degree hypotheses. The explicit link to the Caccetta-Häggkvist conjecture for the positive-degree case of H_k(G) (k ≥ 3) is a notable strength.

major comments (2)
  1. [Theorem 1 (or equivalent statement of the H_2 expander result)] The expander claim for H_2(G) under δ(G) ≥ ⌊2n/3⌋ + 1 is load-bearing for the main theorem; the proof must establish a uniform spectral gap independent of n. The abstract states the result but does not indicate whether the expansion constant is explicit or merely existential; if the latter, the claim should be clarified in the statement of the theorem.
  2. [Section on positive minimum degree for k ≥ 3] The relation to the Caccetta-Häggkvist conjecture for the positive-minimum-degree threshold of H_k(G) when k ≥ 3 is presented as a reduction rather than a resolution. The manuscript should make explicit whether the reduction is if-and-only-if or one-directional, and whether any new information about the conjecture is obtained.
minor comments (2)
  1. [Introduction] Notation: the symbol H_k(G) is introduced without an explicit reminder that its vertex set is exactly M_G; a parenthetical clarification in the first paragraph of the introduction would help readers.
  2. [Abstract and Introduction] The lower-bound constructions for disconnection are stated to exist for each δ ≤ ⌊(2n-2)/3⌋ (k=2) and δ ≤ n/2 - C_k (k ≥ 3). It would be useful to include a brief description or reference to the extremal graphs in the abstract or introduction so that the tightness is immediately visible.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and positive recommendation for minor revision. We address the major comments below and will incorporate the suggested clarifications into the revised manuscript.

read point-by-point responses

  1. Referee: [Theorem 1 (or equivalent statement of the H_2 expander result)] The expander claim for H_2(G) under δ(G) ≥ ⌊2n/3⌋ + 1 is load-bearing for the main theorem; the proof must establish a uniform spectral gap independent of n. The abstract states the result but does not indicate whether the expansion constant is explicit or merely existential; if the latter, the claim should be clarified in the statement of the theorem.

    Authors: We appreciate this observation. The proof of the expander property for H_2(G) in Theorem 1 establishes a spectral gap bounded below by a positive constant independent of n. We will revise the statement of Theorem 1 (and the abstract if appropriate) to explicitly indicate that the expansion is with a constant independent of n. revision: yes

  2. Referee: [Section on positive minimum degree for k ≥ 3] The relation to the Caccetta-Häggkvist conjecture for the positive-minimum-degree threshold of H_k(G) when k ≥ 3 is presented as a reduction rather than a resolution. The manuscript should make explicit whether the reduction is if-and-only-if or one-directional, and whether any new information about the conjecture is obtained.

    Authors: Thank you for highlighting this point. The connection we establish is a one-directional reduction showing that the threshold for δ(G) guaranteeing positive minimum degree in H_k(G) (k ≥ 3) is at least as large as the threshold implied by the Caccetta-Häggkvist conjecture. We obtain no new information about the conjecture itself. We will revise the relevant section to make this one-directional nature explicit. revision: yes

Circularity Check

0 steps flagged

No circularity in derivation chain

full rationale

The paper states direct combinatorial theorems that extend Dirac's theorem (an external result) to connectivity and expansion of the reconfiguration graphs H_k(G). The proofs establish that the given minimum-degree thresholds guarantee sufficient alternating cycles or paths for switches to connect matchings, with explicit constructions showing tightness of the bounds. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear; the central claims rest on standard graph-theoretic arguments that do not reduce to the target statements by construction. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard graph-theory background (simple undirected graphs, even order for perfect matchings, Dirac's theorem) with no free parameters, no new invented entities, and no ad-hoc axioms visible from the abstract.

axioms (2)
  • standard math Graphs are finite, simple, undirected; n is even so that perfect matchings exist.
    Invoked throughout the definitions of M_G and H_k(G).
  • standard math Dirac's theorem: δ(G) ≥ n/2 implies M_G is non-empty.
    Used as the baseline that the new results strengthen.

pith-pipeline@v0.9.0 · 5817 in / 1494 out tokens · 42309 ms · 2026-05-10T04:35:00.535981+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

43 extracted references · 43 canonical work pages

  1. [1]

    Achlioptas and A

    D. Achlioptas and A. Coja-Oghlan. Algorithmic barriers from phase transitions. In49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 793–802. IEEE Computer Society, 2008

    work page 2008

  2. [2]

    Achlioptas, A

    D. Achlioptas, A. Coja-Oghlan, and F. Ricci-Tersenghi. On the solution-space geometry of random constraint satisfaction problems.Random Struct. Algorithms, 38(3):251–268, 2011

    work page 2011

  3. [3]

    Allen, J

    P. Allen, J. Böttcher, J. Corsten, E. Davies, M. Jenssen, P. Morris, B. Roberts, and J. Skokan. A robust Corrádi-Hajnal theorem.Random Struct. Algorithms, 65(1):61–130, 2024

    work page 2024

  4. [4]

    Balogh, C

    J. Balogh, C. Lee, and W. Samotij. Corrádi and Hajnal’s theorem for sparse random graphs. Comb. Probab. Comput., 21(1-2):23–55, 2012

    work page 2012

  5. [5]

    Bastide, C

    P. Bastide, C. Legrand-Duchesne, and A. Müyesser. Random embeddings of bounded degree trees with optimal spread. Preprint, arXiv:2409.06640 [math.CO] (2024), 2024

    work page arXiv 2024

  6. [6]

    Behzad, G

    M. Behzad, G. Chartrand, and C. E. Wall. On minimal regular digraphs with given girth. Fund. Math., 69:227–231, 1970

    work page 1970

  7. [7]

    Bonamy, N

    M. Bonamy, N. Bousquet, and G. Perarnau. Frozen(∆ + 1)-colourings of bounded degree graphs.Combin. Probab. Comput., 30(3):330–343, 2021

    work page 2021

  8. [8]

    Bousquet, L

    N. Bousquet, L. Feuilloley, M. Heinrich, and M. Rabie. Short and local transformations between(∆ + 1)-colorings.Innov. Graph Theory, 2:119–156, 2025

    work page 2025

  9. [9]

    L. M. Brègman. Certain properties of nonnegative matrices and their permanents.Dokl. Akad. Nauk SSSR, 211:27–30, 1973

    work page 1973

  10. [10]

    Howhardisittomarryatrandom? (Ontheapproximationofthepermanent)

    A.Z.Broder. Howhardisittomarryatrandom? (Ontheapproximationofthepermanent). InProceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 50–58, 1986

    work page 1986

  11. [11]

    P. Buys, R. J. Kang, and K. Ozeki. Reconfiguration of independent transversals.Random Structures Algorithms, 67(1):Paper No. e70025, 10, 2025

    work page 2025

  12. [12]

    P. Buys, J. van den Heuvel, and R. J. Kang. Condensation in Turán’s theorem. Manuscript in preparation

    work page

  13. [13]

    Onminimaldigraphswithgivengirth

    L.CaccettaandR.Häggkvist. Onminimaldigraphswithgivengirth. InProc. 9th Southeast. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton., pages 181–187, 1978. 29

    work page 1978

  14. [14]

    Cambie, W

    S. Cambie, W. Cames van Batenburg, D. W. Cranston, J. van den Heuvel, and R. J. Kang. Reconfiguration of List Colourings.arXiv e-prints, page arXiv:2505.08020, May 2025

    work page arXiv 2025

  15. [15]

    Csaba, D

    B. Csaba, D. Kühn, A. Lo, D. Osthus, and A. Treglown.Proof of the 1-factorization and Hamilton decomposition conjectures, volume 1154 ofMem. Am. Math. Soc.Providence, RI: American Mathematical Society (AMS), 2016

    work page 2016

  16. [16]

    Csikvári

    P. Csikvári. Lower matching conjecture, and a new proof of Schrijver’s and Gurvits’s theorems.J. Eur. Math. Soc. (JEMS), 19(6):1811–1844, 2017

    work page 2017

  17. [17]

    Cuckler and J

    B. Cuckler and J. Kahn. Entropy bounds for perfect matchings and Hamiltonian cycles. Combinatorica, 29(3):327–335, 2009

    work page 2009

  18. [18]

    Cuckler and J

    B. Cuckler and J. Kahn. Hamiltonian cycles in Dirac graphs.Combinatorica, 29(3):299–326, 2009

    work page 2009

  19. [19]

    Diaconis, R

    P. Diaconis, R. Graham, and S. P. Holmes. Statistical problems involving permutations with restricted positions. InState of the art in probability and statistics. Festschrift for Willem R. van Zwet. Papers from the symposium, Leiden, Netherlands, March 23–26, 1999, pages 195–222. Beachwood, OH: IMS, Institute of Mathematical Statistics, 2001

    work page 1999

  20. [20]

    Diaconis and L

    P. Diaconis and L. Saloff-Coste. Comparison theorems for reversible Markov chains.Ann. Appl. Probab., 3(3):696–730, 1993

    work page 1993

  21. [21]

    G. A. Dirac. Some theorems on abstract graphs.Proc. Lond. Math. Soc. (3), 2:69–81, 1952

    work page 1952

  22. [22]

    M. Dyer, M. Jerrum, and H. Müller. On the switch Markov chain for perfect matchings.J. ACM, 64(2):33, 2017. Id/No 12

    work page 2017

  23. [23]

    Feghali, M

    C. Feghali, M. Johnson, and D. Paulusma. A reconfigurations analogue of Brooks’ theorem and its consequences.J. Graph Theory, 83(4):340–358, 2016

    work page 2016

  24. [24]

    Galliano and R

    J. Galliano and R. J. Kang. Largest component in Boolean sublattices.Acta Math. Hungar., 176(1):183–214, 2025

    work page 2025

  25. [25]

    L. Gurvits. Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all.Electron. J. Combin., 15(1):Research Paper 66, 26, 2008. With a corrigendum

    work page 2008

  26. [26]

    Hladký, D

    J. Hladký, D. Král, and S. Norin. Counting flags in triangle-free digraphs.Combinatorica, 37(1):49–76, 2017

    work page 2017

  27. [27]

    M. Huber. Exact sampling from perfect matchings of dense regular bipartite graphs.Algo- rithmica, 44(3):183–193, 2006

    work page 2006

  28. [28]

    Jerrum and A

    M. Jerrum and A. Sinclair. Approximating the permanent.SIAM J. Comput., 18(6):1149– 1178, 1989

    work page 1989

  29. [29]

    D. Y. Kang, T. Kelly, D. Kühn, D. Osthus, and V. Pfenninger. Perfect matchings in random sparsifications of Dirac hypergraphs.Combinatorica, 44(6):1233–1266, 2024

    work page 2024

  30. [30]

    Kelly, A

    T. Kelly, A. Müyesser, and A. Pokrovskiy. Optimal spread for spanning subgraphs of Dirac hypergraphs.J. Comb. Theory, Ser. B, 169:507–541, 2024

    work page 2024

  31. [31]

    Kleer, V

    P. Kleer, V. Patel, and F. Stroh. Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs.Electron. J. Comb., 27(4):research paper p4.29, 25, 2020. 30

    work page 2020

  32. [32]

    Komlós, G

    J. Komlós, G. N. Sárközy, and E. Szemerédi. Proof of a packing conjecture of Bollobás. Comb. Probab. Comput., 4(3):241–255, 1995

    work page 1995

  33. [33]

    Krivelevich, C

    M. Krivelevich, C. Lee, and B. Sudakov. Robust Hamiltonicity of Dirac graphs.Trans. Am. Math. Soc., 366(6):3095–3130, 2014

    work page 2014

  34. [34]

    Krząkała, A

    F. Krząkała, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborová. Gibbs states and the set of solutions of random constraint satisfaction problems.Proc. Natl. Acad. Sci. USA, 104(25):10318–10323, 2007

    work page 2007

  35. [35]

    Coupling from the past

    D. A. Levin, Y. Peres, and E. L. Wilmer.Markov chains and mixing times. With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson.Providence, RI: American Mathematical Society (AMS), 2nd edition edition, 2017

    work page 2017

  36. [36]

    B. D. McKay, N. C. Wormald, and B. Wysocka. Short cycles in random regular graphs. Electron. J. Combin., 11(1):Research Paper 66, 12, 2004

    work page 2004

  37. [37]

    H.-T. Pham, A. Sah, M. Sawhney, and M. Simkin. A Toolkit for Robust Thresholds. Preprint, arXiv:2210.03064 [math.CO] (2022), 2022

    work page arXiv 2022

  38. [38]

    Randall and P

    D. Randall and P. Tetali. Analyzing Glauber dynamics by comparison of Markov chains. J. Math. Phys., 41(3):1598–1615, 2000

    work page 2000

  39. [39]

    G. N. Sárközy, S. M. Selkow, and E. Szemerédi. On the number of Hamiltonian cycles in Dirac graphs.Discrete Math., 265(1-3):237–250, 2003

    work page 2003

  40. [40]

    Schrijver

    A. Schrijver. Counting1-factors in regular bipartite graphs.J. Combin. Theory Ser. B, 72(1):122–135, 1998

    work page 1998

  41. [41]

    B. Sudakov. Robustness of graph properties. InSurveys in Combinatorics 2017. Papers based on the 26th British Combinatorial Conference, University of Strathclyde, Glasgow, UK, July 2017, pages 372–408. Cambridge: Cambridge University Press, 2017

    work page 2017

  42. [42]

    L. G. Valiant. The complexity of computing the permanent.Theor. Comput. Sci., 8:189– 201, 1979

    work page 1979

  43. [43]

    Voorhoeve

    M. Voorhoeve. A lower bound for the permanents of certain(0,1)-matrices.Nederl. Akad. Wetensch. Indag. Math., 41(1):83–86, 1979. 31

    work page 1979