Search

We construct a set of $2^n$ points in $\mathbb{R}^n$ such that all pairwise Manhattan distances are odd integers, which improves the recent linear lower bound of Golovanov, Kupavskii and Sagdeev. In contrast to the Euclidean and maximum metrics, this shows that the odd-distance set problem behaves very differently to the equilateral set problem under the Manhattan metric. Moreover, all coordinates of the points in our construction are integers or half-integers, and we show that our construction is optimal under this additional restriction., Comment: 6 pages

We show that a $k$-uniform hypergraph on $n$ vertices has a spanning subgraph homeomorphic to the $(k - 1)$-dimensional sphere provided that $H$ has no isolated vertices and each set of $k - 1$ vertices supported by an edge is contained in at least $n/2 + o(n)$ edges. This gives a topological extension of Dirac's theorem and asymptotically confirms a conjecture of Georgakopoulos, Haslegrave, Montgomery, and Narayanan. Unlike typical results in the area, our proof does not rely on the Absorption Method, the Regularity Lemma or the Blow-up Lemma. Instead, we use a recently introduced framework that is based on covering the vertex set of the host graph with a family of complete blow-ups., Comment: 20 pages

The $c$-strong chromatic number of a hypergraph is the smallest number of colours needed to colour its vertices so that every edge sees at least $c$ colours or is rainbow. We show that every $t$-intersecting hypergraph has bounded $(t + 1)$-strong chromatic number, resolving a problem of Blais, Weinstein and Yoshida. In fact, we characterise when a $t$-intersecting hypergraph has large $c$-strong chromatic number for $c\geq t+2$. Our characterisation also applies to hypergraphs which exclude sunflowers with specified parameters., Comment: 13 pages

A $\textit{dominating $K_t$-model}$ in a graph $G$ is a sequence $(T_1,\dots,T_t)$ of pairwise disjoint non-empty connected subgraphs of $G$, such that for $1 \leqslant i

We disprove the conjecture of Georgakopoulos and Papasoglu that a length space (or graph) with no $K$-fat $H$ minor is quasi-isometric to a graph with no $H$ minor. Our counterexample is furthermore not quasi-isometric to a graph with no 2-fat $H$ minor or a length space with no $H$ minor. On the other hand, we show that the following weakening holds: any graph with no $K$-fat $H$ minor is quasi-isometric to a graph with no $3$-fat $H$ minor., Comment: 14 pages, 5 figures

A multigraph drawn in the plane is non-homotopic if no two edges connecting the same pair of vertices can be continuously deformed into each other without passing through a vertex, and is $k$-crossing if every pair of edges (self-)intersects at most $k$ times. We prove that the number of edges in an $n$-vertex non-homotopic $k$-crossing multigraph is at most $6^{13 n (k + 1)}$, which is a big improvement over previous upper bounds. We also study this problem in the setting of monotone drawings where every edge is an x-monotone curve. We show that the number of edges, $m$, in such a drawing is at most $2 \binom{2n}{k + 1}$ and the number of crossings is $\Omega\bigl(\frac{m^{2 + 1/k}}{n^{1 + 1/k}}\bigr)$. For fixed $k$ these bounds are both best possible up to a constant multiplicative factor., Comment: 19 pages

We prove that a large family of pairs of graphs satisfy a polynomial dependence in asymmetric graph removal lemmas. In particular, we give an unexpected answer to a question of Gishboliner, Shapira, and Wigderson by showing that for every $t \geqslant 4$, there are $K_t$-abundant graphs of chromatic number $t$. Using similar methods, we also extend work of Ruzsa by proving that a set $\mathcal{A} \subset \{1,\dots,N\}$ which avoids solutions with distinct integers to an equation of genus at least two has size $\mathcal{O}(\sqrt{N})$. The best previous bound was $N^{1 - o(1)}$ and the exponent of $1/2$ is best possible in such a result. Finally, we investigate the relationship between polynomial dependencies in asymmetric removal lemmas and the problem of avoiding integer solutions to equations. The results suggest a potentially deep correspondence. Many open questions remain., Comment: 28 pages, 4 figures

Scott and Seymour conjectured the existence of a function $f \colon \mathbb{N} \to \mathbb{N}$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $\chi(G) \geqslant f(k)$ implies that $\chi(G[N_T^+(v)]) \geqslant k$ for some vertex $v$. In this note we disprove this conjecture even if $v$ is replaced by a vertex set of size $\mathcal{O}(\log{\lvert V(G)\rvert})$. As a consequence, we answer in the negative a question of Harutyunyan, Le, Thomass\'{e}, and Wu concerning the corresponding statement where the graph $G$ is replaced by another tournament, and disprove a related conjecture of Nguyen, Scott, and Seymour. We also show that the setting where chromatic number is replaced by degeneracy exhibits a quite different behaviour., Comment: 7 pages; funding information added

Colour the edges of the complete graph with vertex set $\{1, 2, \dotsc, n\}$ with an arbitrary number of colours. What is the smallest integer $f(l,k)$ such that if $n > f(l,k)$ then there must exist a monotone monochromatic path of length $l$ or a monotone rainbow path of length $k$? Lefmann, R\"{o}dl, and Thomas conjectured in 1992 that $f(l, k) = l^{k - 1}$ and proved this for $l \ge (3 k)^{2 k}$. We prove the conjecture for $l \geq k^3 (\log k)^{1 + o(1)}$ and establish the general upper bound $f(l, k) \leq k (\log k)^{1 + o(1)} \cdot l^{k - 1}$. This reduces the gap between the best lower and upper bounds from exponential to polynomial in $k$. We also generalise some of these results to the tournament setting., Comment: 14 pages, improved Theorem 1.3 slightly

The free semigroup $\mathcal{F}$ over a finite alphabet $\mathcal{A}$ is the set of all finite words with letters from $\mathcal{A}$ equipped with the operation of concatenation. A subset $S$ of $\mathcal{F}$ is $k$-product-free if no element of $S$ can be obtained by concatenating $k$ words from $S$, and strongly $k$-product-free if no element of $S$ is a (non-trivial) concatenation of at most $k$ words from $S$. We prove that a $k$-product-free subset of $\mathcal{F}$ has upper Banach density at most $1/\rho(k)$, where $\rho(k) = \min\{\ell \colon \ell \nmid k - 1\}$. We also determine the structure of the extremal $k$-product-free subsets for all $k \notin \{3, 5, 7, 13\}$; a special case of this proves a conjecture of Leader, Letzter, Narayanan, and Walters. We further determine the structure of all strongly $k$-product-free sets with maximum density. Finally, we prove that $k$-product-free subsets of the free group have upper Banach density at most $1/\rho(k)$, which confirms a conjecture of Ortega, Ru\'{e}, and Serra., Comment: 31 pages, added density results for the free group

In 2019, Dvo\v{r}\'{a}k asked whether every connected graph $G$ has a tree decomposition $(T, \mathcal{B})$ so that $T$ is a subgraph of $G$ and the width of $(T, \mathcal{B})$ is bounded by a function of the treewidth of $G$. We prove that this is false, even when $G$ has treewidth $2$ and $T$ is allowed to be a minor of $G$., Comment: 10 pages, 2 figures

Let $V$ be a set of $n$ points on the real line. Suppose that each pairwise distance is known independently with probability $p$. How much of $V$ can be reconstructed up to isometry? We prove that $p = (\log n)/n$ is a sharp threshold for reconstructing all of $V$ which improves a result of Benjamini and Tzalik. This follows from a hitting time result for the random process where the pairwise distances are revealed one-by-one uniformly at random. We also show that $1/n$ is a weak threshold for reconstructing a linear proportion of $V$., Comment: 13 pages

A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects'. Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs, and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. Using the same tools, we also study the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, we show that if the crossing graph is $K_t$-minor-free, then $G$ has treewidth at most $12t-23$ and has no $K_{2,4t}$-topological minor. On the other hand, we show that there are graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate.

In 2017, Ron Aharoni made the following conjecture about rainbow cycles in edge-coloured graphs: If $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{r} \rceil$. One motivation for studying Aharoni's conjecture is that it is a strengthening of the Caccetta-H\"aggkvist conjecture on digraphs from 1978. In this article, we present a survey of Aharoni's conjecture, including many recent partial results and related conjectures. We also present two new results. Our main new result is for the $r=3$ case of Aharoni's conjecture. We prove that if $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least 3, then $G$ contains a rainbow cycle of length at most $\frac{4n}{9}+7$. We also discuss how our approach might generalise to larger values of $r$., Comment: 12 pages, 0 figures. Minor changes. Also added an exact result for the 3 colour case of Question 2.5

We prove that the vertices of every $(r + 1)$-uniform hypergraph with maximum degree $\Delta$ may be coloured with $c(\frac{\Delta}{d + 1})^{1/r}$ colours such that each vertex is in at most $d$ monochromatic edges. This result, which is best possible up to the value of the constant $c$, generalises the classical result of Erd\H{o}s and Lov\'asz who proved the $d = 0$ case., Comment: 11 pages; revised argument in section 2.2, results unchanged

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$, for every graph ${G \in \mathcal{G}}$ there is a graph $H$ with ${\text{tw}(H) \leq c}$ such that $G$ is isomorphic to a subgraph of ${H \boxtimes K_{f(\text{tw}(G))}}$. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of $K_{s,t}$-minor-free graphs has underlying treewidth $s$ (for ${t \geq \max\{s,3\}}$); and the class of $K_t$-minor-free graphs has underlying treewidth ${t-2}$. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.

We show that the edges of any graph $G$ containing two edge-disjoint spanning trees can be blue/red coloured so that the blue and red graphs are connected and the blue and red degrees at each vertex differ by at most four. This improves a result of H\"orsch. We discuss variations of the question for digraphs, infinite graphs and a computational question, and resolve two further questions of H\"orsch in the negative., Comment: 23 pages, 22 figures

We prove that, for every graph $F$ with at least one edge, there is a constant $c_F$ such that there are graphs of arbitrarily large chromatic number and the same clique number as $F$ in which every $F$-free induced subgraph has chromatic number at most $c_F$. This generalises recent theorems of Bria\'{n}ski, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every $r\geq 3$ the class of $K_r$-free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth., Comment: 26 pages; v4: final version incorporating the suggestions of referees and Jarik Ne\v{s}et\v{r}il, including simplified constructions and a new open question

In 1967, Erd\H{o}s asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of Erd\H{o}s and Hajnal together with Shearer's classical upper bound for the off-diagonal Ramsey number $R(3, t)$ shows that $f(n)$ is at most $(2 \sqrt{2} + o(1)) \sqrt{n/\log n}$. We improve this bound by a factor $\sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot., Comment: 13 pages. This version contains minor revisions and a bound in terms of genus that follows from our main results

Loh, Tait, Timmons and Zhou introduced the notion of induced Tur\'{a}n numbers, defining $\operatorname{ex}(n, \{H, F\text{-ind}\})$ to be the greatest number of edges in an $n$-vertex graph with no copy of $H$ and no induced copy of $F$. Their and subsequent work has focussed on $F$ being a complete bipartite graph. In this short note, we complement this focus by asymptotically determining the induced Tur\'{a}n number whenever $H$ is not bipartite and $F$ is not an independent set nor a complete bipartite graph., Comment: 2 pages

This paper shows that $K_t$-minor-free (and $K_{s, t}$-minor-free) graphs $G$ are subgraphs of products of a tree-like graph $H$ (of bounded treewidth) and a complete graph $K_m$. Our results include optimal bounds on the treewidth of $H$ and optimal bounds (to within a constant factor) on $m$ in terms of the number of vertices of $G$ and the treewidth of $G$. These results follow from a more general theorem whose corollaries include a strengthening of the celebrated separator theorem of Alon, Seymour, and Thomas [J. Amer. Math. Soc. 1990] and the Planar Graph Product Structure Theorem of Dujmovi\'c et al. [J. ACM 2020]., Comment: Main results are not in v1. Theorem 4 is new in v3. v5 is a major update, now with a proof of the Planar Graph Product Structure Theorem. v6 includes applications to p-centred colouring and appendix on simple treewidth

Given an $(r + 1)$-chromatic graph $H$, the fundamental edge stability result of Erd\H{o}s and Simonovits says that all $n$-vertex $H$-free graphs have at most $(1 - 1/r + o(1)) \binom{n}{2}$ edges, and any $H$-free graph with that many edges can be made $r$-partite by deleting $o(n^{2})$ edges. Here we consider a natural variant of this -- the minimum degree stability of $H$-free graphs. In particular, what is the least $c$ such that any $n$-vertex $H$-free graph with minimum degree greater than $cn$ can be made $r$-partite by deleting $o(n^{2})$ edges? We determine this least value for all 3-chromatic $H$ and for very many non-3-colourable $H$ (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andr\'{a}sfai-Erd\H{o}s-S\'{o}s theorem and work of Alon and Sudakov., Comment: 16 pages, 2 figures. Final version, concluding remarks and open question added

The classical Andr\'{a}sfai-Erd\H{o}s-S\'{o}s theorem considers the chromatic number of $K_{r + 1}$-free graphs with large minimum degree, and in the case $r = 2$ says that any $n$-vertex triangle-free graph with minimum degree greater than $2/5 \cdot n$ is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each $k$, what minimum degree guarantees that a triangle-free graph is $k$-colourable? The profile has been extensively studied and was finally determined by Brandt and Thomass\'{e}. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, \L uczak and Thomass\'{e} introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is $b$-colourable (locally $b$-partite graphs) as well as the family where the common neighbourhood of every $a$-clique is $b$-colourable. Our results include the chromatic thresholds of these families as well as showing that every $n$-vertex locally $b$-partite graph with minimum degree greater than $(1 - 1/(b + 1/7)) \cdot n$ is $(b + 1)$-colourable. Understanding these locally colourable graphs is crucial for extending the Andr\'{a}sfai-Erd\H{o}s-S\'{o}s theorem to non-complete graphs, which we develop elsewhere., Comment: 34 pages, 18 figures. Final version. arXiv admin note: text overlap with arXiv:2012.10409

In 1973, Erd\H{o}s and Simonovits asked whether every $n$-vertex triangle-free graph with minimum degree greater than $1/3 \cdot n$ is 3-colourable. This question initiated the study of the chromatic profile of triangle-free graphs: for each $k$, what minimum degree guarantees that a triangle-free graph is $k$-colourable. This problem has a rich history which culminated in its complete solution by Brandt and Thomass\'{e}. Much less is known about the chromatic profile of $H$-free graphs for general $H$. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. Locally bipartite graphs, first mentioned by Luczak and Thomass\'{e}, are the natural variant of triangle-free graphs in which each neighbourhood is bipartite. Here we study the chromatic profile of locally bipartite graphs. We show that every $n$-vertex locally bipartite graph with minimum degree greater than $4/7 \cdot n$ is 3-colourable ($4/7$ is tight) and with minimum degree greater than $6/11 \cdot n$ is 4-colourable. Although the chromatic profiles of locally bipartite and triangle-free graphs bear some similarities, we will see there are striking differences., Comment: 35 pages, 29 figures. Final version

Consider a graph $G$ on $n$ vertices with $\alpha \binom{n}{2}$ edges which does not contain an induced $K_{2, t}$ ($t \geqslant 2$). How large does $\alpha$ have to be to ensure that $G$ contains, say, a large clique or some fixed subgraph $H$? We give results for two regimes: for $\alpha$ bounded away from zero and for $\alpha = o(1)$. Our results for $\alpha = o(1)$ are strongly related to the Induced Tur\'{a}n numbers which were recently introduced by Loh, Tait, Timmons and Zhou. For $\alpha$ bounded away from zero, our results can be seen as a generalisation of a result of Gy\'{a}rf\'{a}s, Hubenko and Solymosi and more recently Holmsen (whose argument inspired ours)., Comment: 8 pages; final version incorporating changes suggested by referees; new result in last section