pith. sign in

arxiv: 1907.00964 · v1 · pith:J3I57JXAnew · submitted 2019-07-01 · 🧮 math.CO

Tur\'an theorems for unavoidable patterns

Ant\'onio Gir\~ao , Bhargav Narayanan This is my paper

Pith reviewed 2026-05-25 11:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords Turán theoremsRamsey theoryunavoidable patternsgraph colouringstournamentsextremal graph theoryoff-diagonal Ramsey numbersstability methods
0
0 comments X

The pith

Any two-colouring of K_n that deviates by more than n to the power -1/t from monochromatic must contain an unavoidable t-colouring on 2t vertices.

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

The paper proves quantitative Turán-type results that force the appearance of specific forbidden configurations in edge colourings and in tournaments once the deviation from a simple extremal example exceeds a power-law threshold. For colourings, the threshold is on the order of n^{-1/t} for any t at least 3; for tournaments the threshold is n^{-1 over ceiling of t/2}. These statements determine the correct order of magnitude for the associated off-diagonal Ramsey numbers, provided a standard conjecture on bipartite Turán numbers holds. A reader would care because the results give precise density conditions under which Ramsey phenomena become unavoidable rather than merely existent.

Core claim

For every t ≥ 3, every two-colouring of the edges of the complete graph on n vertices whose red or blue graph differs from the empty graph or the complete graph by more than δ n^2 edges contains an unavoidable t-colouring whenever δ is much larger than n^{-1/t}; an unavoidable t-colouring is any two-colouring of K_{2t} in which one colour class induces either a clique of size t or two disjoint cliques of size t. Likewise, every tournament on n vertices whose transitive closure differs from the transitive tournament by more than δ n^2 edges contains an unavoidable t-tournament whenever δ is much larger than n^{-1/⌈t/2⌉}; an unavoidable t-tournament is the blow-up of a directed 3-cycle in each

What carries the argument

The unavoidable t-colouring (a two-edge-colouring of K_{2t} in which one colour spans a K_t or two disjoint K_t's) and the unavoidable t-tournament (the balanced blow-up of a cyclic triangle by transitive tournaments of order t); these objects serve as the minimal forbidden substructures whose forced presence is established by stability and counting arguments.

If this is right

  • The order of magnitude of the off-diagonal Ramsey numbers r(t,t;2t) and their tournament analogues is settled up to constants.
  • The same stability methods that prove the existence statements also yield the sharp thresholds once the bipartite conjecture is assumed.
  • The results apply uniformly for all t ≥ 3 and give matching upper and lower bounds on the minimal deviation needed to force the patterns.
  • The tournament result uses a different exponent ceiling(t/2) that reflects the structure of transitive tournaments.

Where Pith is reading between the lines

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

  • The same pattern-forcing technique could be applied to other Ramsey problems whose extremal examples are blow-ups or complete multipartite graphs.
  • If the bipartite Turán conjecture fails, the paper's existence theorems remain valid but the precise order of the Ramsey numbers would need to be revisited.
  • The unavoidable patterns are minimal in the sense that removing any edge from them produces a colourable structure, suggesting they are the right minimal witnesses for the Ramsey property.

Load-bearing premise

The claim that the thresholds are sharp up to constant factors rests on the truth of the standard conjecture giving the asymptotic order of the bipartite Turán number ex(n, K_{s,t}).

What would settle it

An explicit two-colouring of K_n with only o(n^{2-1/t}) edges in each colour class that avoids every unavoidable t-colouring, or a counterexample to the bipartite Turán conjecture that produces a different exponent for the extremal function.

read the original abstract

We prove Tur\'an-type theorems for two related Ramsey problems raised by Bollob\'as and by Fox and Sudakov. First, for $t \ge 3$, we show that any two-colouring of the complete graph on $n$ vertices that is $\delta$-far from being monochromatic contains an \emph{unavoidable $t$-colouring} when $\delta \gg n^{-1/t}$, where an unavoidable $t$-colouring is any two-colouring of a clique of order $2t$ in which one colour forms either a clique of order $t$ or two disjoint cliques of order $t$. Next, for $ t\ge 3$, we show that any tournament on $n$ vertices that is $\delta$-far from being transitive contains an \emph{unavoidable $t$-tournament} when $\delta \gg n^{-1/\lceil t/2 \rceil}$, where an unavoidable $t$-tournament is the blow-up of a cyclic triangle obtained by replacing each vertex of the triangle by a transitive tournament of order $t$. Conditional on a well-known conjecture about bipartite Tur\'an numbers, both results are sharp up to implied constants and hence determine the order of magnitude of the corresponding off-diagonal Ramsey numbers.

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

0 major / 3 minor

Summary. The paper proves Turán-type theorems for unavoidable patterns in Ramsey problems. For t ≥ 3, any 2-edge-coloring of K_n that is δ-far from monochromatic contains an unavoidable t-coloring (a 2-coloring of K_{2t} in which one color class contains a K_t or two disjoint K_t's) whenever δ ≫ n^{-1/t}. Similarly, any tournament on n vertices that is δ-far from transitive contains an unavoidable t-tournament (the blow-up of a directed cycle of length 3 with each vertex replaced by a transitive tournament on t vertices) whenever δ ≫ n^{-1/⌈t/2⌉}. Both results are shown to be sharp up to constants, conditional on a standard conjecture on bipartite Turán numbers.

Significance. If the results hold, they determine the order of magnitude of the corresponding off-diagonal Ramsey numbers for these unavoidable configurations, directly addressing open questions posed by Bollobás and by Fox-Sudakov. The unconditional existence theorems constitute the core contribution; the explicit conditioning of the sharpness statements on an external conjecture is a strength that avoids overclaiming. The work supplies concrete thresholds linking distance from the extremal examples to the forced appearance of the patterns.

minor comments (3)
  1. [Introduction] §1, definition of unavoidable t-colouring: the parenthetical description of the two cases for the red (or blue) clique could be supplemented by a small explicit example (e.g., t=3) to aid readability.
  2. [Section 4] The proof of the tournament result (likely §4) invokes a reduction to the graph-coloring case; a one-sentence pointer to the precise lemma used would clarify the dependence.
  3. [Theorem statements] Notation for the distance parameter δ is introduced in the abstract and §1 but is not restated when the main theorems are formally stated; a uniform definition block would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. The report accurately summarizes the main results and their significance in addressing questions of Bollobás and Fox-Sudakov.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The central existence theorems are stated unconditionally and proved directly via combinatorial arguments on δ-far colorings and tournaments. Sharpness is explicitly flagged as conditional on an external conjecture about bipartite Turán numbers (not an author-defined quantity or self-citation). No steps reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard combinatorial axioms and one external conjecture for sharpness; no free parameters are fitted inside the paper and no new entities are postulated.

axioms (2)
  • standard math Standard results and techniques from extremal graph theory (Turán-type theorems)
    Invoked to prove the existence of the unavoidable patterns at the stated densities.
  • domain assumption Well-known conjecture on bipartite Turán numbers
    Used only for the conditional sharpness claim that the thresholds are optimal up to constants.

pith-pipeline@v0.9.0 · 5758 in / 1547 out tokens · 40973 ms · 2026-05-25T11:30:54.954351+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

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

  1. The balancing number and list balancing number of some graph classes

    math.CO 2020-11 unverdicted novelty 7.0

    The list balancing number always exists, coincides with the balancing number when the latter does, and is exactly determined for cycles except 4k-cycles (tight bounds) with general bounds via extremal numbers and a su...

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 1 Pith paper

  1. [1]

    Conlon, A new upper bound for diagonal Ramsey numbers , Ann

    D. Conlon, A new upper bound for diagonal Ramsey numbers , Ann. of Math. 170 (2009), 941–960

    work page 2009

  2. [2]

    Cutler and B

    J. Cutler and B. Mont´ agh, Unavoidable subgraphs of colored graphs , Discrete Math. 308 (2008), 4396–4413

    work page 2008

  3. [3]

    Erd˝ os,Some remarks on the theory of graphs , Bull

    P. Erd˝ os,Some remarks on the theory of graphs , Bull. Amer. Math. Soc. 53 (1947), 292–294

    work page 1947

  4. [4]

    Erd˝ os and L

    P. Erd˝ os and L. Moser, On the representation of directed graphs as unions of orderings, Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl.9 (1964), 125–132

    work page 1964

  5. [5]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres, A combinatorial problem in geometry , Compositio Math. 2 (1935), 463–470. 25

    work page 1935

  6. [6]

    Fox and B

    J. Fox and B. Sudakov, Unavoidable patterns , J. Combin. Theory Ser. A 115 (2008), 1561–1569

    work page 2008

  7. [7]

    , Dependent random choice , Random Structures Algorithms 38 (2011), 68–99

    work page 2011

  8. [8]

    F¨ uredi and M

    Z. F¨ uredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems , Erd˝ os centennial, Bolyai Soc. Math. Stud., vol. 25, J´ anos Bolyai Math. Soc., Budapest, 2013, pp. 169–264

    work page 2013

  9. [9]

    R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, 2 nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wi- ley & Sons, Inc., New York, 1990

    work page 1990

  10. [10]

    K˝ ovari, V

    T. K˝ ovari, V. T. S´ os, and P. Tur´ an,On a problem of K . Zarankiewicz, Collo- quium Math. 3 (1954), 50–57

    work page 1954

  11. [11]

    Long, Large unavoidable subtournaments , Combin

    E. Long, Large unavoidable subtournaments , Combin. Probab. Comput. 26 (2017), 68–77

    work page 2017

  12. [12]

    F. P. Ramsey, On a problem of formal logic , Proc. London Math. Soc. 30 (1930), 264–286

    work page 1930

  13. [13]

    Thomason, An upper bound for some Ramsey numbers , J

    A. Thomason, An upper bound for some Ramsey numbers , J. Graph Theory 12 (1988), 509–517. School of Mathematics, University of Birmingham, Edgbasto n, Birmingham, B15 2TT, UK E-mail address : giraoa@bham.ac.uk Department of Mathematics, Rutgers University, Piscatawa y, NJ 08854, USA E-mail address : narayanan@math.rutgers.edu 26

    work page 1988