Optimal stability results on color-biased Hamilton cycles

Mingyuan Rong; Wenchong Chen; Zixiang Xu

REVIEW 4 major objections 4 minor 1 cited by

Optimal stability results on color-biased Hamilton cycles

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that if all Hamilton cycles in a dense edge-colored graph are nearly color-balanced, the graph must be close to one of the known extremal color-partition constructions.

desk verdict Strong and likely correct stability theorems, but the written proof's central B-type definition is reversed relative to its use, making Proposition 2.5 false as stated. read the letter →

arxiv 2507.17739 v2 pith:FPFFSJYG submitted 2025-07-23 math.CO

Wenchong Chen , Mingyuan Rong , Zixiang Xu This is my paper · ORCID

classification math.CO MSC 05C4505C1505C35

keywords color-biasdiscrepancyHamiltoncyclesstabilityedge-coloringbowtieminimumdegreeextremalconstructions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves a stability theorem for color-balanced Hamilton cycles in edge-colored graphs. It shows that if an $n$-vertex graph with minimum degree just above $n/2$ has every Hamilton cycle deviating from equal color counts by less than $m$, then the graph must be close to one of the known extremal constructions: a partition with one dominant part whose edges are nearly monochromatic, or, for three colors, a nearly balanced tripartite color-symmetric graph. The degree threshold $n/2$ is exactly the classical Hamiltonicity threshold, so it cannot be lowered, and the additive error term $\Theta(m)$ is shown to be best possible for two colors. The result places the structural stability threshold for balanced Hamiltonicity at $n/2$, strictly below the extremal threshold $(r+1)n/(2r)$ at which color imbalance is forced.

What carries the argument

The load-bearing local object is the bad bowtie: five vertices $v_1,\dots,v_5$ with edges $v_1v_2,v_1v_3,v_1v_4,v_1v_5,v_2v_3,v_4v_5$, together with the color-shift function $f(B,k)=\mathbf{1}_k(v_1v_2)+\mathbf{1}_k(v_1v_3)+\mathbf{1}_k(v_4v_5)-\mathbf{1}_k(v_1v_4)-\mathbf{1}_k(v_1v_5)-\mathbf{1}_k(v_2v_3)$. A bowtie is bad when some $f(B,k)\ne 0$; replacing the first three edges by the second three gives a new Hamilton cycle whose color-$k$ count changes by $f(B,k)$. The proof bounds the number of disjoint bad bowties by $2rm$, deletes their vertices, and in the remaining graph classifies every vertex as one of three types $A(j,k,\ell)$, $B(k,\ell)$, or $C(k)$ according to the colors that occur inside its neighborhood. The completeness of this trichotomy turns local color patterns into the global dichotomy of Proposition 2.5, and the dichotomy yields the matching-exclusion statements of the theorems.

What would settle it

Enumerate all $3^6$ colorings of the six edges of the bowtie (or all $2^6$ for two colors), compute $f(B,k)$ for each color, and compare the patterns with $f(B,k)=0$ for every $k$ against the list in Fig. 2.1. If any zero-bias coloring is missing from the figure, two vertex-disjoint edges in some neighborhood could carry different types without forming a bad bowtie, and Proposition 2.4 would fail.

Watch

Extended reading notes

Core claim

On its own terms, the central claim is that the only way for a dense graph to keep all its Hamilton cycles nearly color-balanced is to sit inside one of the extremal color-partition constructions. For $r\ge 2$, $r\ne 3$, under $\delta(G)=n/2+6r^2m$ and $d_\chi(H)<m$ for every Hamilton cycle $H$, the graph admits a partition $V_1\cup\cdots\cup V_r$ with $|V_k|=(r+1)n/(2r)$ and $|V_i|=n/(2r)$ for $i\ne k$ such that $G[V_k]$ is $(100r^2m,k)$-nearly monochromatic, each $G[V_i,V_k]$ is $(100r^2m,i)$-nearly monochromatic, and the induced graph on the small parts is $100r^2m$-nearly empty. For $r=3$ there is a second allowed alternative, a balanced three-part structure in which each cross pair $G[V_i,V_j]$ is $(900m,k)$-nearly monochromatic for the third color $k$ and each part is nearly empty. These statements place the stability threshold at $n/2$ and make the additive error linear in $m$; the linear error is optimal for $r=2$.

Load-bearing premise

The load-bearing premise is that the small figure listing all non-bad six-edge bowtie colorings is complete; the paper asserts this with 'one can easily check' and gives no proof, and if a coloring is missing the vertex classification collapses.

Editorial extensions

If this is right

For every $r\ge 2$, $r\ne 3$, the hypotheses imply a partition into parts of sizes $(r+1)n/(2r)$ and $n/(2r)$ with the three matching-exclusion bounds of Theorem 1.2 holding at scale $100r^2m$.
For $r=3$, any such graph is either the balanced three-part color-symmetric structure or the single-dominant-part structure, and the two alternatives are mutually exclusive.
The degree condition cannot be relaxed to $n/2+o(m)$ without allowing the two-color counterexample, so the additive error term in the theorem is best possible for $r=2$.
In this degree regime every Hamilton cycle is forced to be nearly uniform in its color counts, and the structural obstruction to imbalance is a large monochromatic hub.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A reader who wants to stress-test the proof should start with the six-edge enumeration: an exhaustive check of $3^6$ colorings would confirm or refute the 'one can easily check' step in Proposition 2.4.
The same bad-bowtie replacement should transfer to Hamilton paths or perfect matchings, yielding analogous stability dichotomies for other spanning subgraphs in edge-colored graphs.
For $r\ge 3$ the optimality of the $\Theta(m)$ error remains open; if counterexamples exist, they may interpolate between the dominant-hub and the balanced tripartite extremal forms.
If the paper's final local-resilience conjecture holds, the structural dichotomy would survive even when the global minimum-degree assumption is replaced by a much weaker robustness hypothesis.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The main results are natural and likely correct: Theorems 1.2 and 1.3 locate the structural stability threshold for color-biased Hamilton cycles at the Hamiltonicity threshold n/2, with additive error optimal for r=2, and the r=3 symmetric case is handled carefully. The proof idea—remove bad bowties, classify vertices, force a global dichotomy—is sound. But the written proof has a load-bearing inconsistency in the classification. Under the formal definition of Type B(k,l) (Section 2.3), a vertex has all incident edges colored k and all edges inside its neighborhood colored l. Proposition 2.5 then claims that for r≠3, all vertices lie in union of B(k,l) over l≠k plus C(k). The paper's own r=2 extremal construction refutes this: V1 vertices are B(1,2), V2 vertices are C(2), and no single k gives the claimed union. Section 2.4 later counts as if B(k,l) meant the opposite—vertices whose incident edges are color l—and with that reading the dichotomy works. So the fix is likely a systematic index swap, but as printed the proof cannot be verified.

Second soft spot: Proposition 2.4's trichotomy depends on an unproved enumeration of non-bad bowtie color patterns in Figure 2.1 ('one can easily check'). That gap is independent of the indexing bug and needs a real argument. Minor issue at the end: matching-exclusion arguments occasionally write |V(M)| ≤ |W| when the proof only shows M ⊆ E(W); the bounds are the same order, so it's cosmetic.

Credit where due: the paper is not circular, uses Pósa's lemma cleanly, gives a sharp counterexample for the Θ(m) term when r=2, and engages honestly with Chen-Cheng-Yan. No free parameters, no fitted entities beyond the bowtie, which is a legitimate local witness.

Bottom line: the theorems deserve proof and are probably true, but this manuscript is not publishable as is. Send it to a serious referee, with instructions to fix the B(k,l) indexing and supply the bowtie enumeration.

Referee Report

4 major / 4 minor

Summary. This paper proves stability theorems for edge-colored graphs in which every Hamilton cycle has small color-bias. Theorem 1.2 (for r≠3) and Theorem 1.3 (for r=3) assert that if δ(G)=n/2+Θ(m) and every Hamilton cycle has discrepancy <m, then G admits a partition into one large and r−1 small parts (or, in the r=3 case, a symmetric tripartite alternative) such that all color-class complements have matchings of size at most O(r²m). The proof removes O(rm) vertices containing 'bad bowties', classifies the remaining vertices into local types A, B, C, proves a global dichotomy for G1, and then converts the dichotomy into matching-exclusion statements. A separate construction with two colors and minimum degree n/2+o(m) shows that the additive Θ(m) error is best possible for r=2.

Significance. If the proof can be completed, the results are significant: they move the structural stability threshold for color-balanced Hamiltonicity from the extremal threshold (r+1)n/(2r) down to the Dirac threshold n/2, with an error term Θ(m), and they establish optimality of the error for r=2. The 'bad bowtie' local-to-global mechanism is a promising new ingredient, and the use of Pósa's lemma to convert local color imbalances into forbidden Hamilton-cycle discrepancies is elegant. The paper is not merely an incremental extension: it addresses the near-balance regime at degrees far below the extremal threshold, and the quantitative lower-bound construction for r=2 is a genuine addition. However, the significance is conditional on repairing several load-bearing gaps in the written proof, which are listed below.

major comments (4)

[Section 2.3 (Definition of B(k,l)), Proposition 2.5(1), and Section 2.4] With the formal definition B(k,l) = {v : L(v)={k} and all edges in E(G1[N_k(v)]) have color l}, the r=2 extremal construction of Section 1 (V1 independent, V2 complete, V1-V2 edges color 1, internal V2 edges color 2) contains no bad bowties, so G1=G; it satisfies V(G1)=B(1,2)∪C(2). Proposition 2.5(1) claims a single k with V(G1)=⋃_{l≠k}B(k,l)∪C(k), but for k=1 the right-hand side is only V1 and for k=2 it is only V2. Thus Proposition 2.5 is false as stated. The proof and Section 2.4 systematically use B(k,l) with the reverse meaning, namely 'vertices whose incident edges all have color l', which corresponds to B(l,k). The indices must be reversed consistently throughout the dominant-color branch before the structural dichotomy can be true.
[Section 2.3, proof of Proposition 2.4] The proof that two vertex-disjoint edges in G1[N(v)] of different types create a bad bowtie is the entire justification for the trichotomy into types A, B, C, but it rests on the assertion that the enumeration of non-bad bowties in Fig. 2.1 is complete and on the phrase 'one can easily check'. No proof of the completeness of that enumeration is provided, and the figure is not described in the text. Since every subsequent step, including Proposition 2.5 and Theorems 1.2 and 1.3, depends on this uniqueness-of-type fact, the enumeration needs a rigorous proof or a machine-checked certificate rather than an assertion.
[Section 2.4, proof of Theorem 1.3(1)] The displayed inequality 2(|A(1,2,3)|−2|V0|) ≤ |A(2,3,1)|+|A(3,1,2)| is incorrect. A vertex in A(2,3,1)∪A(3,1,2) may have both Hamilton-cycle neighbors in A(1,2,3), so the number of cross edges is bounded by 2(|A(2,3,1)|+|A(3,1,2)|), not by that sum. With the correct factor 2, the argument gives only |A(1,2,3)| ≤ n/2+O(rm), which does not imply the claimed |A(1,2,3)| ≤ n/3+10rm. The balance |A_i| ≈ n/3 needs a different proof, for example by counting the three color classes through the incidence identities 2|A_i| = (number of Hamilton edges of the corresponding pair of colors) + O(|V0|) and using dχ(H)<m.
[Section 2.3, proof of Proposition 2.5(2)] The line 'no vertex in G1 can be adjacent to an edge colored with any color outside of {j,k,l}, which implies that r=3' is not a valid inference as written. An r-coloring need not be surjective, and colors outside {j,k,l} could appear on edges incident to the removed set V0; both are compatible with r>3. If the intended argument is that any Hamilton cycle would then have too few edges of a color outside {j,k,l}, that color-bias argument must be written out and must account for the up to O(rm) edges incident to V0. As printed, the A-type case is not excluded for r>3.

minor comments (4)

[Theorem 1.2 and Theorem 1.3 statements] The theorems state δ(G)=n/2+6r²m (and δ(G)=n/2+54m for r=3), while the abstract and the proofs use the condition 'exceeding' or 'at least'. The statements should say δ(G) ≥ n/2+6r²m (respectively ≥ n/2+54m).
[Section 2.4, matching-exclusion bounds] The displayed bounds |V(M_i)| ≤ |W_i| are false for matchings whose edges have exactly one endpoint in W_i and one endpoint outside; the correct bound is 2|W_i|. Since 2·40r²m = 80r²m < 100r²m, the quantitative conclusions still survive after this correction, but the inequalities should be repaired.
[Section 2, opening paragraph] The proof section begins with the assumption dχ(H) ≤ m for every Hamilton cycle, whereas Theorems 1.2 and 1.3 assume dχ(H) < m. These should be aligned.
[Throughout] There are several typographical errors, including 'an graph' in Lemma 2.1 and 'n-vetrex' in the introduction; the manuscript would benefit from a careful proofreading pass.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained and the target theorems do not reduce to their hypotheses.

full rationale

The derivation chain is self-contained against external benchmarks. Theorems 1.2 and 1.3 are proved from Pósá's Lemma 2.1, the new bad-bowtie machinery, and elementary counting arguments; no parameter is fitted to the conclusion and no 'prediction' is defined in terms of the target structure. The only self-citation is [9] in the introduction, where it is used to motivate the problem, and it is not load-bearing: the proof never invokes [9] to establish the dichotomy, and the present result is an extension rather than a restatement of it. The type classification in Section 2.3 is a definition, and the structural conclusion is claimed to follow from the no-bad-bowtie condition via Proposition 2.4; even if the classification step contains a proof gap or is incorrect, that is a correctness concern, not circularity. The counterexample showing optimality of the error term is an independent construction. Therefore the paper receives a circularity score of 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The central claim rests on standard external theorems (Pósa's lemma, Dirac's theorem) and on a case-analysis enumeration specific to this paper. There are no fitted parameters or invented physical entities; the bad bowtie is a proof gadget. The only input specific to this paper is the unproved bowtie list and the resulting classification, which are explicit combinatorial checks rather than hidden assumptions.

assumptions (3)

standard math Pósa's lemma (Lemma 2.1, cited from [30])
Used in Proposition 2.3 to extend the path systems L1 and L2 into Hamilton cycles; a classical external theorem accepted without proof in this paper.
ad hoc to paper The enumeration of non-bad bowtie color patterns in Fig. 2.1 is complete
Load-bearing for Proposition 2.4, asserted by inspection of the figure rather than derived; if incomplete, the vertex-type trichotomy could fail.
domain assumption Convention that n is sufficiently large and floors/ceilings are omitted
Standard in extremal graph theory; the stated inequalities are asymptotic and consistent with the use of large n throughout.

invented entities (1)

bad bowtie
purpose: A 5-vertex, 6-edge local configuration whose color-count function f(B,k) changes by a fixed nonzero amount under a swap inside a Hamilton cycle; used to certify local color imbalance.
A proof device introduced in Definition 2.2; it has no external falsifiable handle, but it is a mathematical construct rather than a physical postulate, so it does not trigger the graviton problem.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimal stability results on color-biased Hamilton cycles." pith.science (2026). https://pith.science/paper/FPFFSJYG

@misc{pith2026250717739,
  author       = {Pith},
  title        = {Pith review of: Optimal stability results on color-biased Hamilton cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FPFFSJYG}},
  note         = {Machine review of arXiv:2507.17739}
}

abstract

We investigate Hamilton cycles in edge-colored graphs with $ r $ colors, focusing on the notion of color-bias (discrepancy), the maximum deviation from uniform color frequencies along a cycle. Foundational work by Balogh, Csaba, Jing, and Pluh\'{a}r, and the later generalization by Freschi, Hyde, Lada, and Treglown, as well as an independent work by Gishboliner, Krivelevich, and Michaeli, established that any $n$-vertex graph with minimum degree exceeding $ \frac{(r+1)n}{2r} + \frac{m}{2}$ contains a Hamilton cycle with color-bias at least $m$, and characterized the extremal graphs with minimum degree $\frac{(r+1)n}{2r}$ in which all Hamilton cycles are perfectly balanced. We prove the optimal stability results: for any positive integers $r\ge 2$ and $ m < 2^{-6} r^{2} n,$ if every Hamilton cycle in an $ n $-vertex graph with minimum degree exceeding $ \frac{n}{2} + 6r^{2}m $ has color-bias less than $ m $, then the graph must closely resemble the extremal constructions of Freschi, Hyde, Lada, and Treglown. The leading term $ \frac{n}{2} $ in the degree condition is optimal, as it is the sharp threshold for guaranteeing Hamiltonicity. Moreover, we show the additive error term $\Theta(m)$ is also best possible when $m$ is large and $r=2$, since weaker condition $\frac{n}{2}+o(m)$ allow for a counterexample. Notably, the structural stability threshold $ \frac{1}{2} $ lies strictly below the extremal threshold $ \frac{1}{2} + \frac{1}{2r} $ required to force color imbalance. Our proof leverages local configurations to deduce global structure, revealing a rigid combinatorial dichotomy.

Figures

Figures reproduced from arXiv: 2507.17739 by the authors.

**Figure 1.1.** Two extremal constructions for general r ě 2 and for r “ 3 • In the first construction, the induced subgraph GrVrs is exactly monochromatic in color r, and hence ps, rq-nearly monochromatic for any s. • In the first construction, each bipartite subgraph GrVi , Vrs with i ‰ r is exactly monochromatic in color i, and thus ps, iq-nearly monochromatic. In the second construction for r “ 3, for each pair ti, ju P ` r3s 2… view at source ↗

**Figure 1.2.** A construction witnessing the optimality of the error term [PITH_FULL_IMAGE:figures/full_fig_p005_1_2.png] view at source ↗

**Figure 2.1.** The top row illustrates all structurally distinct bowties that are not bad, while the bottom [PITH_FULL_IMAGE:figures/full_fig_p007_2_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Layer barriers for colour-biased tight Hamilton cycles
math.CO 2026-08 accept novelty 8.0 of 10

A new family of layer barriers for colour-biased tight Hamilton cycles gives a counterexample to the recent conjecture of Behague, Clemen, Hyde and Morrison on minimum vertex degree thresholds.

Reference graph

Works this paper leans on

32 extracted references · 28 canonical work pages · cited by 1 Pith paper

[1]

Andr´ asfai, P

B. Andr´ asfai, P. Erd˝ os, and V. T. S´ os. On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math., 8:205–218, 1974

1974
[2]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluh´ ar. On the discrepancies of graphs.Electron. J. Combin., 27(2):Paper No. 2.12, 14, 2020

work page 2020
[3]

Balogh, B

J. Balogh, B. Csaba, A. Pluh´ ar, and A. Treglown. A discrepancy version of the Hajnal-Szemer´ edi theorem. Combin. Probab. Comput., 30(3):444–459, 2021

work page 2021
[4]

Balogh, A

J. Balogh, A. Treglown, and C. Z´ arate-Guer´ en. A note on color-bias perfect matchings in hypergraphs. SIAM J. Discrete Math. , 38(4):2543–2552, 2024

work page 2024
[5]

Bollob´ as, T

B. Bollob´ as, T. I. Fenner, and A. M. Frieze. An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica, 7(4):327–341, 1987

work page 1987
[6]

Bradaˇ c

D. Bradaˇ c. Powers of Hamilton cycles of high discrepancy are unavoidable. Electron. J. Combin., 29(3):Paper No. 3.22, 26, 2022

work page 2022
[7]

Bradaˇ c, M

D. Bradaˇ c, M. Christoph, and L. Gishboliner. Minimum degree threshold forH-factors with high discrepancy. Electron. J. Combin., 31(3):Paper No. 3.33, 82, 2024

work page 2024
[8]

Chazelle

B. Chazelle. The discrepancy method. Cambridge University Press, Cambridge, 2000. Randomness and complexity

work page 2000

Show all 32 references

[9]

W. Chen, X. Cheng, and Z. Yan. Colour-biased Hamilton cycles in randomly perturbed graphs. arXiv preprint, arXiv: 2506.04189, 2025

2025 arXiv
[10]

Csaba, D

B. Csaba, D. K¨ uhn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures. Mem. Amer. Math. Soc. , 244(1154):v+164, 2016

2016
[11]

Cuckler and J

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

2009
[12]

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

1952
[13]

Erd˝ os, Z

P. Erd˝ os, Z. F¨ uredi, R. J. Gould, and D. S. Gunderson. Extremal graphs for intersecting triangles. J. Combin. Theory Ser. B , 64(1):89–100, 1995

1995
[14]

Ferber, E

A. Ferber, E. Long, and B. Sudakov. Counting Hamilton decompositions of oriented graphs. Int. Math. Res. Not. IMRN , (22):6908–6933, 2018. 13

2018
[15]

J. Fox, M. W. Xu, and Y. Zhou. Discrepancy in modular arithmetic progressions. Compos. Math., 158(11):2082–2108, 2022

2022
[16]

J. Fox, M. W. Xu, and Y. Zhou. Discrepancy of arithmetic progressions in grids. Mathematika, 70(1):Paper No. e12237, 31, 2024

2024
[17]

Freschi, J

A. Freschi, J. Hyde, J. Lada, and A. Treglown. A note on color-bias Hamilton cycles in dense graphs. SIAM J. Discrete Math. , 35(2):970–975, 2021

2021
[18]

Freschi and A

A. Freschi and A. Lo. An oriented discrepancy version of Dirac’s theorem. J. Combin. Theory Ser. B, 169:338–351, 2024

2024
[19]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli. Color-biased Hamilton cycles in random graphs. Random Structures Algorithms, 60(3):289–307, 2022

2022
[20]

Gishboliner, M

L. Gishboliner, M. Krivelevich, and P. Michaeli. Discrepancies of spanning trees and Hamilton cycles. J. Combin. Theory Ser. B , 154:262–291, 2022

2022
[21]

Hefetz, M

D. Hefetz, M. Krivelevich, and T. Szab´ o. Hamilton cycles in highly connected and expanding graphs. Combinatorica, 29(5):547–568, 2009

2009
[22]

M. Kang, T. Makai, and O. Pikhurko. Supersaturation problem for the bowtie. European J. Combin., 88:103107, 27, 2020

2020
[23]

Krivelevich

M. Krivelevich. The critical bias for the Hamiltonicity game is p1`op1qqn{ lnn. J. Amer. Math. Soc., 24(1):125–131, 2011

2011
[24]

Krivelevich, C

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

2014
[25]

K¨ uhn, J

D. K¨ uhn, J. Lapinskas, D. Osthus, and V. Patel. Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. Proc. Lond. Math. Soc. (3) , 109(3):733–762, 2014

2014
[26]

K¨ uhn and D

D. K¨ uhn and D. Osthus. Hamilton decompositions of regular expanders: a proof of Kelly’s conjecture for large tournaments. Adv. Math., 237:62–146, 2013

2013
[27]

Y. Li, L. Feng, and Y. Peng. Spectral supersaturation: Triangles and bowties. European Journal of Combinatorics, 128:104171, 2025

2025
[28]

Matouˇ sek.Geometric discrepancy, volume 18 of Algorithms and Combinatorics

J. Matouˇ sek.Geometric discrepancy, volume 18 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999. An illustrated guide

1999
[29]

Matouˇ sek and J

J. Matouˇ sek and J. Spencer. Discrepancy in arithmetic progressions. J. Amer. Math. Soc. , 9(1):195–204, 1996

1996
[30]

L. P´ osa. On the circuits of finite graphs. Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 8:355–361 (1964), 1963

1964
[31]

K. F. Roth. Remark concerning integer sequences. Acta Arith., 9:257–260, 1964

1964
[32]

T. Tao. The Erd˝ os discrepancy problem. Discrete Anal., pages Paper No. 1, 29, 2016. 14

2016

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Andr´ asfai, P

B. Andr´ asfai, P. Erd˝ os, and V. T. S´ os. On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math., 8:205–218, 1974

1974

[2] [2]

Balogh, B

J. Balogh, B. Csaba, Y. Jing, and A. Pluh´ ar. On the discrepancies of graphs.Electron. J. Combin., 27(2):Paper No. 2.12, 14, 2020

work page 2020

[3] [3]

Balogh, B

J. Balogh, B. Csaba, A. Pluh´ ar, and A. Treglown. A discrepancy version of the Hajnal-Szemer´ edi theorem. Combin. Probab. Comput., 30(3):444–459, 2021

work page 2021

[4] [4]

Balogh, A

J. Balogh, A. Treglown, and C. Z´ arate-Guer´ en. A note on color-bias perfect matchings in hypergraphs. SIAM J. Discrete Math. , 38(4):2543–2552, 2024

work page 2024

[5] [5]

Bollob´ as, T

B. Bollob´ as, T. I. Fenner, and A. M. Frieze. An algorithm for finding Hamilton paths and cycles in random graphs. Combinatorica, 7(4):327–341, 1987

work page 1987

[6] [6]

Bradaˇ c

D. Bradaˇ c. Powers of Hamilton cycles of high discrepancy are unavoidable. Electron. J. Combin., 29(3):Paper No. 3.22, 26, 2022

work page 2022

[7] [7]

Bradaˇ c, M

D. Bradaˇ c, M. Christoph, and L. Gishboliner. Minimum degree threshold forH-factors with high discrepancy. Electron. J. Combin., 31(3):Paper No. 3.33, 82, 2024

work page 2024

[8] [8]

Chazelle

B. Chazelle. The discrepancy method. Cambridge University Press, Cambridge, 2000. Randomness and complexity

work page 2000