Shoham Letzter

An improvement on Łuczak's connected matchings method

A connected matching in a graph $G$ is a matching contained in a connected component of $G$ . A well-known method due to Ł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árfás, Ruszinkó, Sárközy, and Szemerédi (2007).

Hypergraphs with no tight cycles

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.

Immersion of complete digraphs in Eulerian digraphs

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 $Ω(t)$ vertices, thus answering a question of DeVos, Mcdonald, Mohar, and Scheide.

Large rainbow cliques in randomly perturbed dense graphs

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.

Small rainbow cliques in randomly perturbed dense graphs

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.

Fractional triangle decompositions in almost complete graphs

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ős.

Hypergraph Lagrangians I: the Frankl-Füredi conjecture is false

An old and well-known conjecture of Frankl and Fü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}$ .

Lagrangians of Hypergraphs II: When colex is best

A well-known conjecture of Frankl and Fü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.

Minimum degree conditions for monochromatic cycle partitioning

A classical result of Erdős, Gyárfás 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.

Monochromatic triangle packings in red-blue graphs

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ő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.

Orthonormal representations of $H$ -free graphs

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ős and Lovász, are closely related to orthonormal representations of triangle-free graphs, in particular to their Lová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án number of $H$ and the maximum of $\vartheta \left( \overline{G} \right)$ over all $H$ -free graphs $G$ .

preprint2019arXiv

Monochromatic trees in random tournaments

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.

Almost partitioning the hypercube into copies of a graph

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$ .

Eigenvalues of subgraphs of the cube

We consider the problem of maximising the largest eigenvalue of subgraphs of the hypercube $Q_d$ of a given order. We believe that in most cases, Hamming balls are maximisers, and our results support this belief. We show that the Hamming balls of radius $o(d)$ have largest eigenvalue that is within $1 + o(1)$ of the maximum value. We also prove that Hamming balls with fixed radius maximise the largest eigenvalue exactly, rather than asymptotically, when $d$ is sufficiently large. Our proofs rely on the method of compressions.

Minimising the number of triangular edges

We consider the problem of minimising the number of edges that are contained in triangles, among $n$ -vertex graphs with a given number of edges. We prove a conjecture of Füredi and Maleki that gives an exact formula for this minimum, for sufficiently large $n$ .