pith. sign in

Tur\'an theorems for unavoidable patterns

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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.

fields

math.CO 1

years

2020 1

verdicts

UNVERDICTED 1

representative citing papers

The balancing number and list balancing number of some graph classes

math.CO · 2020-11-22 · 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 surprisingly large value for K5.

citing papers explorer

Showing 1 of 1 citing paper.

  • The balancing number and list balancing number of some graph classes math.CO · 2020-11-22 · unverdicted · none · ref 11 · internal anchor

    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 surprisingly large value for K5.