Search

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.

Hansel's lemma states that $\sum_{H\in \mathcal{H}}|H| \geq n \log_2 n$ holds where $\mathcal{H}$ is a collection of bipartite graphs covering all the edges of $K_n$. We generalize this lemma to the corresponding multigraph covering problem and the graphon covering problem. We also prove an upper bound on $\sum_{H\in \mathcal{H}}|H|$ which shows that our generalization is asymptotically tight in some sense., 13 pages

It is well-known that every tournament contains a Hamilton path, and every strongly connected tournament contains a Hamilton cycle. This paper establishes transversal generalizations of these classical results. For a collection $\mathbf{T}=\{T_1,\dots,T_m\}$ of not-necessarily distinct tournaments on a common vertex set $V$, an $m$-edge directed graph $\mathcal{D}$ with vertices in $V$ is called a $\mathbf{T}$-transversal if there exists a bijection $\phi\colon E(\mathcal{D})\to [m]$ such that $e\in E(T_{\phi(e)})$ for all $e\in E(\mathcal{D})$. We prove that for sufficiently large $m$ with $m=|V|-1$, there exists a $\mathbf{T}$-transversal Hamilton path. Moreover, if $m=|V|$ and at least $m-1$ of the tournaments $T_1,\ldots,T_m$ are assumed to be strongly connected, then there is a $\mathbf{T}$-transversal Hamilton cycle. In our proof, we utilize a novel way of partitioning tournaments which we dub $\mathbf{H}$-partition.

Given a collection $\mathcal{G}=(G_1,\dots, G_h)$ of graphs on the same vertex set $V$ of size $n$, an $h$-edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow [h]$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The conditions on the minimum degree $\delta(\mathcal{G})=\min_{i\in[h]}\{ \delta(G_i)\}$ for finding a spanning $\mathcal{G}$-transversal isomorphic to a graph $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$-factor, a spanning tree with maximum degree $o(n/\log n)$ and a power of a Hamilton cycle, etc. In this paper, we determined the asymptotically tight threshold on $\delta(\mathcal{G})$ for finding a $\mathcal{G}$-transversal isomorphic to $H$ when $H$ is a general $n$-vertex graph with bounded maximum degree and $o(n)$-bandwidth. This provides a transversal generalization of the celebrated Bandwidth theorem by B\"ottcher, Schacht and Taraz.

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

There has been extensive studies on the following question: given $k$ graphs $G_1,\dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a `colorful' copy of $H$, i.e., a copy of $H$ containing at most one edge from each $G_i$? A lower bound on $\sum_{i\in [k]} e(G_i)$ enforcing a colorful copy of a given graph $H$ was considered by Keevash, Saks, Sudakov, and Verstra\"{e}te. They defined $\operatorname{ex}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,\dots, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $\operatorname{ex}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, one of the two natural constructions is always the extremal construction. Moreover, they conjectured the same holds for every color-critical graphs and proved it for 3-color-critical graphs. We prove their conjecture for 4-color-critical graphs and for almost all $r$-color-critical graphs when $r > 4$. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of $k$. This answers a question of Keevash, Saks, Sudakov, and Verstra\"{e}te.

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 tight up to multiplicative constant.

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

A celebrated theorem of Pippenger, and Frankl and R\"odl states that every almost-regular, uniform hypergraph $\mathcal{H}$ with small maximum codegree has an almost-perfect matching. We extend this result by obtaining a ``conflict-free'' matching, where conflicts are encoded via a collection $\mathcal{C}$ of subsets $C\subseteq E(\mathcal{H})$. We say that a matching $\mathcal{M}\subseteq E(\mathcal{H})$ is conflict-free if $\mathcal{M}$ does not contain an element of $\mathcal{C}$ as a subset. Under natural assumptions on $\mathcal{C}$, we prove that $\mathcal{H}$ has a conflict-free, almost-perfect matching. This has many applications, one of which yields new asymptotic results for so-called ``high-girth'' Steiner systems. Our main tool is a random greedy algorithm which we call the ``conflict-free matching process''., Comment: 58 pages

Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and Rödl conjectured that for any given $μ>0$, there exists $n_0$ such that the following holds. Every $n$-vertex Steiner triple system contains all hypertrees with at most $(1-μ)n$ vertices whenever $n\geq n_0$. We prove this conjecture., 19 pages, 2 figures

Let $f^{(r)}(n;s,k)$ be the maximum number of edges of an $r$-uniform hypergraph on $n$ vertices not containing a subgraph with $k$ edges and at most $s$ vertices. In 1973, Brown, Erdős and Sós conjectured that the limit $$\lim_{n\to \infty} n^{-2} f^{(3)}(n;k+2,k)$$ exists for all $k$ and confirmed it for $k=2$. Recently, Glock showed this for $k=3$. We settle the next open case, $k=4$, by showing that $f^{(3)}(n;6,4)=\left(\frac{7}{36}+o(1)\right)n^2$ as $n\to\infty$. More generally, for all $k\in \{3,4\}$, $r\ge 3$ and $t\in [2,r-1]$, we compute the value of the limit $\lim_{n\to \infty} n^{-t}f^{(r)}(n;k(r-t)+t,k)$, which settles a problem of Shangguan and Tamo., 11 pages, 2 figures

We prove that every properly edge-colored $n$-vertex graph with average degree at least $100(\log n)^2$ contains a rainbow cycle, improving upon $(\log n)^{2+o(1)}$ bound due to Tomon. We also prove that every properly colored $n$-vertex graph with at least $10^5 k^2 n^{1+1/k}$ edges contains a rainbow $2k$-cycle, which improves the previous bound $2^{ck^2}n^{1+1/k}$ obtained by Janzer. Our method using homomorphism inequalities and a lopsided regularization lemma also provides a simple way to prove the Erd\H{o}s--Simonovits supersaturation theorem for even cycles, which may be of independent interest.

For a given graph $H$, its subdivisions carry the same topological structure. The existence of $H$-subdivisions within a graph $G$ has deep connections with topological, structural and extremal properties of $G$. One prominent examples of such connections, due to Bollob\'{a}s and Thomason and independently Koml\'os and Szemer\'edi, asserts that the average degree of $G$ being $d$ ensures a $K_{\Omega(\sqrt{d})}$-subdivision in $G$. Although this square-root bound is best possible, various results showed that much larger clique subdivisions can be found in a graph from many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. This reveals the unifying cause underpinning all those improvements for various classes of graphs studied. Roughly speaking, when embedding subdivisions, natural space constraints arise; and such space constraints can be measured via crux. Our main result gives an asymptotically optimal bound on the size of a largest clique subdivision in a generic graph $G$, which is determined by both its average degree and its crux size. As corollaries, we obtain (1) a characterisation of extremal graphs for which the square-root bound above is tight: they are essentially disjoint union of graphs each of which has the crux size linear in $d$; (2) a unifying approach to find a clique subdivision of almost optimal size in graphs which does not contain a fixed bipartite graph as a subgraph; (3) and that the clique subdivision size in random graphs $G(n,p)$ witnesses a dichotomy: when $p = \omega(n^{-1/2})$, the barrier is the space, while when $p=o( n^{-1/2})$, the bottleneck is the density., Comment: 37 pages, 2 figures

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

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 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��s-Hajnal conjecture for the class of graphs with no pivot-minor isomorphic to $C_k$., 13 pages, 4 figures

The famous Erd\H{o}s-Rademacher problem asks for the smallest number of $r$-cliques in a graph with the given number of vertices and edges. Despite decades of active attempts, the asymptotic value of this extremal function for all $r$ was determined only recently, by Reiher [Annals of Mathematics, 184 (2016) 683--707]. Here we describe the asymptotic structure of all almost extremal graphs. This task for $r=3$ was previously accomplished by Pikhurko and Razborov [Combinatorics, Probability and Computing, 26 (2017) 138--160].

We investigate how minor-monotone graph parameters change if we add a few random edges to a connected graph $H$. Surprisingly, after adding a few random edges, its treewidth, treedepth, genus, and the size of a largest complete minor become very large regardless of the shape of $H$. Our results are close to best possible for various cases., Comment: 19 pages

We prove several results on approximate decompositions of edge-coloured quasirandom graphs into rainbow spanning structures. More precisely, we say that an edge-colouring of a graph is locally $\ell$-bounded if no vertex is incident to more than $\ell$ edges of any given colour, and that it is (globally) $g$-bounded if no colour appears more than $g$ times in the colouring. Note that every proper colouring of an $n$-vertex graph is locally $1$-bounded, and (globally) $n/2$-bounded. Our results imply the following: (i) The existence of approximate decompositions of edge-coloured $K_n$ into rainbow almost-spanning cycles, provided that the colouring is $\frac{n}{2}$-bounded and locally $o(n)$-bounded. (ii) The existence of approximate decompositions of edge-coloured $K_n$ into rainbow Hamilton cycles, provided that the colouring is $(1-o(1))\frac n2$-bounded and locally $o\big(\frac{n}{\log^4 n}\big)$-bounded. (iii) A bipartite version of our results implies that every $n\times n$ array, where each symbol appears $(1-o(1))n$ times in total and appears only $o\big(\frac{n}{\log^2 n}\big)$ times in each row or column, has an approximate decomposition into full transversals. We also prove analogues of (i) and (ii) for $F$-factors, where $F$ is any fixed graph. Apart from the logarithmic factor in (ii), all these bounds are essentially best possible. (i) can be viewed as a generalization of a recent result of Alon, Pokrovskiy and Sudakov, who showed the existence of an almost spanning cycle in a properly coloured complete graph. Both (i) and (ii) imply approximate versions of a conjecture of Brualdi and Hollingsworth, stating that every properly edge-coloured complete graph can be decomposed into rainbow spanning trees., final version, to appear in Random Structures and Algorithms

Given graphs $H_1,\ldots, H_k$, a graph $G$ is $(H_1,\ldots, H_k)$-free if there is a $k$-edge-colouring $��:E(G)\rightarrow [k]$ with no monochromatic copy of $H_i$ with edges of colour $i$ for each $i\in[k]$. Fix a function $f(n)$, the Ramsey-Tur��n function $\textrm{RT}(n,H_1,\ldots,H_k,f(n))$ is the maximum number of edges in an $n$-vertex $(H_1,\ldots,H_k)$-free graph with independence number at most $f(n)$. We determine $\textrm{RT}(n,K_3,K_s,��n)$ for $s\in\{3,4,5\}$ and sufficiently small $��$, confirming a conjecture of Erd��s and S��s from 1979. It is known that $\textrm{RT}(n,K_8,f(n))$ has a phase transition at $f(n)=��(\sqrt{n\log n})$. However, the values of $\textrm{RT}(n,K_8, o(\sqrt{n\log n}))$ was not known. We determined this value by proving $\textrm{RT}(n,K_8,o(\sqrt{n\log n}))=\frac{n^2}{4}+o(n^2)$, answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings., 20 pages, 2 figures, 2 pages appendix

The extremal number $\mathrm{ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r \in [1,2]$ is realisable if there exists a graph $F$ with $\mathrm{ex}(n , F) = ��(n^r)$. Several decades ago, Erd��s and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1, \frac{7}{5}, 2$, and the numbers of the form $1+\frac{1}{m}$, $2-\frac{1}{m}$, $2-\frac{2}{m}$ for integers $m \geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$. In this paper, we make progress on the conjecture of Erd��s and Simonovits. First, we show that $2 - \frac{a}{b}$ is realisable for any integers $a,b \geq 1$ with $b>a$ and $b \equiv \pm 1 ~({\rm mod}\:a)$. This includes all previously known ones, and gives infinitely many limit points $2-\frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.

An $r$-matching in a graph $G$ is a collection of edges in $G$ such that the distance between any two edges is at least $r$. A $2$-matching is also called an induced matching. In this paper, we estimate the maximum number of $r$-matchings in a tree of fixed order. We also prove that the $n$-vertex path has the maximum number of induced matchings among all $n$-vertex trees.

Koml��s conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify., 33 pages, to appear in Proceedings of the London Mathematical Society

We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to longstanding decomposition problems. For instance, our results imply the following. Let $G$ be a quasi-random $n$-vertex graph and suppose $H_1,\dots,H_s$ are bounded degree $n$-vertex graphs with $\sum_{i=1}^{s} e(H_i) \leq (1-o(1)) e(G)$. Then $H_1,\dots,H_s$ can be packed edge-disjointly into $G$. The case when $G$ is the complete graph $K_n$ implies an approximate version of the tree packing conjecture of Gy\'arf\'as and Lehel for bounded degree trees, and of the Oberwolfach problem. We provide a more general version of the above approximate decomposition result which can be applied to super-regular graphs and thus can be combined with Szemer\'edi's regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Koml\'os, S\'ark\H{o}zy and Szemer\'edi to the setting of approximate decompositions., Comment: Final version, to appear in Transactions of the American Mathematical Society

A family $\mathcal{F}$ is $t$-$\it{intersecting}$ if any two members have at least $t$ common elements. Erd\H os, Ko, and Rado proved that the maximum size of a $t$-intersecting family of subsets of size $k$ is equal to $ {{n-t} \choose {k-t}}$ if $n\geq n_0(k,t)$. Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing $t$-intersecting families for all $t \geq 1$. In 2004, Talbot generalized Bollob\'{a}s's Two Families Theorem to $t$-intersecting families. In this paper, we proved a slight generalization of Talbot's result by using the probabilistic method.