Search

The families $\mathcal F_0,\ldots,\mathcal F_s$ of $k$-element subsets of $[n]:=\{1,2,\ldots,n\}$ are called cross-union if there is no choice of $F_0\in \mathcal F_0, \ldots, F_s\in \mathcal F_s$ such that $F_0\cup\ldots\cup F_s=[n]$. A natural generalization of the celebrated Erd\H{o}s--Ko--Rado theorem, due to Frankl and Tokushige, states that for $n\le (s+1)k$ the geometric mean of $\lvert \mathcal F_i\rvert$ is at most $\binom{n-1}{k}$. Frankl conjectured that the same should hold for the arithmetic mean under some mild conditions. We prove Frankl's conjecture in a strong form by showing that the unique (up to isomorphism) maximizer for the arithmetic mean of cross-union families is the natural one $\mathcal F_0=\ldots=\mathcal F_s={[n-1]\choose k}$., Comment: 14 pages, 1 figure Accepted at Combinatorial Theory

We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, and (iii) a certain random variable on the boundary of a ball has a small tail. As applications, we show that the volume of intersection of balls in Hamming, Johnson spaces and symmetric groups decay exponentially as their centers drift apart. To verify condition (iii), we prove some large deviation inequalities `on a slice' for functions with Lipschitz conditions. We then use these estimates on intersection volumes to $\bullet$ obtain a sharp lower bound on list-decodability of random $q$-ary codes, confirming a conjecture of Li and Wootters; and $\bullet$ improve the classical bound of Levenshtein from 1971 on constant weight codes by a factor linear in dimension, resolving a problem raised by Jiang and Vardy. Our probabilistic point of view also offers a unified framework to obtain improvements on other Gilbert--Varshamov type bounds, giving conceptually simple and calculation-free proofs for $q$-ary codes, permutation codes, and spherical codes. Another consequence is a counting result on the number of codes, showing ampleness of large codes., Comment: 25 pages

The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$, provided $n$ is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n,H)=(n-1)(\chi(H)-1)+\sigma(H)$, where $\sigma(H)$ is the minimum possible size of a colour class in a $\chi(H)$-colouring of $H$. Allen, Brightwell and Skokan conjectured that the same should be true already when $n\geq |H|\chi(H)$. We improve this 40-year-old result of Burr by giving quantitative bounds of the form $n\geq C|H|\log^4\chi(H)$, which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number., Comment: 20 pages, 3 figures. Final version to appear in Forum of Mathematics, Sigma

The following question was proposed by Nenadov and Pehova and reiterated by Knierim and Su: Given integers $\ell,r$ and $n$ with $n\in r\mathbb{N}$, is it true that every $n$-vertex graph $G$ with $\delta(G) \ge \max \{ \frac{1}{2},\frac{r - \ell}{r} \}n + o(n)$ and $\alpha_{\ell}(G) = o(n) $ contains a $K_{r}$-factor? We give a negative answer for the case when $\ell\ge \frac{3r}{4}$ by giving a family of constructions using the so-called cover thresholds and show that the minimum degree condition given by our construction is asymptotically best possible. That is, for all integers $r,\ell$ with $r > \ell \ge \frac{3}{4}r$ and $\mu >0$, there exist $\alpha > 0$ and $N$ such that for every $n\in r\mathbb{N}$ with $n>N$, every $n$-vertex graph $G$ with $\delta(G) \ge \left( \frac{1}{2-\varrho_{\ell}(r-1)} + \mu \right)n $ and $\alpha_{\ell}(G) \le \alpha n$ contains a $K_{r}$-factor. Here $\varrho_{\ell}(r-1)$ is the Ramsey--Tur\'an density for $K_{r-1}$ under the $\ell$-independence number condition., Comment: 23 pages,2 figures

Let the kissing number $K(d)$ be the maximum number of non-overlapping unit balls in $\mathbb R^d$ that can touch a given unit ball. Determining or estimating the number $K(d)$ has a long history, with the value of $K(3)$ being the subject of a famous discussion between Gregory and Newton in 1694. We prove that, as the dimension $d$ goes to infinity, $$ K(d)\ge (1+o(1)){\frac{\sqrt{3\pi}}{4\sqrt2}}\,\log\frac{3}{2}\cdot d^{3/2}\cdot \Big(\frac{2}{\sqrt{3}}\Big)^{d}, $$ thus improving the previously best known bound of Jenssen, Joos and Perkins by a factor of $\log(3/2)/\log(9/8)+o(1)=3.442...$. Our proof is based on the novel approach from Jenssen, Joos and Perkins that uses the hard core sphere model of an appropriate fugacity. Similar constant-factor improvements in lower bounds are also obtained for general spherical codes, as well as for the expected density of random sphere packings in the Euclidean space $\mathbb R^d$., Comment: 20 pages

The oriented Ramsey number $\vec{r}(H)$ for an acyclic digraph $H$ is the minimum integer $n$ such that any $n$-vertex tournament contains a copy of $H$ as a subgraph. We prove that the $1$-subdivision of the $k$-vertex transitive tournament $H_k$ satisfies $\vec{r}(H_k)= O(k^2\log\log k)$. This is tight up to multiplicative $\log\log k$-term. We also show that if $T$ is an $n$-vertex tournament with $\Delta^+(T)-\delta^+(T)= O(n/k) - k^2$, then $T$ contains a $1$-subdivision of $\vec{K}_k$, a complete $k$-vertex digraph with all possible $k(k-1)$ arcs. This is also tight up to multiplicative constant.

Suppose a $k$-uniform hypergraph $H$ that satisfies a certain regularity instance (that is, there is a partition of $H$ given by the hypergraph regularity lemma into a bounded number of quasirandom subhypergraphs of prescribed densities). We prove that with high probability a large enough uniform random sample of the vertex set of $H$ also admits the same regularity instance. Here the crucial feature is that the error term measuring the quasirandomness of the subhypergraphs requires only an arbitrarily small additive correction. This has applications to combinatorial property testing. The graph case of the sampling result was proved by Alon, Fischer, Newman and Shapira., Comment: 49 pages; we split our paper arXiv:1707.03303 into two, this one and the new version of arXiv:1707.03303. Final version, to appear in Random Structures and Algorithms

A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected $2$-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem.

We study regular graphs in which the random walks starting from a positive fraction of vertices have small mixing time. We prove that any such graph is virtually an expander and has no small separator. This answers a question of Pak [SODA, 2002]. As a corollary, it shows that sparse (constant degree) regular graphs with many well-mixing vertices have a long cycle, improving a result of Pak. Furthermore, such cycle can be found in polynomial time. Secondly, we show that if the random walks from a positive fraction of vertices are well-mixing, then the random walks from almost all vertices are well-mixing (with a slightly worse mixing time)., Comment: accepted in PAMS

Helly's theorem and its variants show that for a family of convex sets in Euclidean space, local intersection patterns influence global intersection patterns. A classical result of Eckhoff in 1988 provided an optimal fractional Helly theorem for axis-aligned boxes, which are Cartesian products of line segments. Answering a question raised by B\'ar\'any and Kalai, and independently Lew, we generalize Eckhoff's result to Cartesian products of convex sets in all dimensions. In particular, we prove that given $\alpha \in (1-\frac{1}{t^d},1]$ and a finite family $\mathcal{F}$ of Cartesian products of convex sets $\prod_{i\in[t]}A_i$ in $\mathbb{R}^{td}$ with $A_i\subset \mathbb{R}^d$ if at least $\alpha$-fraction of the $(d+1)$-tuples in $\mathcal{F}$ are intersecting then at least $(1-(t^d(1-\alpha))^{1/(d+1)})$-fraction of sets in $\mathcal{F}$ are intersecting. This is a special case of a more general result on intersections of $d$-Leray complexes. We also provide a construction showing that our result on $d$-Leray complexes is optimal. Interestingly the extremal example is representable as a family of cartesian products of convex sets, implying the bound $\alpha>1-\frac{1}{t^d}$ and the fraction $(1-(t^d(1-\alpha))^{1/(d+1)})$ above are also best possible. The well-known optimal construction for fractional Helly theorem for convex sets in $\mathbb{R}^d$ does not have $(p,d+1)$-condition for sublinear $p$. Inspired by this we give constructions showing that, somewhat surprisingly, imposing additional $(p,d+1)$-condition has negligible effect on improving the quantitative bounds in neither the fractional Helly theorem for convex sets nor Cartesian products of convex sets. Our constructions offer a rich family of distinct extremal configurations for fractional Helly theorem, implying in a sense that the optimal bound is stable., Comment: 17 pages, 2 figures

We introduce a notion of the \emph{crux} of a graph $G$, measuring the order of a smallest dense subgraph in $G$. This simple-looking notion leads to some generalisations of known results about cycles, offering an interesting paradigm of `replacing average degree by crux'. In particular, we prove that \emph{every} graph contains a cycle of length linear in its crux. Long proved that every subgraph of a hypercube $Q^m$ (resp. discrete torus $C_3^m$) with average degree $d$ contains a path of length $2^{d/2}$ (resp. $2^{d/4}$), and conjectured that there should be a path of length $2^{d}-1$ (resp. $3^{d/2}-1$). As a corollary of our result, together with isoperimetric inequalities, we close these exponential gaps giving asymptotically optimal bounds on long paths in hypercubes, discrete tori, and more generally Hamming graphs. We also consider random subgraphs of $C_4$-free graphs and hypercubes, proving near optimal bounds on lengths of long cycles., Comment: 16 pages, 1 figure. Minor changes. Accepted by SIAM Journal on Discrete Mathematics

In 1975, Erd\H{o}s asked the following question: what is the smallest function $f(n)$ for which all graphs with $n$ vertices and $f(n)$ edges contain two edge-disjoint cycles $C_1$ and $C_2$, such that the vertex set of $C_2$ is a subset of the vertex set of $C_1$ and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound $f(n)=O(n)$ using sublinear expanders., Comment: 10 pages, 2 figures

We prove an asymptotically tight bound on the extremal density guaranteeing subdivisions of bounded-degree bipartite graphs with a mild separability condition. As corollaries, we answer several questions of Reed and Wood on embedding sparse minors. Among others, $\bullet$ $(1+o(1))t^2$ average degree is sufficient to force the $t\times t$ grid as a topological minor; $\bullet$ $(3/2+o(1))t$ average degree forces every $t$-vertex planar graph as a minor, and the constant $3/2$ is optimal, furthermore, surprisingly, the value is the same for $t$-vertex graphs embeddable on any fixed surface; $\bullet$ a universal bound of $(2+o(1))t$ on average degree forcing every $t$-vertex graph in any nontrivial minor-closed family as a minor, and the constant 2 is best possible by considering graphs with given treewidth., Comment: 33 pages, 6 figures

For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e \in E(\overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $n\to\infty$.

We conduct a quantitative analysis on the number of random edges required to be added to a base graph~$H$ to significantly increase natural minor-monotone graph parameters in the resulting graph~$R$. Specifically, we show that if $R$ is obtained from a connected graph $H$ by adding only a few random edges, the tree-width, genus, and Hadwiger number of $R$ become very large, irrespective of the structure of~$H$., Comment: 20 pages

We prove that for every integer $k$, there exists $\varepsilon > 0$ such that for every n-vertex graph $G$ with no pivot-minor isomorphic to $C_k$, there exist disjoint sets $A,B \subseteq V(G)$ such that $|A|,|B| \geq \varepsilon n$, and $A$ is either complete or anticomplete to $B$. This proves the analog of the Erd\H{o}s-Hajnal conjecture for the class of graphs with no pivot-minor isomorphic to $C_k$., Comment: 13 pages, 4 figures