We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph $K_{2,\ell}$. This includes the containment of …
We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph $K_{2,\ell}$. This includes the containment of Hamilton paths and cycles, and has applications in the random geometric graph model. Our proof provides a greedy algorithm for constructing such structures.
The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in …
The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in $G$. Given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum $N$ such that whenever the edges of the complete graph $K_N$ are coloured with red and blue, there exists either a red copy of $G$ or a blue copy of $H$.
 We prove that for all sufficiently large $n$ we have$$ R(P_{3n}^2,P_{3n}^2)=R(P_{3n+1}^2,P_{3n+1}^2)=R(C_{3n}^2,C_{3n}^2)=9n-3\mbox{ and } R(P_{3n+2}^2,P_{3n+2}^2)=9n+1.$$
 We also show that for any $\gamma>0$ and $\Delta$ there exists $\beta>0$ such that the following holds: If $G$ can be coloured with three colours such that all colour classes have size at most $n$, the maximum degree $\Delta(G)$ of $G$ is at most $\Delta$, and $G$ has bandwidth at most $\beta n$, then $R(G,G)\le (3+\gamma)n$.
Answering a question by Letzter and Snyder, we prove that for large enough $k$ any $n$-vertex graph $G$ with minimum degree at least $\frac{1}{2k-1}n$ and without odd cycles of length …
Answering a question by Letzter and Snyder, we prove that for large enough $k$ any $n$-vertex graph $G$ with minimum degree at least $\frac{1}{2k-1}n$ and without odd cycles of length less than $2k+1$ is $3$-colourable. In fact, we prove a stronger result that works with a slightly smaller minimum degree.
Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the …
Schur's theorem states that in any $k$-colouring of the set of integers $[n]$ there is a monochromatic solution to $a+b=c$, provided $n$ is sufficiently large. Abbott and Wang studied the size of the largest subset of $[n]$ such that there is a $k$-colouring avoiding a monochromatic $a+b=c$. In other directions, the minimum number of $a+b=c$ in $k$-colourings of $[n]$ and the probability threshold in random subsets of $[n]$ for the property of having a monochromatic $a+b=c$ in any $k$-colouring were investigated. In this paper, we study natural generalisations of these streams to products $ab=c$, in a deterministic, random, and randomly perturbed environments.
We denote by $\text{ex}(n, H, F)$ the maximum number of copies of $H$ in an $n$-vertex graph that does not contain $F$ as a subgraph. Recently, Grzesik, Gy\H{o}ri, Salia, Tompkins …
We denote by $\text{ex}(n, H, F)$ the maximum number of copies of $H$ in an $n$-vertex graph that does not contain $F$ as a subgraph. Recently, Grzesik, Gy\H{o}ri, Salia, Tompkins considered conditions on $H$ under which $\text{ex}(n, H, K_r)$ is asymptotically attained at a blow-up of $K_{r-1}$, and proposed a conjecture. In this note we disprove their conjecture.
The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in …
The square $G^2$ of a graph $G$ is the graph on $V(G)$ with a pair of vertices $uv$ an edge whenever $u$ and $v$ have distance $1$ or $2$ in $G$. Given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the minimum $N$ such that whenever the edges of the complete graph $K_N$ are coloured with red and blue, there exists either a red copy of $G$ or a blue copy of $H$. We prove that for all sufficiently large $n$ we have \[R(P_{3n}^2,P_{3n}^2)=R(P_{3n+1}^2,P_{3n+1}^2)=R(C_{3n}^2,C_{3n}^2)=9n-3\mbox{ and } R(P_{3n+2}^2,P_{3n+2}^2)=9n+1.\] We also show that for any $\gamma>0$ and $\Delta$ there exists $\beta>0$ such that the following holds. If $G$ can be coloured with three colours such that all colour classes have size at most $n$, the maximum degree $\Delta(G)$ of $G$ is at most $\Delta$, and $G$ has bandwidth at most $\beta n$, then $R(G,G)\le (3+\gamma)n$.
We prove the statement of the title, thereby solving a $100 problem of Ron Graham. This was solved independently by Tomasz Schoen.
We prove the statement of the title, thereby solving a $100 problem of Ron Graham. This was solved independently by Tomasz Schoen.
A set<italic>S</italic>of integers is said to be sum-free if<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a comma b element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mo>∈<!-- ∈ --></mml:mo><mml:mi>S</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">a,b \in S</mml:annotation></mml:semantics></mml:math></inline-formula>implies<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a plus b not-an-element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mo>∉<!-- …
A set<italic>S</italic>of integers is said to be sum-free if<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a comma b element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>b</mml:mi><mml:mo>∈<!-- ∈ --></mml:mo><mml:mi>S</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">a,b \in S</mml:annotation></mml:semantics></mml:math></inline-formula>implies<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a plus b not-an-element-of upper S"><mml:semantics><mml:mrow><mml:mi>a</mml:mi><mml:mo>+</mml:mo><mml:mi>b</mml:mi><mml:mo>∉<!-- ∉ --></mml:mo><mml:mi>S</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">a + b \notin S</mml:annotation></mml:semantics></mml:math></inline-formula>. In this paper, we investigate two new problems on sum-free sets: (1) Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">f(k)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the largest positive integer for which there exists a partition of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma f left-parenthesis k right-parenthesis EndSet"><mml:semantics><mml:mrow><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…<!-- … --></mml:mo><mml:mo>,</mml:mo><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo fence="false" stretchy="false">}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\{ 1,2, \ldots ,f(k)\}</mml:annotation></mml:semantics></mml:math></inline-formula>into<italic>k</italic>sum-free sets, and let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="h left-parenthesis k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">h(k)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the largest positive integer for which there exists a partition of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma h left-parenthesis k right-parenthesis EndSet"><mml:semantics><mml:mrow><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…<!-- … --></mml:mo><mml:mo>,</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo fence="false" stretchy="false">}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\{ 1,2, \ldots ,h(k)\}</mml:annotation></mml:semantics></mml:math></inline-formula>into<italic>k</italic>sets which are sum-free<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mod h left-parenthesis k right-parenthesis plus 1"><mml:semantics><mml:mrow><mml:mo lspace="thickmathspace" rspace="thickmathspace">mod</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow><mml:annotation encoding="application/x-tex">\bmod h(k) + 1</mml:annotation></mml:semantics></mml:math></inline-formula>. We obtain evidence to support the conjecture that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis k right-parenthesis equals h left-parenthesis k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>f</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>h</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">f(k) = h(k)</mml:annotation></mml:semantics></mml:math></inline-formula>for all<italic>k</italic>. (2) Let<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g left-parenthesis n comma k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">g(n,k)</mml:annotation></mml:semantics></mml:math></inline-formula>denote the cardinality of a largest subset of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma n EndSet"><mml:semantics><mml:mrow><mml:mo fence="false" stretchy="false">{</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo>,</mml:mo><mml:mo>…<!-- … --></mml:mo><mml:mo>,</mml:mo><mml:mi>n</mml:mi><mml:mo fence="false" stretchy="false">}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\{ 1,2, \ldots ,n\}</mml:annotation></mml:semantics></mml:math></inline-formula>that can be partitioned into<italic>k</italic>sum-free sets. We obtain upper and lower bounds for<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g left-parenthesis n comma k right-parenthesis"><mml:semantics><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">g(n,k)</mml:annotation></mml:semantics></mml:math></inline-formula>. We also show that<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="g left-parenthesis n comma 1 right-parenthesis equals left-bracket left-parenthesis n plus 1 right-parenthesis slash 2 right-bracket"><mml:semantics><mml:mrow><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>2</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">g(n,1) = [(n + 1)/2]</mml:annotation></mml:semantics></mml:math></inline-formula>and indicate how one may show that for all<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n less-than-or-slanted-equals 54 comma g left-parenthesis n comma 2 right-parenthesis equals n minus left-bracket n slash 5 right-bracket"><mml:semantics><mml:mrow><mml:mi>n</mml:mi><mml:mo>⩽<!-- ⩽ --></mml:mo><mml:mn>54</mml:mn><mml:mo>,</mml:mo><mml:mi>g</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi><mml:mo>−<!-- − --></mml:mo><mml:mo stretchy="false">[</mml:mo><mml:mi>n</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mn>5</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">n \leqslant 54,g(n,2) = n - [n/5]</mml:annotation></mml:semantics></mml:math></inline-formula>.
Let G be a graph with chromatic number χ and with t being the minimum number of points in any color class of any point-coloring of G with χ colors. …
Let G be a graph with chromatic number χ and with t being the minimum number of points in any color class of any point-coloring of G with χ colors. Let H be any connected graph and let Hn be a graph on n points which is homeomorphic to H. It is proved that if n is large enough, the Ramsey number r(G, Hn) satisfies r(G, Hn) = (χ − l)(n −l) + t. It is also shown that for some G, no such result holds when Hn is a star with n points.
We determine the order of magnitude of H(x, y, z), the number of integers n ≤ x having a divisor in (y, z], for all x, y and z.We also …
We determine the order of magnitude of H(x, y, z), the number of integers n ≤ x having a divisor in (y, z], for all x, y and z.We also study H r (x, y, z), the number of integers n ≤ x having exactly r divisors in (y, z].When r = 1 we establish the order of magnitude of H 1 (x, y, z) for all x, y, z satisfying z ≤ x 1/2-ε .For every r ≥ 2, C > 1 and ε > 0, we determine the order of magnitude of H r (x, y, z) uniformly for y large and y + y/(log y) log 4-1-ε ≤ z ≤ min(y C , x 1/2-ε ).As a consequence of these bounds, we settle a 1960 conjecture of Erdős and some conjectures of Tenenbaum.One key element of the proofs is a new result on the distribution of uniform order statistics.
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has …
The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs that embed into a corresponding system of complete pairs. This lemma has far-reaching applications in extremal combinatorics. We prove sparse analogues of the blow-up lemma for subgraphs of random and of pseudorandom graphs. Our main results are the following three sparse versions of the blow-up lemma: one for embedding spanning graphs with maximum degree $Δ$ in subgraphs of $G(n,p)$ with $p=C(\log n/n)^{1/Δ}$; one for embedding spanning graphs with maximum degree $Δ$ and degeneracy $D$ in subgraphs of $G(n,p)$ with $p=C_Δ\big(\log n/n\big)^{1/(2D+1)}$; and one for embedding spanning graphs with maximum degree $Δ$ in $(p,cp^{\max(4,(3Δ+1)/2)}n)$-bijumbled graphs. We also consider various applications of these lemmas.
Given a dense subset $A$ of the first $n$ positive integers, we provide a short proof showing that for $p=\omega(n^{-2/3}),$ the so-called randomly perturbed set $A \cup [n]_p$ a.a.s. has …
Given a dense subset $A$ of the first $n$ positive integers, we provide a short proof showing that for $p=\omega(n^{-2/3}),$ the so-called randomly perturbed set $A \cup [n]_p$ a.a.s. has the property that any 2-coloring of it has a monochromatic Schur triple, i.e., a triple of the form $(a,b,a+b)$. This result is optimal since there are dense sets $A$, for which $A\cup [n]_p$ does not possess this property for $p=o(n^{-2/3})$.
A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x,y and z with x+y=z. We study the following problem: how many …
A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x,y and z with x+y=z. We study the following problem: how many random integers from [n] need to be added to some A⊆[n] to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when |A|>⌈4n5⌉, no random integers are needed, as A is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers A⊆[n], adding ω(n1/3) random integers suffices, noting that this is optimal for sets A with |A|≤⌈n2⌉. We close the gap between these two results by showing that if A⊆[n] with |A|=⌈n2⌉+t<⌈4n5⌉, then adding ω(min{n1/3,nt−1}) random integers will with high probability result in a set that is Schur. Our result is optimal for all t, and we further provide a stability result showing that one needs far fewer random integers when A is not close in structure to the extremal examples. We also initiate the study of perturbing sparse sets of integers A by using algorithmic arguments and the theory of hypergraph containers to provide nontrivial upper and lower bounds.