Transversal Hamilton cycles in digraph collections

Guanghui Wang; Heng Li; Wanting Sun; Yangyang Cheng

arxiv: 2501.00998 · v2 · submitted 2025-01-02 · 🧮 math.CO

Transversal Hamilton cycles in digraph collections

Yangyang Cheng , Heng Li , Wanting Sun , Guanghui Wang This is my paper

Pith reviewed 2026-05-23 06:46 UTC · model grok-4.3

classification 🧮 math.CO

keywords transversal Hamilton cycledigraph collectionGhouila-Houri theoremsemi-degree conditionabsorption methodregularity lemmatransversal Dirac theorem

0 comments

The pith

A collection of digraphs on n vertices each with minimum semi-degree n/2 admits a transversal directed Hamilton cycle.

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

The paper establishes a transversal generalization of Ghouila-Houri's theorem for a collection of m digraphs on a common vertex set. It shows that when each digraph meets the semi-degree threshold of n/2 and m equals n, a directed cycle of length n exists whose edges come from distinct members of the collection via a bijection. This directly solves an open problem on transversal Hamilton cycles in digraphs. The result also yields the transversal version of Dirac's theorem for sufficiently large n as a corollary. A reader would care because the statement extends classical degree conditions from single digraphs to multi-colored or multi-graph settings without adding extra hypotheses.

Core claim

Given a collection D = {D1, ..., Dn} of digraphs on a common n-vertex set where each Di has minimum semi-degree at least n/2, there exists a directed Hamilton cycle that is transversal in D, meaning its n edges can be assigned bijectively to the n digraphs so that each edge belongs to its assigned digraph.

What carries the argument

The transversal directed Hamilton cycle, defined by a bijection from its edges to the collection such that each edge lies in its assigned digraph; the absorption and regularity methods adapted to this multi-digraph setting carry the proof.

Load-bearing premise

The minimum semi-degree conditions on every member of the collection are enough to make the absorption and regularity arguments produce a transversal cycle.

What would settle it

A collection of n digraphs on n vertices, each with minimum semi-degree floor(n/2)-1, that contains no transversal directed Hamilton cycle.

Figures

Figures reproduced from arXiv: 2501.00998 by Guanghui Wang, Heng Li, Wanting Sun, Yangyang Cheng.

**Figure 1.** Figure 1: Extremal digraphs EC1, EC2, and EC3. The gray shaded elliptical indicates that the digraph induced by this vertex set is complete, the gray shaded arrow between two vertex sets indicates that the induced digraph by them is complete in this direction. We call the partition obtained in Lemma 3.3 a characteristic partition of D. Assume that 0 < 1 n ≪ µ ≪ ϵ ≤ 1 and D = {D1, . . . , Dn} is a collection of digra… view at source ↗

**Figure 2.** Figure 2: A Type-I directed Figure 2: A Type-I directed Figure 2: A TypeI directed ) ith 6 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Figure 3: A Type-II directed Figure 3: A Type-II directed c Figure 3: A Type-II directed [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

**Figure 4.** Figure 4: Absorbing. Proof of Claim 4.4. For every color pair (b1, b2) ∈ C2 , every vertex pair (u1, u2) ∈ V 2 and color c ∈ C, let S(b1, b2, u1, u2, c) be the collection of pairs (v1, v2) ∈ V 2 such that c ∈ L(v1u1), b2 ∈ L(u2v2) and (b1, b2, v1, v2) is totally absorbable. We will prove that |S(b1, b2, u1, u2, c)| ≥ 2 −4n 2 . For this, we first count the number of choices for v1. Let N1 := {x ∈ N − c (u1) : x is Db… view at source ↗

**Figure 5.** Figure 5: w1w2 is a c-absorbing edge of (u, v). • for every i ∈ [n], dGi (x) ≥ [PITH_FULL_IMAGE:figures/full_fig_p048_5.png] view at source ↗

read the original abstract

Given a collection $\mathcal{D} =\{D_1,D_2,\ldots,D_m\}$ of digraphs on the common vertex set $V$, an $m$-edge digraph $H$ with vertices in $V$ is \textit{transversal} in $\mathcal{D}$ if there exists a bijection $\varphi :E(H)\rightarrow [m]$ such that $e \in E(D_{\varphi(e)})$ for all $e\in E(H)$. Ghouila-Houri proved that any $n$-vertex digraph with minimum semi-degree at least $\frac{n}{2}$ contains a directed Hamilton cycle. In this paper, we provide a transversal generalization of Ghouila-Houri's theorem, thereby solving a problem proposed by Chakraborti, Kim, Lee and Seo. Our proof utilizes the absorption method for transversals, the regularity method for digraph collections, as well as the transversal blow-up lemma and the related machinery. As an application, when $n$ is sufficiently large, our result implies the transversal version of Dirac's theorem, which was proved by Joos and Kim.

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.

Desk Editor's Note private letter to a colleague

This paper gives a transversal Ghouila-Houri theorem for digraph collections and solves the open problem from Chakraborti et al. using absorption and regularity methods.

read the letter

The paper states a transversal version of Ghouila-Houri: for a collection of digraphs on the same n vertices, if each has minimum semi-degree at least n/2, then there is a directed Hamilton cycle that uses one edge from each digraph in the collection. This directly answers the question posed by Chakraborti, Kim, Lee and Seo. The proof adapts the absorption method to the transversal setting, combines it with regularity for digraph collections, and invokes a transversal blow-up lemma. As a corollary it recovers the transversal Dirac theorem of Joos and Kim for large n. These steps are the actual content; the component tools are known, but their joint application to collections of digraphs is new here. The argument appears internally consistent and the cited methods match the standard toolkit for Hamiltonicity results in oriented graphs. No circularity or invented parameters show up in the description. The main limitation is that the exact degree thresholds and error-term handling are not visible from the abstract alone, so a referee would still need to verify the technical lemmas in full. The work sits squarely inside transversal extremal graph theory for digraphs. Readers already following the Chakraborti et al. problem or the Joos-Kim result will find it directly useful; outsiders will see it as a routine but correct extension. It is worth sending to peer review because it resolves a stated open question with a complete argument built on established techniques.

Referee Report

0 major / 3 minor

Summary. The manuscript proves a transversal generalization of Ghouila-Houri's theorem: for a collection of m digraphs on a common n-vertex set satisfying suitable minimum semi-degree conditions, there exists a transversal directed Hamilton cycle (an m-edge directed cycle using exactly one edge from each digraph via a bijection). The proof adapts the absorption method to the transversal setting, combines it with the regularity lemma for digraph collections and the transversal blow-up lemma, and applies the result to recover the transversal Dirac theorem of Joos and Kim for sufficiently large n. This resolves an open problem posed by Chakraborti, Kim, Lee and Seo.

Significance. If the central claim holds, the result is a meaningful advance in extremal digraph theory by extending a classical Hamiltonicity theorem to the transversal setting for collections. The explicit use of established tools (absorption, regularity, blow-up) and the consistency check with the Joos-Kim theorem are strengths; the derivation is described as parameter-free in the sense of the cited methods rather than fitted quantities.

minor comments (3)

[Abstract and §1] The precise minimum semi-degree threshold (presumably of the form (1/2 - o(1))n or similar) should be stated explicitly in the abstract and in the statement of the main theorem (likely Theorem 1.1 or 1.2) rather than left implicit.
[§1] Notation for the collection D = {D1,...,Dm} and the transversal mapping φ is introduced clearly, but the distinction between the semi-degree conditions on individual Di versus the joint collection could be clarified with an additional sentence in the introduction.
[§1] The application paragraph stating that the result implies the Joos-Kim theorem for large n would benefit from a one-sentence pointer to the exact corollary number.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our manuscript, the assessment of its significance, and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper states a transversal generalization of Ghouila-Houri's theorem proved via absorption, regularity, and blow-up methods for digraph collections. These are standard external techniques with no equations or definitions shown that reduce the claimed result to a self-referential fit, renamed input, or load-bearing self-citation chain. The application to the Joos-Kim transversal Dirac theorem is presented as a consequence rather than a premise, and the solved open problem is attributed to independent prior work. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on standard combinatorial axioms and the applicability of known proof techniques (absorption, regularity lemma for digraphs, blow-up lemma) to the transversal setting; no free parameters or new entities are introduced in the abstract.

axioms (2)

standard math Standard axioms and definitions of directed graphs, semi-degrees, and Hamilton cycles
Invoked throughout to state Ghouila-Houri and its transversal version.
domain assumption The absorption method, regularity method, and transversal blow-up lemma apply to digraph collections under the stated degree conditions
These are the core tools listed in the abstract for the proof.

pith-pipeline@v0.9.0 · 5726 in / 1310 out tokens · 38590 ms · 2026-05-23T06:46:45.429646+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages · 1 internal anchor

[1]

Aharoni, M

R. Aharoni, M. DeVos, S. González Hermosillo de la Maza, A. Montejano, and R. Šámal. A rainbow version of Mantel’s theorem.Adv. Comb., pages Paper No. 2, 12, 2020

work page 2020
[2]

Aharoni and D

R. Aharoni and D. Howard. A rainbow r-partite version of the Erdős-Ko-Rado theorem. Combin. Probab. Comput., 26(3):321–337, 2017

work page 2017
[3]

Babiński, A

S. Babiński, A. Grzesik, and M. Prorok. Directed graphs without rainbow triangles. arXiv:2308.01461, 2023

work page arXiv 2023
[4]

I. Bárány. A generalization of Carathéodory’s theorem.Discrete Math., 40(2-3):141–152, 1982. 39

work page 1982
[5]

Bradshaw

P. Bradshaw. Transversals and bipancyclicity in bipartite graph families.Electron. J. Combin., pages P4–25, 2021

work page 2021
[6]

Chakraborti, J

D. Chakraborti, J. Kim, H. Lee, and J. Seo. Hamilton Transversals in Tournaments.Combi- natorica, 44(6):1381–1400, 2024

work page 2024
[7]

Chakraborti, J

D. Chakraborti, J. Kim, H. Lee, and J. Seo. Transversal cycles and paths in tournaments. arXiv:2407.14300, 2024

work page arXiv 2024
[8]

Cheng, J

Y. Cheng, J. Han, B. Wang, and G. Wang. Rainbow spanning structures in graph and hyper- graph systems. Forum Math. Sigma, 11:Paper No. e95, 20, 2023

work page 2023
[9]

Cheng and K

Y. Cheng and K. Staden. Transversals via regularity.arXiv:2306.03595, 2023

work page arXiv 2023
[10]

Cheng and K

Y. Cheng and K. Staden. Stability of transversal Hamilton cycles and paths.arXiv:2403.09913, 2024

work page arXiv 2024
[11]

Cheng, W

Y. Cheng, W. Sun, G. Wang, and L. Wei. Transversal hamilton paths and cycles. arXiv:2406.13998, 2024

work page arXiv 2024
[12]

Cheng, G

Y. Cheng, G. Wang, and Y. Zhao. Rainbow pancyclicity in graph systems. Electron. J. Combin., 28(3):Paper No. 3.24, 9, 2021

work page 2021
[13]

Cheng, Z

Y. Cheng, Z. Wang, and J. Yan. A Dirac-type theorem for arbitrary HamiltonianH-linked digraphs. arXiv:2401.17475v2, 2024

work page arXiv 2024
[14]

F. R. Chung. Regularity lemmas for hypergraphs and quasi-randomness.Random Structures Algorithms, 2(2):241–252, 1991

work page 1991
[15]

Czygrinow, L

A. Czygrinow, L. DeBiasio, H. A. Kierstead, and T. Molla. An extension of the Hajnal- Szemerédi theorem to directed graphs.Combin. Probab. Comput., 24(5):754–773, 2015

work page 2015
[16]

DeBiasio, D

L. DeBiasio, D. Kühn, T. Molla, D. Osthus, and A. Taylor. Arbitrary orientations of Hamilton cycles in digraphs.SIAM J. Discrete Math., 29(3):1553–1584, 2015

work page 2015
[17]

Semi-degreethresholdforanti-directedHamiltoniancycles

L.DeBiasioandT.Molla. Semi-degreethresholdforanti-directedHamiltoniancycles. Electron. J. Combin., 22(4):Paper 4.34, 23, 2015

work page 2015
[18]

Gerbner, A

D. Gerbner, A. Grzesik, C. Palmer, and M. Prorok. Directed Graphs Without Rainbow Stars. Electron. J. Combin., 31(4):Paper No. 4.70, 2024

work page 2024
[19]

Ghouila-Houri

A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien.C. R. Acad. Sci. Paris, 251:495–497, 1960

work page 1960
[20]

Huang and G.-C

R. Huang and G.-C. Rota. On the relations of various conjectures on Latin squares and straightening coefficients.Discrete Math., 128(1-3):225–236, 1994

work page 1994
[21]

Joos and J

F. Joos and J. Kim. On a rainbow version of Dirac’s theorem. Bull. Lond. Math. Soc., 52(3):498–504, 2020

work page 2020
[22]

Kalai and R

G. Kalai and R. Meshulam. A topological colorful Helly theorem.Adv. Math., 191(2):305–311, 2005

work page 2005
[23]

Keevash, D

P. Keevash, D. Kühn, and D. Osthus. An exact minimum degree condition for Hamilton cycles in oriented graphs.J. Lond. Math. Soc. (2), 79(1):144–166, 2009

work page 2009
[24]

Rota’s Basis Conjecture holds asymptotically

A. Pokrovskiy. Rota’s basis conjecture holds asymptotically.arXiv:2008.06045, 2020

work page arXiv 2008
[25]

V. Rödl, E. Szemerédi, and A. Ruciński. An approximate dirac-type theorem for k-uniform hypergraphs. Combinatorica, 28(2):229–260, 2008. 40

work page 2008
[26]

W. Sun, G. Wang, and L. Wei. Transversal structures in graph systems: A survey. arXiv:2412.01121, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024
[27]

Szemerédi

E. Szemerédi. Regular partitions of graphs.Stanford University, 1975

work page 1975
[28]

Thomason

A. Thomason. Paths and cycles in tournaments.Trans. Amer. Math. Soc., 296(1):167–180, 1986

work page 1986
[29]

T. D. Townsend.Extremal problems on graphs, directed graphs and hypergraphs. PhD thesis, University of Birmingham, 2016

work page 2016
[30]

OndirectedversionsoftheHajnal-Szemeréditheorem

A.Treglown. OndirectedversionsoftheHajnal-Szemeréditheorem. Combin. Probab. Comput., 24(6):873–928, 2015. Appendix A Regularity for digraph collections In this section, we prove the regularity lemma for digraph collections (i.e., Lemma 2.2). Before proceeding with the proof, we first make some preparations, including some necessary definitions and key the...

work page 2015
[31]

, V′ L′ and those which are subsets ofC are C′ 1,

Relabel the subclus- ters such that those which are subsets ofV are V ′ 1, . . . , V′ L′ and those which are subsets ofC are C′ 1, . . . ,C′ M ′. For eachc ∈ C \ (C0 ∪ C ′ 0), let D′′ c be the spanning sub-digraph ofDc with vertex set V and edge set uv : {u, v, c} ∈ H ′ 1 or {u, v, c} ∈ H ′ 2 ∪ E(D′± c [V0, V \ (V0 ∪ V ′ 0)]). Let D∗ i := D′ i for i ∈ C 0...

work page
[32]

We define a vertexv ∈ V is i-good if either Gi is ϵ-extremal and v ∈ V \ (C1 i ∪ C2 i ) or Gi is not ϵ-extremal and dGi(v) ≥ ( 1 2 − ϵ3)n

of Gi. We define a vertexv ∈ V is i-good if either Gi is ϵ-extremal and v ∈ V \ (C1 i ∪ C2 i ) or Gi is not ϵ-extremal and dGi(v) ≥ ( 1 2 − ϵ3)n. Note that for eachi ∈ [n] and j ∈ {1, 2}, there are at most2ϵn vertices in Vj that are noti-good. Definition B.3 (absorbing edge, absorbing matching). Let G = {G1, . . . , Gn} be a collection of bipartite graphs...

work page
[33]

Fix any such indicesi, j and vertices u, v

corresponding to Gℓ. Fix any such indicesi, j and vertices u, v. Since v is i-good, we have dGi(v, Ai

work page
[34]

≥ 1 2 − 2ϵ n or dGi(v, Bi

work page
[35]

Assume, without loss of generality, that the former case holds (the latter case is analogous)

≥ 1 2 − 2ϵ n. Assume, without loss of generality, that the former case holds (the latter case is analogous). Since Gi and Gj are δ-crossing and ϵ ≪ δ, one has |Ai 1 ∩ Aj 1| ≥ δn 2 , |Ai 1 ∩ Bj 1| ≥ δn 2 , |Aj 1 ∩ Bi 1| ≥ δn 2 , and |Bi 1 ∩ Bj 1| ≥ δn 2 . Combining |Ai 1 ∩ Aj 1| ≥ δn 2 with dGi(v, Ai

work page
[36]

≥ ( 1 2 − 2ϵ)n, we obtain dGi(v, Aj

work page
[37]

Similarly, we havedGi(v, Bj

≥ |Ai 1 ∩ Aj 1| − |Ai 1| − dGi(v, Ai 1) ≥ δn 2 − ϵn ≥ δn 3 . Similarly, we havedGi(v, Bj

work page
[38]

Recall thatu ∈ V1 and u is j-good, which implies thatu ∈ X j 1 for some X ∈ { A, B}

≥ δn 3 . Recall thatu ∈ V1 and u is j-good, which implies thatu ∈ X j 1 for some X ∈ { A, B}. Since dGj(u, Xj

work page
[39]

≥ ( 1 2 − 2ϵ)n, there are at least ( 1 2 − 2ϵ)n choices for w′ ∈ X j

work page
[40]

Fixing w′ ∈ X j 2, and using dGi(v, X j

Notice that in Gj, every vertex inX j 2 is adjacent to all but at mostϵn vertices in X j 1. Fixing w′ ∈ X j 2, and using dGi(v, X j

work page
[41]

≥ δn 3 , we conclude that there are at leastδn 4 choices for w ∈ X j

work page
[42]

For any vertexv ∈ V, let Cv := {i ∈ [n] : v is i-good}

Thus, |Zj(i, uv)| ≥ δn 4 1 2 − 2ϵ n ≥ 2−4δn2, as desired. For any vertexv ∈ V, let Cv := {i ∈ [n] : v is i-good}. Since e(Cϵ,δ G ) ≥ δn2, there exists a subgraphH of Cϵ,δ G such that |V (H)| ≥ δn and δ(H) ≥ δn. For each i ∈ V (H), define the set Ti := v ∈ V : |NH(i) \ Cv| ≥ δn 2 . Observe that there are at most4ϵn2 pairs (u, i) ∈ V ×[n] such thatu is noti...

work page

[1] [1]

Aharoni, M

R. Aharoni, M. DeVos, S. González Hermosillo de la Maza, A. Montejano, and R. Šámal. A rainbow version of Mantel’s theorem.Adv. Comb., pages Paper No. 2, 12, 2020

work page 2020

[2] [2]

Aharoni and D

R. Aharoni and D. Howard. A rainbow r-partite version of the Erdős-Ko-Rado theorem. Combin. Probab. Comput., 26(3):321–337, 2017

work page 2017

[3] [3]

Babiński, A

S. Babiński, A. Grzesik, and M. Prorok. Directed graphs without rainbow triangles. arXiv:2308.01461, 2023

work page arXiv 2023

[4] [4]

I. Bárány. A generalization of Carathéodory’s theorem.Discrete Math., 40(2-3):141–152, 1982. 39

work page 1982

[5] [5]

Bradshaw

P. Bradshaw. Transversals and bipancyclicity in bipartite graph families.Electron. J. Combin., pages P4–25, 2021

work page 2021

[6] [6]

Chakraborti, J

D. Chakraborti, J. Kim, H. Lee, and J. Seo. Hamilton Transversals in Tournaments.Combi- natorica, 44(6):1381–1400, 2024

work page 2024

[7] [7]

Chakraborti, J

D. Chakraborti, J. Kim, H. Lee, and J. Seo. Transversal cycles and paths in tournaments. arXiv:2407.14300, 2024

work page arXiv 2024

[8] [8]

Cheng, J

Y. Cheng, J. Han, B. Wang, and G. Wang. Rainbow spanning structures in graph and hyper- graph systems. Forum Math. Sigma, 11:Paper No. e95, 20, 2023

work page 2023

[9] [9]

Cheng and K

Y. Cheng and K. Staden. Transversals via regularity.arXiv:2306.03595, 2023

work page arXiv 2023

[10] [10]

Cheng and K

Y. Cheng and K. Staden. Stability of transversal Hamilton cycles and paths.arXiv:2403.09913, 2024

work page arXiv 2024

[11] [11]

Cheng, W

Y. Cheng, W. Sun, G. Wang, and L. Wei. Transversal hamilton paths and cycles. arXiv:2406.13998, 2024

work page arXiv 2024

[12] [12]

Cheng, G

Y. Cheng, G. Wang, and Y. Zhao. Rainbow pancyclicity in graph systems. Electron. J. Combin., 28(3):Paper No. 3.24, 9, 2021

work page 2021

[13] [13]

Cheng, Z

Y. Cheng, Z. Wang, and J. Yan. A Dirac-type theorem for arbitrary HamiltonianH-linked digraphs. arXiv:2401.17475v2, 2024

work page arXiv 2024

[14] [14]

F. R. Chung. Regularity lemmas for hypergraphs and quasi-randomness.Random Structures Algorithms, 2(2):241–252, 1991

work page 1991

[15] [15]

Czygrinow, L

A. Czygrinow, L. DeBiasio, H. A. Kierstead, and T. Molla. An extension of the Hajnal- Szemerédi theorem to directed graphs.Combin. Probab. Comput., 24(5):754–773, 2015

work page 2015

[16] [16]

DeBiasio, D

L. DeBiasio, D. Kühn, T. Molla, D. Osthus, and A. Taylor. Arbitrary orientations of Hamilton cycles in digraphs.SIAM J. Discrete Math., 29(3):1553–1584, 2015

work page 2015

[17] [17]

Semi-degreethresholdforanti-directedHamiltoniancycles

L.DeBiasioandT.Molla. Semi-degreethresholdforanti-directedHamiltoniancycles. Electron. J. Combin., 22(4):Paper 4.34, 23, 2015

work page 2015

[18] [18]

Gerbner, A

D. Gerbner, A. Grzesik, C. Palmer, and M. Prorok. Directed Graphs Without Rainbow Stars. Electron. J. Combin., 31(4):Paper No. 4.70, 2024

work page 2024

[19] [19]

Ghouila-Houri

A. Ghouila-Houri. Une condition suffisante d’existence d’un circuit hamiltonien.C. R. Acad. Sci. Paris, 251:495–497, 1960

work page 1960

[20] [20]

Huang and G.-C

R. Huang and G.-C. Rota. On the relations of various conjectures on Latin squares and straightening coefficients.Discrete Math., 128(1-3):225–236, 1994

work page 1994

[21] [21]

Joos and J

F. Joos and J. Kim. On a rainbow version of Dirac’s theorem. Bull. Lond. Math. Soc., 52(3):498–504, 2020

work page 2020

[22] [22]

Kalai and R

G. Kalai and R. Meshulam. A topological colorful Helly theorem.Adv. Math., 191(2):305–311, 2005

work page 2005

[23] [23]

Keevash, D

P. Keevash, D. Kühn, and D. Osthus. An exact minimum degree condition for Hamilton cycles in oriented graphs.J. Lond. Math. Soc. (2), 79(1):144–166, 2009

work page 2009

[24] [24]

Rota’s Basis Conjecture holds asymptotically

A. Pokrovskiy. Rota’s basis conjecture holds asymptotically.arXiv:2008.06045, 2020

work page arXiv 2008

[25] [25]

V. Rödl, E. Szemerédi, and A. Ruciński. An approximate dirac-type theorem for k-uniform hypergraphs. Combinatorica, 28(2):229–260, 2008. 40

work page 2008

[26] [26]

W. Sun, G. Wang, and L. Wei. Transversal structures in graph systems: A survey. arXiv:2412.01121, 2024

work page internal anchor Pith review Pith/arXiv arXiv 2024

[27] [27]

Szemerédi

E. Szemerédi. Regular partitions of graphs.Stanford University, 1975

work page 1975

[28] [28]

Thomason

A. Thomason. Paths and cycles in tournaments.Trans. Amer. Math. Soc., 296(1):167–180, 1986

work page 1986

[29] [29]

T. D. Townsend.Extremal problems on graphs, directed graphs and hypergraphs. PhD thesis, University of Birmingham, 2016

work page 2016

[30] [30]

OndirectedversionsoftheHajnal-Szemeréditheorem

A.Treglown. OndirectedversionsoftheHajnal-Szemeréditheorem. Combin. Probab. Comput., 24(6):873–928, 2015. Appendix A Regularity for digraph collections In this section, we prove the regularity lemma for digraph collections (i.e., Lemma 2.2). Before proceeding with the proof, we first make some preparations, including some necessary definitions and key the...

work page 2015

[31] [31]

, V′ L′ and those which are subsets ofC are C′ 1,

Relabel the subclus- ters such that those which are subsets ofV are V ′ 1, . . . , V′ L′ and those which are subsets ofC are C′ 1, . . . ,C′ M ′. For eachc ∈ C \ (C0 ∪ C ′ 0), let D′′ c be the spanning sub-digraph ofDc with vertex set V and edge set uv : {u, v, c} ∈ H ′ 1 or {u, v, c} ∈ H ′ 2 ∪ E(D′± c [V0, V \ (V0 ∪ V ′ 0)]). Let D∗ i := D′ i for i ∈ C 0...

work page

[32] [32]

We define a vertexv ∈ V is i-good if either Gi is ϵ-extremal and v ∈ V \ (C1 i ∪ C2 i ) or Gi is not ϵ-extremal and dGi(v) ≥ ( 1 2 − ϵ3)n

of Gi. We define a vertexv ∈ V is i-good if either Gi is ϵ-extremal and v ∈ V \ (C1 i ∪ C2 i ) or Gi is not ϵ-extremal and dGi(v) ≥ ( 1 2 − ϵ3)n. Note that for eachi ∈ [n] and j ∈ {1, 2}, there are at most2ϵn vertices in Vj that are noti-good. Definition B.3 (absorbing edge, absorbing matching). Let G = {G1, . . . , Gn} be a collection of bipartite graphs...

work page

[33] [33]

Fix any such indicesi, j and vertices u, v

corresponding to Gℓ. Fix any such indicesi, j and vertices u, v. Since v is i-good, we have dGi(v, Ai

work page

[34] [34]

≥ 1 2 − 2ϵ n or dGi(v, Bi

work page

[35] [35]

Assume, without loss of generality, that the former case holds (the latter case is analogous)

≥ 1 2 − 2ϵ n. Assume, without loss of generality, that the former case holds (the latter case is analogous). Since Gi and Gj are δ-crossing and ϵ ≪ δ, one has |Ai 1 ∩ Aj 1| ≥ δn 2 , |Ai 1 ∩ Bj 1| ≥ δn 2 , |Aj 1 ∩ Bi 1| ≥ δn 2 , and |Bi 1 ∩ Bj 1| ≥ δn 2 . Combining |Ai 1 ∩ Aj 1| ≥ δn 2 with dGi(v, Ai

work page

[36] [36]

≥ ( 1 2 − 2ϵ)n, we obtain dGi(v, Aj

work page

[37] [37]

Similarly, we havedGi(v, Bj

≥ |Ai 1 ∩ Aj 1| − |Ai 1| − dGi(v, Ai 1) ≥ δn 2 − ϵn ≥ δn 3 . Similarly, we havedGi(v, Bj

work page

[38] [38]

Recall thatu ∈ V1 and u is j-good, which implies thatu ∈ X j 1 for some X ∈ { A, B}

≥ δn 3 . Recall thatu ∈ V1 and u is j-good, which implies thatu ∈ X j 1 for some X ∈ { A, B}. Since dGj(u, Xj

work page

[39] [39]

≥ ( 1 2 − 2ϵ)n, there are at least ( 1 2 − 2ϵ)n choices for w′ ∈ X j

work page

[40] [40]

Fixing w′ ∈ X j 2, and using dGi(v, X j

Notice that in Gj, every vertex inX j 2 is adjacent to all but at mostϵn vertices in X j 1. Fixing w′ ∈ X j 2, and using dGi(v, X j

work page

[41] [41]

≥ δn 3 , we conclude that there are at leastδn 4 choices for w ∈ X j

work page

[42] [42]

For any vertexv ∈ V, let Cv := {i ∈ [n] : v is i-good}

Thus, |Zj(i, uv)| ≥ δn 4 1 2 − 2ϵ n ≥ 2−4δn2, as desired. For any vertexv ∈ V, let Cv := {i ∈ [n] : v is i-good}. Since e(Cϵ,δ G ) ≥ δn2, there exists a subgraphH of Cϵ,δ G such that |V (H)| ≥ δn and δ(H) ≥ δn. For each i ∈ V (H), define the set Ti := v ∈ V : |NH(i) \ Cv| ≥ δn 2 . Observe that there are at most4ϵn2 pairs (u, i) ∈ V ×[n] such thatu is noti...

work page