Search

We consider the problem of constructing a graph of minimum degree $k\ge 1$ in the following controlled random graph process, introduced recently by Frieze, Krivelevich and Michaeli. Suppose the edges of the complete graph on $n$ vertices are permuted uniformly at random. A player, Builder, sees the edges one by one, and must decide irrevocably upon seeing each edge whether to purchase it or not. Suppose Builder purchases an edge if and only if at least one endpoint has degree less than $k$ in her graph. Frieze, Krivelevich and Michaeli observed that this strategy succeeds in building a graph of minimum degree at least $k$ by $\tau_k$, the hitting time for having minimum degree $k$. They conjectured that any strategy using $\epsilon n$ fewer edges, where $\epsilon>0$ is any constant, fails with high probability. In this paper we disprove their conjecture. We show that for $k\ge 2$ Builder has a strategy which purchases $n/9$ fewer edges and succeeds with high probability in building a graph of minimum degree at least $k$ by $\tau_k$. For $k=1$ we show that any strategy using $\epsilon n$ fewer edges fails with probability bounded away from 0, and exhibit such a strategy that succeeds with probability bounded away from 0.

In this survey we aim to give a comprehensive overview of results using sublinear expanders. The term sublinear expanders refers to a variety of definitions of expanders, which typically are defined to be graphs $G$ such that every not-too-small and not-too-large set of vertices $U$ has neighbourhood of size at least $\alpha |U|$, where $\alpha$ is a function of $n$ and $|U|$. This is in contrast with linear expanders, where $\alpha$ is typically a constant. :We will briefly describe proof ideas of some of the results mentioned here, as well as related open problems., Comment: 39 pages, 15 figures. This survey will appear in `Surveys in Combinatorics 2024' (the proceedings of the 30th British Combinatorial Conference)

Let $f^{(r)}(n;s,k)$ be the maximum number of edges in an $n$-vertex $r$-uniform hypergraph not containing a subhypergraph with $k$ edges on at most $s$ vertices. Recently, Delcourt and Postle, building on work of Glock, Joos, Kim, K\"{u}hn, Lichev and Pikhurko, proved that the limit $\lim_{n \to \infty} n^{-2} f^{(3)}(n;k+2,k)$ exists for all $k \ge 2$, solving an old problem of Brown, Erd\H{o}s and S\'{o}s (1973). Meanwhile, Shangguan and Tamo asked the more general question of determining if the limit $\lim_{n \to \infty} n^{-t} f^{(r)}(n;k(r-t)+t,k)$ exists for all $r>t\ge 2$ and $k \ge 2$. Here we make progress on their question. For every even $k$, we determine the value of the limit when $r$ is sufficiently large with respect to $k$ and $t$. Moreover, we show that the limit exists for $k \in \{5,7\}$ and all $r > t \ge 2$., Comment: 14 pages, final version as accepted for publication in Proceedings of the AMS

For a given $\delta \in (0,1)$, the randomly perturbed graph model is defined as the union of any $n$-vertex graph $G_0$ with minimum degree $\delta n$ and the binomial random graph $\mathbf{G}(n,p)$ on the same vertex set. Moreover, we say that a graph is uniformly coloured with colours in $\mathcal{C}$ if each edge is coloured independently and uniformly at random with a colour from $\mathcal{C}$. Based on a coupling idea of McDiarmird, we provide a general tool to tackle problems concerning finding a rainbow copy of a graph $H=H(n)$ in a uniformly coloured perturbed $n$-vertex graph with colours in $[(1+o(1))e(H)]$. For example, our machinery easily allows to recover a result of Aigner-Horev and Hefetz concerning rainbow Hamilton cycles, and to improve a result of Aigner-Horev, Hefetz and Lahiri concerning rainbow bounded-degree spanning trees. Furthermore, using different methods, we prove that for any $\delta \in (0,1)$ and integer $d \ge 2$, there exists $C=C(\delta,d)>0$ such that the following holds. Let $T$ be a tree on $n$ vertices with maximum degree at most $d$ and $G_0$ be an $n$-vertex graph with $\delta(G_0)\ge \delta n$. Then a uniformly coloured $G_0 \cup \mathbf{G}(n,C/n)$ with colours in $[n-1]$ contains a rainbow copy of $T$ with high probability. This is optimal both in terms of colours and edge probability (up to a constant factor)., Comment: 22 pages, 1 figure

A typical theme for many well-known decomposition problems is to show that some obvious necessary conditions for decomposing a graph $G$ into copies $H_1, \ldots, H_m$ are also sufficient. One such problem was posed in 1987, by Alavi, Boals, Chartrand, Erd\H{o}s, and Oellerman. They conjectured that the edges of every graph with $\binom{m+1}2$ edges can be decomposed into subgraphs $H_1, \dots, H_m$ such that each $H_i$ has $i$ edges and is isomorphic to a subgraph of $H_{i+1}$. In this paper we prove this conjecture for sufficiently large $m$.

A well-known result due to Chvat\'al and Erd\H{o}s (1972) asserts that, if a graph $G$ satisfies $\kappa(G) \ge \alpha(G)$, where $\kappa(G)$ is the vertex-connectivity of $G$, then $G$ has a Hamilton cycle. We prove a similar result implying that a graph $G$ is pancyclic, namely it contains cycles of all lengths between $3$ and $|G|$: if $|G|$ is large and $\kappa(G) > \alpha(G)$, then $G$ is pancyclic. This confirms a conjecture of Jackson and Ordaz (1990) for large graphs, and improves upon a very recent result of Dragani\'c, Munh\'a-Correia, and Sudakov., Comment: 32 pages, 11 figures, added two references

For a finite abelian group $A$, define $f(A)$ to be the minimum integer such that for every complete digraph $\Gamma$ on $f$ vertices and every map $w:E(\Gamma) \rightarrow A$, there exists a directed cycle $C$ in $\Gamma$ such that $\sum_{e \in E(C)}w(e) = 0$. The study of $f(A)$ was initiated by Alon and Krivelevich (2021). In this article, we prove that $f(\mathbb{Z}_p^k) = O(pk (\log k)^2)$, where $p$ is prime, with an improved bound of $O(k \log k)$ when $p = 2$. These bounds are tight up to a factor which is polylogarithmic in $k$., Comment: 18 pages (including a 3 page appendix)

We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $\delta \in (0,1)$ there exists $C = C(\delta) > 0$ such that the following holds. Let $D_0$ be an $n$-vertex digraph with minimum semidegree at least $\delta n$ and suppose that each edge of the union of $D_0$ with the random digraph $D(n, p)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup D(n, p)$ has a rainbow directed Hamilton cycle. This improves a result of Aigner-Horev and Hefetz (2021) who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon)n$ colours., Comment: Incorporated referee's comments. Accepted for publication in Combinatorics, Probability and Computing

Given a graph $H$, we say that an edge-coloured graph $G$ is $H$-rainbow saturated if it does not contain a rainbow copy of $H$, but the addition of any non-edge in any colour creates a rainbow copy of $H$. The rainbow saturation number $\text{rsat}(n,H)$ is the minimum number of edges among all $H$-rainbow saturated edge-coloured graphs on $n$ vertices. We prove that for any non-empty graph $H$, the rainbow saturation number is linear in $n$, thus proving a conjecture of Gir\~{a}o, Lewis, and Popielarz. In addition, we also give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Gir\~{a}o, Lewis, and Popielarz., Comment: 16 pages, 2 figures

A separating path system for a graph $G$ is a collection $\mathcal{P}$ of paths in $G$ such that for every two edges $e$ and $f$ in $G$, there is a path in $\mathcal{P}$ that contains $e$ but not $f$. We show that every $n$-vertex graph has a separating path system of size $O(n \log^* n)$. This improves upon the previous best upper bound of $O(n \log n)$, and makes progress towards a conjecture of Falgas-Ravry--Kittipassorn--Kor\'andi--Letzter--Narayanan and Balogh--Csaba--Martin--Pluh\'ar, according to which an $O(n)$ bound should hold., Comment: 36 pages, 2 figures, fixed small errors in section 5

We prove that there exists a constant $c > 0$ such that the vertices of every strongly $c \cdot kt$-connected tournament can be partitioned into $t$ parts, each of which induces a strongly $k$-connected tournament. This is clearly tight up to a constant factor, and it confirms a conjecture of K\"uhn, Osthus and Townsend (2016)., Comment: 24 pages, 2 figures

A common problem in graph colouring seeks to decompose the edge set of a given graph into few similar and simple subgraphs, under certain divisibility conditions. In 1987 Wormald conjectured that the edges of every cubic graph on $4n$ vertices can be partitioned into two isomorphic linear forests. We prove this conjecture for large connected cubic graphs. Our proof uses a wide range of probabilistic tools in conjunction with intricate structural analysis, and introduces a variety of local recolouring techniques., Comment: 49 pages, many figures

The Tur\'an density of an $r$-uniform hypergraph $\mathcal{H}$, denoted $\pi(\mathcal{H})$, is the limit of the maximum density of an $n$-vertex $r$-uniform hypergraph not containing a copy of $\mathcal{H}$, as $n \to \infty$. Denote by $\mathcal{C}_{\ell}$ the $3$-uniform tight cycle on $\ell$ vertices. Mubayi and R\"odl gave an ``iterated blow-up'' construction showing that the Tur\'an density of $\mathcal{C}_5$ is at least $2\sqrt{3} - 3 \approx 0.464$, and this bound is conjectured to be tight. Their construction also does not contain $\mathcal{C}_{\ell}$ for larger $\ell$ not divisible by $3$, which suggests that it might be the extremal construction for these hypergraphs as well. Here, we determine the Tur\'an density of $\mathcal{C}_{\ell}$ for all large $\ell$ not divisible by $3$, showing that indeed $\pi(\mathcal{C}_{\ell}) = 2\sqrt{3} - 3$. To our knowledge, this is the first example of a Tur\'an density being determined where the extremal construction is an iterated blow-up construction. A key component in our proof, which may be of independent interest, is a $3$-uniform analogue of the statement ``a graph is bipartite if and only if it does not contain an odd cycle''., Comment: 34 pages, 4 figures (final version accepted to IMRN plus a few comments in conclusion)

We prove that the family of graphs containing no cycle with exactly $k$-chords is $\chi$-bounded, for $k$ large enough or of form $\ell(\ell-2)$ with $\ell \ge 3$ an integer. This verifies (up to a finite number of values $k$) a conjecture of Aboulker and Bousquet (2015)., Comment: 38 pages, 13 figures

A digraph $G$ \emph{immerses} a digraph $H$ if there is an injection $f : V(H) \to V(G)$ and a collection of pairwise edge-disjoint directed paths $P_{uv}$, for $uv \in E(H)$, such that $P_{uv}$ starts at $u$ and ends at $v$. We prove that every Eulerian digraph with minimum out-degree $t$ immerses a complete digraph on $\Omega(t)$ vertices, thus answering a question of DeVos, Mcdonald, Mohar, and Scheide., Comment: 17 pages; fixed typos

We show that for every integer $m \ge 2$ and large $n$, every properly edge-coloured graph on $n$ vertices with at least $n (\log n)^{53}$ edges contains a rainbow subdivision of $K_m$. This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs., Comment: 22 pages, journal version

We show that every $r$-uniform hypergraph on $n$ vertices which does not contain a tight cycle has at most $O(n^{r-1} (\log n)^5)$ edges. This is an improvement on the previously best-known bound, of $n^{r-1} e^{O(\sqrt{\log n})}$, due to Sudakov and Tomon, and our proof builds up on their work. A recent construction of B. Janzer implies that our bound is tight up to an $O((\log n)^4 \log \log n)$ factor., Comment: 9 pages; corrected typos

The $s$-colour size-Ramsey number of a hypergraph $H$ is the minimum number of edges in a hypergraph $G$ whose every $s$-edge-colouring contains a monochromatic copy of $H$. We show that the $s$-colour size-Ramsey number of the $t$-power of the $r$-uniform tight path on $n$ vertices is linear in $n$, for every fixed $r, s, t$, thus answering a question of Dudek, La Fleur, Mubayi, and R\"odl (2017). In fact, we prove a stronger result that allows us to deduce that powers of bounded degree hypergraph trees and powers of `long subdivisions' of bounded degree hypergraphs have size-Ramsey numbers that are linear in the number of vertices. This extends and strongly generalises recent results about the linearity of size-Ramsey numbers of powers of bounded degree trees and of long subdivisions of bounded degree graphs., Comment: 32 pages (41 including appendix), 6 figures

A connected matching in a graph $G$ is a matching contained in a connected component of $G$. A well-known method due to {\L}uczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic connected matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs. We illustrate the potential of this new reduction by showing how it can be used to determine the $3$-colour Ramsey number of long paths, using a simpler argument than the original one by Gy\'arf\'as, Ruszink\'o, S\'ark\"ozy, and Szemer\'edi (2007)., Comment: 17 pages

We prove that every $n$-vertex graph with at least $\binom{n}{2} - (n - 4)$ edges has a fractional triangle decomposition, for $n \ge 7$. This is a key ingredient in our proof, given in a companion paper, that every $n$-vertex $2$-coloured complete graph contains $n^2/12 + o(n^2)$ edge-disjoint monochromatic triangles, which confirms a conjecture of Erd\H{o}s., Comment: 21 pages

We prove that in every $2$-edge-colouring of $K_n$ there is a collection of $n^2/12 + o(n^2)$ edge-disjoint monochromatic triangles, thus confirming a conjecture of Erd\H{o}s. We also prove a corresponding stability result, showing that $2$-colourings that are close to attaining the aforementioned bound have a colour class which is close to bipartite. As part of our proof, we confirm a recent conjecture of Tyomkyn about the fractional version of this problem., Comment: 31 pages (37 including appendix)

For two graphs $G$ and $H$, write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every \emph{proper} colouring of its edges yields a \emph{rainbow} copy of $H$. We study the thresholds for such so-called \emph{anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$, where $G$ is an $n$-vertex graph with edge-density at least $d >0$, and $d$ is independent of $n$. In a companion article, we proved that the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_\ell$ is $n^{-1/m_2(K_{\left\lceil \ell/2 \right\rceil})}$, whenever $\ell \geq 9$. For smaller $\ell$, the thresholds behave more erratically, and for $4 \le \ell \le 7$ they deviate downwards significantly from the aforementioned aesthetic form capturing the thresholds for \emph{large} cliques. In particular, we show that the thresholds for $\ell \in \{4, 5, 7\}$ are $n^{-5/4}$, $n^{-1}$, and $n^{-7/15}$, respectively. For $\ell \in \{6, 8\}$ we determine the threshold up to a $(1 + o(1))$-factor in the exponent: they are $n^{-(2/3 + o(1))}$ and $n^{-(2/5 + o(1))}$, respectively. For $\ell = 3$, the threshold is $n^{-2}$; this follows from a more general result about odd cycles in our companion paper., Comment: 41 pages, 12 figures; final journal version

For two graphs $G$ and $H$, write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every {\sl proper} colouring of its edges yields a {\sl rainbow} copy of $H$. We study the thresholds for such so-called {\sl anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$, where $G$ is an $n$-vertex graph with edge-density at least $d$, and $d$ is a constant that does not depend on $n$. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_s$ for every $s$. In this paper, we show that for $s \geq 9$ the threshold is $n^{-1/m_2(K_{\left\lceil s/2 \right\rceil})}$; in fact, our $1$-statement is a supersaturation result. This turns out to (almost) be the threshold for $s=8$ as well, but for every $4 \leq s \leq 7$, the threshold is lower; see our companion paper for more details. In this paper, we also consider the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} C_{2\ell - 1}$, and show that the threshold for this property is $n^{-2}$ for every $\ell \geq 2$; in particular, it does not depend on the length of the cycle $C_{2\ell - 1}$. It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all., Comment: This is the journal version

We investigate adaptive sublinear algorithms for detecting monotone patterns in an array. Given fixed $2 \leq k \in \mathbb{N}$ and $\varepsilon > 0$, consider the problem of finding a length-$k$ increasing subsequence in an array $f \colon [n] \to \mathbb{R}$, provided that $f$ is $\varepsilon$-far from free of such subsequences. Recently, it was shown that the non-adaptive query complexity of the above task is $\Theta((\log n)^{\lfloor \log_2 k \rfloor})$. In this work, we break the non-adaptive lower bound, presenting an adaptive algorithm for this problem which makes $O(\log n)$ queries. This is optimal, matching the classical $\Omega(\log n)$ adaptive lower bound by Fischer [2004] for monotonicity testing (which corresponds to the case $k=2$), and implying in particular that the query complexity of testing whether the longest increasing subsequence (LIS) has constant length is $\Theta(\log n)$.

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in \mathbb{N}$ and $\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f \colon [n] \to \mathbb{R}$, assuming that $f$ is $\varepsilon$-far from free of such subsequences, is $\Theta((\log n)^{\lfloor \log_2 k \rfloor})$. Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made $(\log n)^{O(k^2)}$ non-adaptive queries; and the only lower bound known, of $\Omega(\log n)$ queries for the case $k = 2$, followed from that on testing monotonicity due to Erg\"un, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).

A well-known conjecture of Frankl and F\"{u}redi from 1989 states that an initial segment of colex of has the largest Lagrangian of any $r$-uniform hypergraph with $m$ hyperedges. We show that this is true when $r=3$. We also give a new proof of a related conjecture of Nikiforov and a counterexample to an old conjecture of Ahlswede and Katona., Comment: We split our original paper (arXiv:1807.00793v2) into two parts. The first part can be found in arXiv:1807.00793. This is the second part, which consists of 18 pages, including a two-page appendix

Given a hypergraph $H$, the size-Ramsey number $\hat{r}_2(H)$ is the smallest integer $m$ such that there exists a graph $G$ with $m$ edges with the property that in any colouring of the edges of $G$ with two colours there is a monochromatic copy of $H$. We prove that the size-Ramsey number of the $3$-uniform tight path on $n$ vertices $P^{(3)}_n$ is linear in $n$, i.e., $\hat{r}_2(P^{(3)}_n) = O(n)$. This answers a question by Dudek, Fleur, Mubayi, and R\"odl for $3$-uniform hypergraphs [On the size-Ramsey number of hypergraphs, J. Graph Theory 86 (2016), 417-434], who proved $\hat{r}_2(P^{(3)}_n) = O(n^{3/2} \log^{3/2} n)$., Comment: 12 pages,1 figure

Let $x_1, \ldots, x_n \in \mathbb{R}^d$ be unit vectors such that among any three there is an orthogonal pair. How large can $n$ be as a function of $d$, and how large can the length of $x_1 + \ldots + x_n$ be? The answers to these two celebrated questions, asked by Erd\H{o}s and Lov\'{a}sz, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lov\'{a}sz $\vartheta$-function and minimum semidefinite rank. In this paper, we study these parameters for general $H$-free graphs. In particular, we show that for certain bipartite graphs $H$, there is a connection between the Tur\'{a}n number of $H$ and the maximum of $\vartheta \left( \overline{G} \right)$ over all $H$-free graphs $G$., Comment: 16 pages

A classical result of Erd\H{o}s, Gy\'arf\'as and Pyber states that any $r$-edge-coloured complete graph has a partition into $O(r^2 \log r)$ monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant $c$ such that any $r$-edge-coloured graph on $n$ vertices with minimum degree at least $n/2 + c \cdot r \log n$ has a partition into $O(r^2)$ monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight., Comment: 22 pages (26 including appendix)

The $k$-colour bipartite Ramsey number of a bipartite graph $H$ is the least integer $N$ for which every $k$-edge-coloured complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. The study of bipartite Ramsey numbers was initiated over 40 years ago by Faudree and Schelp and, independently, by Gy\'arf\'as and Lehel, who determined the $2$-colour bipartite Ramsey number of paths. Recently the $3$-colour Ramsey number of paths and (even) cycles, was essentially determined as well. Improving the results of DeBiasio, Gy\'arf\'as, Krueger, Ruszink\'o, and S\'ark\"ozy, in this paper we determine asymptotically the $4$-colour bipartite Ramsey number of paths and cycles. We also provide new upper bounds on the $k$-colour bipartite Ramsey numbers of paths and cycles which are close to being tight., Comment: 14 pages, 2 figures

In this paper, we study product-free subsets of the free semigroup over a finite alphabet $A$. We prove that the maximum density of a product-free subset of the free semigroup over $A$, with respect to the natural measure that assigns a weight of $|A|^{-n}$ to each word of length $n$, is precisely $1/2$., Comment: 8 pages, submitted

For graphs $H$ and $F$, let $\operatorname{ex}(n, H, F)$ be the maximum possible number of copies of $H$ in an $F$-free graph on $n$ vertices. The study of this function, which generalises the well-studied Tur\'an numbers of graphs, was initiated recently by Alon and Shikhelman. We show that if $F$ is a tree then $\operatorname{ex}(n, H, F) = \Theta(n^r)$ for some integer $r = r(H, F)$, thus answering one of their questions., Comment: 9 pages, 1 figure

The problem of finding dense induced bipartite subgraphs in $H$-free graphs has a long history, and was posed 30 years ago by Erd\H{o}s, Faudree, Pach and Spencer. In this paper, we obtain several results in this direction. First we prove that any $K_t$-free graph with minimum degree at least $d$ contains an induced bipartite subgraph of minimum degree at least $c_t \log d/\log \log d$, confirming (asymptotically) several conjectures by Esperet, Kang and Thomass\'e. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erd\H{o}s, Janson, {\L}uczak and Spencer., Comment: 17 pages, final version to appear in Combinatorica

We prove that, with high probability, in every $2$-edge-colouring of the random tournament on $n$ vertices there is a monochromatic copy of every oriented tree of order $O (n / \sqrt{\log n})$. This generalises a result of the first, third and forth authors who proved the same statement for paths, and is tight up to a constant factor., Comment: 31 pages, 6 figures

Magnant and Martin conjectured that the vertex set of any $d$-regular graph $G$ on $n$ vertices can be partitioned into $n / (d+1)$ paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when $d = \Omega(n)$, improving a result of Han, who showed that in this range almost all vertices of $G$ can be covered by $n / (d+1) + 1$ vertex-disjoint paths. In fact, our proof gives a partition of $V(G)$ into cycles. We also show that, if $d = \Omega(n)$ and $G$ is bipartite, then $V(G)$ can be partitioned into $n / (2d)$ paths (this bound in tight for bipartite graphs)., Comment: 31 pages, 1 figure

An old and well-known conjecture of Frankl and F\"{u}redi states that the Lagrangian of an $r$-uniform hypergraph with $m$ edges is maximised by an initial segment of colex. In this paper we disprove this conjecture by finding an infinite family of counterexamples for all $r \ge 4$. We also show that, for sufficiently large $t \in \mathbb{N}$, the conjecture is true in the range $\binom{t}{r} \le m \le \binom{t+1}{r} - \binom{t-1}{r-2}$., Comment: We split our original paper (arXiv:1807.00793v2) into two parts. This first part consists of 24 pages, including a one-page appendix. The second part appears in a new submission (arXiv:1907.09797)

The $k$-colour bipartite Ramsey number of a bipartite graph $H$ is the least integer $n$ for which every $k$-edge-coloured complete bipartite graph $K_{n,n}$ contains a monochromatic copy of $H$. The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gy\'arf\'as and Lehel, who determined the $2$-colour Ramsey number of paths. In this paper we determine asymptotically the $3$-colour bipartite Ramsey number of paths and (even) cycles., Comment: 15 pages, 3 figures

We call a family $\mathcal{F}$ of subsets of $[n]$ $s$-saturated if it contains no $s$ pairwise disjoint sets, and moreover no set can be added to $\mathcal{F}$ while preserving this property (here $[n] = \{1,\ldots,n\}$). More than 40 years ago, Erd\H{o}s and Kleitman conjectured that an $s$-saturated family of subsets of $[n]$ has size at least $(1 - 2^{-(s-1)})2^n$. It is easy to show that every $s$-saturated family has size at least $\frac{1}{2}\cdot 2^n$, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of $(1/2 + \varepsilon)2^n$, for some fixed $\varepsilon > 0$, seems difficult. In this note, we prove such a result, showing that every $s$-saturated family of subsets of $[n]$ has size at least $(1 - 1/s)2^n$. This lower bound is a consequence of a multipartite version of the problem, in which we seek a lower bound on $|\mathcal{F}_1| + \ldots + |\mathcal{F}_s|$ where $\mathcal{F}_1, \ldots, \mathcal{F}_s$ are families of subsets of $[n]$, such that there are no $s$ pairwise disjoint sets, one from each family $\mathcal{F}_i$, and furthermore no set can be added to any of the families while preserving this property. We show that $|\mathcal{F}_1| + \ldots + |\mathcal{F}_s| \ge (s-1)\cdot 2^n$, which is tight e.g.\ by taking $\mathcal{F}_1$ to be empty, and letting the remaining families be the families of all subsets of $[n]$., Comment: 8 pages

An oriented graph is a directed graph with no bi-directed edges, i.e. if $xy$ is an edge then $yx$ is not an edge. The oriented size Ramsey number of an oriented graph $H$, denoted by $r(H)$, is the minimum $m$ for which there exists an oriented graph $G$ with $m$ edges, such that every $2$-colouring of $G$ contains a monochromatic copy of $H$. In this paper we prove that the oriented size Ramsey number of the directed paths on $n$ vertices satisfies $r(P_n) = \Omega(n^2 \log n)$. This improves a lower bound by Ben-Eliezer, Krivelevich and Sudakov. It also matches an upper bound by Buci\'c and the authors, thus establishing an asymptotically tight bound on $r(P_n)$. We also discuss how our methods can be used to improve the best known lower bound of the $k$-colour version of $r(P_n)$., Comment: 6 pages

For a positive integer $k$, we say that a graph is $k$-existentially complete if for every $0 \leq a \leq k$, and every tuple of distinct vertices $x_1,\ldots,x_a$, $y_1,\ldots,y_{k-a}$, there exists a vertex $z$ that is joined to all of the vertices $x_1,\ldots,x_a$ and none of the vertices $y_1,\ldots,y_{k-a}$. While it is easy to show that the binomial random graph $G_{n,1/2}$ satisfies this property with high probability for $k \sim c\log n$, little is known about the "triangle-free" version of this problem; does there exist a finite triangle-free graph $G$ with a similar "extension property". This question was first raised by Cherlin in 1993 and remains open even in the case $k=4$. We show that there are no $k$-existentially complete triangle-free graphs with $k >\frac{8\log n}{\log\log n}$, thus giving the first non-trivial, non-existence result on this "old chestnut" of Cherlin. We believe that this result breaks through a natural barrier in our understanding of the problem.

In this paper, we study Ramsey-type problems for directed graphs. We first consider the $k$-colour oriented Ramsey number of $H$, denoted by $\overrightarrow{R}(H,k)$, which is the least $n$ for which every $k$-edge-coloured tournament on $n$ vertices contains a monochromatic copy of $H$. We prove that $ \overrightarrow{R}(T,k) \le c_k|T|^k$ for any oriented tree $T$. This is a generalisation of a similar result for directed paths by Chv\'atal and by Gy\'arf\'as and Lehel, and answers a question of Yuster. In general, it is tight up to a constant factor. We also consider the $k$-colour directed Ramsey number $\overleftrightarrow{R}(H,k)$ of $H$, which is defined as above, but, instead of colouring tournaments, we colour the complete directed graph of order $n$. Here we show that $ \overleftrightarrow{R}(T,k) \le c_k|T|^{k-1}$ for any oriented tree $T$, which is again tight up to a constant factor, and it generalises a result by Williamson and by Gy\'arf\'as and Lehel who determined the $2$-colour directed Ramsey number of directed paths., Comment: 27 pages, 14 figures

A well-known result by Haxell and Kohayakawa states that the vertices of an $r$-coloured complete graph can be partitioned into $r$ monochromatic connected subgraphs of distinct colours; this is a slightly weaker variant of a conjecture by Erd\H{o}s, Pyber and Gy\'arf\'as that states that there exists a partition into $r-1$ monochromatic connected subgraphs. We consider a variant of this problem, where the complete graph is replaced by a graph with large minimum degree, and prove two conjectures of Bal and DeBiasio, for two and three colours., Comment: 14 pages, 2 figures

We prove that, with high probability, any $2$-edge-colouring of a random tournament on $n$ vertices contains a monochromatic path of length $\Omega(n / \sqrt{\log n})$. This resolves a conjecture of Ben-Eliezer, Krivelevich and Sudakov and implies a nearly tight upper bound on the oriented size Ramsey number of a directed path.

Let $H$ be an induced subgraph of the hypercube $Q_k$, for some $k$. We show that for some $c = c(H)$, the vertices of $Q_n$ can be partitioned into induced copies of $H$ and a remainder of at most $O(n^c)$ vertices. We also show that the error term cannot be replaced by anything smaller than $\log n$., Comment: 13 pages, 1 figure