Search

Recently, researchers have extended the concept of matchings to the more general problem of finding $b$-matchings in hypergraphs broadening the scope of potential applications and challenges. The concept of $b$-matchings, where $b$ is a function that assigns positive integers to the vertices of the graph, is a natural extension of matchings in graphs, where each vertex $v$ is allowed to be matched to up to $b(v)$ edges, rather than just one. The weighted $b$-matching problem then seeks to select a subset of the hyperedges that fulfills the constraint and maximizes the weight. In this work, we engineer novel algorithms for this generalized problem. More precisely, we introduce exact data reductions for the problem as well as a novel greedy initial solution and local search algorithms. These data reductions allow us to significantly shrink the input size. This is done by either determining if a hyperedge is guaranteed to be in an optimum $b$-matching and thus can be added to our solution or if it can be safely ignored. Our iterated local search algorithm provides a framework for finding suitable improvement swaps of edges. Experiments on a wide range of real-world hypergraphs show that our new set of data reductions are highly practical, and our initial solutions are competitive for graphs and hypergraphs as well.

Recent work showing the existence of conflict-free almost-perfect hypergraph matchings has found many applications. We show that, assuming certain simple degree and codegree conditions on the hypergraph $ \mathcal{H} $ and the conflicts to be avoided, a conflict-free almost-perfect matching can be extended to one covering all of the vertices in a particular subset of $ V(\mathcal{H}) $, by using an additional set of edges; in particular, we ensure that our matching avoids all of a further set of conflicts, which may consist of both old and new edges. This setup is useful for various applications, and our main theorem provides a black box which encapsulates many long and tedious calculations, massively simplifying the proofs of results in generalised Ramsey theory., Comment: 19 pages + 4 pages appendix

Fix $k\geq 2$, choose $\frac{\log n}{n^{(k-1)/k}}\leq p\leq 1-\Omega(\frac{\log^4 n}{n})$, and consider $G\sim G(n,p)$. For any pair of vertices $v,w\in V(G)$, we give a simple and precise formula for the expected number of steps that a random walk on $G$ starting at $w$ needs to first arrive at $v$. The formula only depends on basic structural properties of $G$. This improves and extends recent results of Ottolini and Steinerberger, as well as Ottolini, who considered this problem for constant as well as for mildly vanishing $p$., Comment: 14 pages

Increasing the connectivity of a graph is a pivotal challenge in robust network design. The weighted connectivity augmentation problem is a common version of the problem that takes link costs into consideration. The problem is then to find a minimum cost subset of a given set of weighted links that increases the connectivity of a graph by one when the links are added to the edge set of the input instance. In this work, we give a first implementation of recently discovered better-than-2 approximations. Furthermore, we propose three new heuristic and one exact approach. These include a greedy algorithm considering link costs and the number of unique cuts covered, an approach based on minimum spanning trees and a local search algorithm that may improve a given solution by swapping links of paths. Our exact approach uses an ILP formulation with efficient cut enumeration as well as a fast initialization routine. We then perform an extensive experimental evaluation which shows that our algorithms are faster and yield the best solutions compared to the current state-of-the-art as well as the recently discovered better-than-2 approximation algorithms. Our novel local search algorithm can improve solution quality even further.

We study conditions under which a given hypergraph is randomly robust Hamiltonian, which means that a random sparsification of the host graph contains a Hamilton cycle with high probability. Our main contribution provides nearly optimal results whenever the host graph is Hamilton connected in a locally robust sense, which translates to a typical induced subgraph of constant order containing Hamilton paths between any pair of suitable ends. The proofs are based on the recent breakthrough on Talagrand's conjecture, which reduces the problem to specifying a distribution on the desired guest structure in the (deterministic) host structure. We find such a distribution via a new argument that reduces the problem to the case of perfect matchings in a higher uniformity. As an application, we obtain asymptotically optimal results for perfect tilings in graphs and hypergraphs both in the minimum degree and uniformly dense setting. We also prove random robustness for powers of cycles under asymptotically optimal minimum degrees and degree sequences. We solve the problem for loose and tight Hamilton cycles in hypergraphs under a range of asymptotic minimum degree conditions. This includes in particular the case of $3$-uniform tight Hamilton cycles under vertex degree conditions. In all cases, our bounds on the sparseness are essentially best-possible., Comment: 28 pages

It is a well known result due to Korshunov and Sapozhenko that the hypercube in $n$ dimensions has $(1 + o(1)) \cdot 2 \sqrt e \cdot 2^{2^{n-1}}$ independent sets. Jenssen and Keevash investigated in depth Cartesian powers of cycles of fixed even lengths far beyond counting independent sets. They wonder to which extent their results extend to cycles of odd length, where not even the easiest case, counting independent sets in Cartesian powers of the triangle, is known. In this paper, we make progress on their question by providing a lower bound, which we believe to be tight. We also obtain a less precise lower bound for the number of independent sets in Cartesian powers of arbitrary odd cycles and show how to approach this question both with the cluster expansion method as well as more directly with isoperimetric inequalities., Comment: 16 pages

Let $T$ be an oriented tree on $n$ vertices with maximum degree at most $e^{o(\sqrt{\log n})}$. If $G$ is a digraph on $n$ vertices with minimum semidegree $\delta^0(G)\geq(\frac12+o(1))n$, then $G$ contains $T$ as a spanning tree, as recently shown by Kathapurkar and Montgomery (in fact, they only require maximum degree $o(n/\log n)$). This generalizes the corresponding result by Koml\'os, S\'ark\"ozy and Szemer\'edi for graphs. We investigate the natural question how many copies of $T$ the digraph $G$ contains. Our main result states that every such $G$ contains at least $|Aut(T)|^{-1}(\frac12-o(1))^nn!$ copies of $T$, which is optimal. This implies the analogous result in the undirected case., Comment: 24 pages

We prove that in all regular robust expanders $G$ every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders., Comment: 8 pages; final version, to appear in Random Structures & Algorithms

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\H{o}s and S\'os 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., Comment: 11 pages, 2 figures

We give asymptotically optimal constructions in generalized Ramsey theory using results about conflict-free hypergraph matchings. For example, we present an edge-coloring of $K_{n,n}$ with $2n/3 + o(n)$ colors such that each $4$-cycle receives at least three colors on its edges. This answers a question of Axenovich, F\"uredi and the second author (On generalized Ramsey theory: the bipartite case, J. Combin. Theory Ser B 79 (2000), 66--86). We also exhibit an edge-coloring of $K_n$ with $5n/6+o(n)$ colors that assigns each copy of $K_4$ at least five colors. This gives an alternative very short solution to an old question of Erd\H{o}s and Gy\'arf\'as that was recently answered by Bennett, Cushman, Dudek, and Pralat by analyzing a colored modification of the triangle removal process., Comment: 11 pages

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

We develop a method to study sufficient conditions for perfect mixed tilings. Our framework allows the embedding of bounded degree graphs $H$ with components of sublinear order. As a corollary, we recover and extend the work of K\"uhn and Osthus regarding sufficient minimum degree conditions for perfect $F$-tilings (for an arbitrary fixed graph $F$) by replacing the $F$-tiling with the aforementioned graphs $H$. Moreover, we obtain analogous results for degree sequences and in the setting of uniformly dense graphs. Finally, we asymptotically resolve a conjecture of Koml\'os in a strong sense., Comment: 32 pages + 2 pages appendix

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 famous result by R\"odl, Ruci\'nski, and Szemer\'edi guarantees a (tight) Hamilton cycle in $k$-uniform hypergraphs $H$ on $n$ vertices with minimum $(k-1)$-degree $\delta_{k-1}(H)\geq (1/2+o(1))n$, thereby extending Dirac's result from graphs to hypergraphs. For graphs, much more is known; each graph on $n$ vertices with $\delta(G)\geq (1/2+o(1))n$ contains $(1-o(1))r$ edge-disjoint Hamilton cycles where $r$ is the largest integer such that $G$ contains a spanning $2r$-regular subgraph, which is clearly asymptotically optimal. This was proved by Ferber, Krivelevich, and Sudakov answering a question raised by K\"uhn, Lapinskas, and Osthus. We extend this result to hypergraphs; every $k$-uniform hypergraph $H$ on $n$ vertices with $\delta_{k-1}(H)\geq (1/2+o(1))n$ contains $(1-o(1))r$ edge-disjoint (tight) Hamilton cycles where $r$ is the largest integer such that $H$ contains a spanning subgraph with each vertex belonging to $kr$ edges. In particular, this yields an asymptotic solution to a question of Glock, K\"uhn, and Osthus. In fact, our main result applies to approximately vertex-regular $k$-uniform hypergraphs with a weak quasirandom property and provides approximate decompositions into cycle factors without too short cycles., Comment: 27 pages

We prove that for any integer $k\geq 2$ and $\varepsilon>0$, there is an integer $\ell_0\geq 1$ such that any $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $(1/2+\varepsilon)n$ has a fractional decomposition into tight cycles of length $\ell$ ($\ell$-cycles for short) whenever $\ell\geq \ell_0$ and $n$ is large in terms of $\ell$. This is essentially tight. This immediately yields also approximate integral decompositions for these hypergraphs into $\ell$-cycles. Moreover, for graphs this even guarantees integral decompositions into $\ell$-cycles and solves a problem posed by Glock, K\"uhn and Osthus. For our proof, we introduce a new method for finding a set of $\ell$-cycles such that every edge is contained in roughly the same number of $\ell$-cycles from this set by exploiting that certain Markov chains are rapidly mixing., Comment: 14 pages

We prove that any quasirandom uniform hypergraph $H$ can be approximately decomposed into any collection of bounded degree hypergraphs with almost as many edges. In fact, our results also apply to multipartite hypergraphs and even to the sparse setting when the density of $H$ quickly tends to $0$ in terms of the number of vertices of $H$. Our results answer and address questions of Kim, K\"uhn, Osthus and Tyomkyn; and Glock, K\"uhn and Osthus as well as Keevash. The provided approximate decompositions exhibit strong quasirandom properties which is very useful for forthcoming applications. Our results also imply approximate solutions to natural hypergraph versions of long-standing graph decomposition problems, as well as several decomposition results for (quasi)random simplicial complexes into various more elementary simplicial complexes such as triangulations of spheres and other manifolds., Comment: 60 pages, updated references

Kim, K\"uhn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655--4742) greatly extended the well-known blow-up lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi by proving a `blow-up lemma for approximate decompositions' which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, K\"uhn and Osthus to prove the tree packing conjecture due to Gy\'arf\'as and Lehel from 1976 and Ringel's conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, K\"uhn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties so that it can be combined with Keevash's results on designs to obtain results of the following form. For all $\varepsilon>0$, $r\in \mathbb{N}$ and all large $n$ (such that $r$ divides $n-1$), there is a decomposition of $K_n$ into any collection of $r$-regular graphs $H_1,\ldots,H_{(n-1)/r}$ on $n$ vertices provided that $H_1,\ldots,H_{\varepsilon n}$ contain each at least $\varepsilon n$ vertices in components of size at most $\varepsilon^{-1}$., Comment: 26 pages

A tight Hamilton cycle in a $k$-uniform hypergraph ($k$-graph) $G$ is a cyclic ordering of the vertices of $G$ such that every set of $k$ consecutive vertices in the ordering forms an edge. R\"{o}dl, Ruci\'{n}ski, and Szemer\'{e}di proved that for $k\geq 3$, every $k$-graph on $n$ vertices with minimum codegree at least $n/2+o(n)$ contains a tight Hamilton cycle. We show that the number of tight Hamilton cycles in such $k$-graphs is $\exp(n\ln n-\Theta(n))$. As a corollary, we obtain a similar estimate on the number of Hamilton $\ell$-cycles in such $k$-graphs for all $\ell\in\{0,\dots,k-1\}$, which makes progress on a question of Ferber, Krivelevich and Sudakov., Comment: 20 pages. Final version, to appear in Combinatorics, Probability & Computing

For a collection $\mathbf{G}=\{G_1,\dots, G_s\}$ of not necessarily distinct graphs on the same vertex set $V$, a graph $H$ with vertices in $V$ is a $\mathbf{G}$-transversal if there exists a bijection $\phi:E(H)\rightarrow [s]$ such that $e\in E(G_{\phi(e)})$ for all $e\in E(H)$. We prove that for $|V|=s\geq 3$ and $\delta(G_i)\geq s/2$ for each $i\in [s]$, there exists a $\mathbf{G}$-transversal that is a Hamilton cycle. This confirms a conjecture of Aharoni. We also prove an analogous result for perfect matchings.

A celebrated theorem of Pippenger states that any almost regular hypergraph with small codegrees has an almost perfect matching. We show that one can find such an almost perfect matching which is `pseudorandom', meaning that, for instance, the matching contains as many edges from a given set of edges as predicted by a heuristic argument., Comment: 14 pages

A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi that applies to almost optimally bounded colourings. A corollary of this is that there exists a rainbow copy of any bounded-degree spanning subgraph $H$ in a quasirandom host graph $G$, assuming that the edge-colouring of $G$ fulfills a boundedness condition that is asymptotically best possible. This has many applications beyond rainbow colourings, for example to graph decompositions, orthogonal double covers and graph labellings., Comment: 28 pages

Robertson and Seymour proved that the family of all graphs containing a fixed graph $H$ as a minor has the Erd\H{o}s-P\'osa property if and only if $H$ is planar. We show that this is no longer true for the edge version of the Erd\H{o}s-P\'osa property, and indeed even fails when $H$ is an arbitrary subcubic tree of large pathwidth or a long ladder. This answers a question of Raymond, Sau and Thilikos., Comment: 22 pages

We show that a quasirandom $k$-uniform hypergraph $G$ has a tight Euler tour subject to the necessary condition that $k$ divides all vertex degrees. The case when $G$ is complete confirms a conjecture of Chung, Diaconis and Graham from 1989 on the existence of universal cycles for the $k$-subsets of an $n$-set., Comment: version accepted for publication in Combinatorica

The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given $2$-factor. We show that this can be achieved for all large $n$. We actually prove a significantly more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton-Waterloo problem for large $n$., Comment: revised version, to appear in Journal of the European Mathematical Society

In the 1960s, Erd\H{o}s and P\'osa proved that there is a packing-covering duality for cycles in graphs. As part of the graph minor project, Robertson and Seymour greatly extended this: there is such a duality for $H$-expansions in graphs if and only if $H$ is a planar graph (this includes the previous result for $H=K_3$). We consider vertex labelled graphs and minors and provide such a characterisation for $2$-connected labelled graphs $H$., Comment: 25 pages

Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. We develop an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov and Vu for graphs. From our results we deduce several corollaries on subgraph counts in random $d$-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruci\'nski and \v{S}ileikis on the threshold for the existence of an $\ell$-overlapping Hamilton cycle in a random $d$-regular $r$-graph. Moreover, we apply our results to prove bounds on the query complexity of testing subgraph-freeness. The problem of testing subgraph-freeness in the general graphs model was first studied by Alon, Kaufman, Krivelevich and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting., Comment: Final version. To appear in SIAM J. Discrete Math

A classical result of Koml\'os, S\'ark\"ozy and Szemer\'edi states that every $n$-vertex graph with minimum degree at least $(1/2+ o(1))n$ contains every $n$-vertex tree with maximum degree $O(n/\log{n})$ as a subgraph, and the bounds on the degree conditions are sharp. On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every $n$-vertex graph $G_\alpha$ with minimum degree at least $\alpha n$ for any fixed $\alpha >0$ and every $n$-vertex tree $T$ with bounded maximum degree, one can still find a copy of $T$ in $G_\alpha$ with high probability after adding $O(n)$ randomly-chosen edges to $G_\alpha$. We extend their results to trees with unbounded maximum degree. More precisely, for a given $n^{o(1)}\leq \Delta\leq cn/\log n$ and $\alpha>0$, we determine the precise number (up to a constant factor) of random edges that we need to add to an arbitrary $n$-vertex graph $G_\alpha$ with minimum degree $\alpha n$ in order to guarantee a copy of any fixed $n$-vertex tree $T$ with maximum degree at most~$\Delta$ with high probability., Comment: 41 pages

We prove a lower bound of $\Omega (d^{3/2} \cdot (2/\sqrt{3})^d)$ on the kissing number in dimension $d$. This improves the classical lower bound of Chabauty, Shannon, and Wyner by a linear factor in the dimension. We obtain a similar linear factor improvement to the best known lower bound on the maximal size of a spherical code of acute angle $\theta$ in high dimensions.

We prove a rainbow version of the blow-up lemma of Koml\'os, S\'ark\"ozy and Szemer\'edi for $\mu n$-bounded edge colourings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow-up lemma can be used to transfer the bandwidth theorem of B\"ottcher, Schacht and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of $\mu n$-bounded edge colourings. Kim, K\"uhn, Kupavskii and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow-up lemma given by R\"odl and Ruci\'nski, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan., Comment: 30 pages, included some recent applications

We provide a combinatorial characterization of all testable properties of $k$-uniform hypergraphs ($k$-graphs for short). Here, a $k$-graph property $P$ is testable if there is a randomized algorithm which makes a bounded number of edge queries and distinguishes with probability $2/3$ between $k$-graphs that satisfy $P$ and those that are far from satisfying $P$. For the $2$-graph case, such a combinatorial characterization was obtained by Alon, Fischer, Newman and Shapira. Our results for the $k$-graph setting are in contrast to those of Austin and Tao, who showed that for the somewhat stronger concept of local repairability, the testability results for graphs do not extend to the $3$-graph setting. Our proof relies on a random subhypergraph sampling result proved in a companion paper., Comment: 39 pages; we split the paper into two parts; the second part is arXiv:2110.01570

A key feature of Simonovits' proof of the classic Erd\H{o}s-P\'osa theorem is a simple subgraph of the host graph, a frame, that determines the outcome of the theorem. We transfer this frame technique to $A$-paths. With it we deduce a simple proof of Gallai's theorem, although with a worse bound, and we verify the Erd\H{o}s-P\'osa property for long and for even $A$-paths. We also show that even $A$-paths do not have the edge-Erd\H{o}s-P\'osa property., Comment: 16 pages. A number of small issues fixed, a table with results on paths and cycles added

We prove a lower bound on the entropy of sphere packings of $\mathbb R^d$ of density $\Theta(d \cdot 2^{-d})$. The entropy measures how plentiful such packings are, and our result is significantly stronger than the trivial lower bound that can be obtained from the mere existence of a dense packing. Our method also provides a new, statistical-physics-based proof of the $\Omega(d \cdot 2^{-d})$ lower bound on the maximum sphere packing density by showing that the expected packing density of a random configuration from the hard sphere model is at least $(1+o_d(1)) \log(2/\sqrt{3}) d \cdot 2^{-d}$ when the ratio of the fugacity parameter to the volume covered by a single sphere is at least $3^{-d/2}$. Such a bound on the sphere packing density was first achieved by Rogers, with subsequent improvements to the leading constant by Davenport and Rogers, Ball, Vance, and Venkatesh.

We show that for all $d\in \{3,\ldots,n-1\}$ the size of the largest component of a random $d$-regular graph on $n$ vertices around the percolation threshold $p=1/(d-1)$ is $\Theta(n^{2/3})$, with high probability. This extends known results for fixed $d\geq 3$ and for $d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. As a corollary, for the largest component of the percolated random $d$-regular graph, we also determine the diameter and the mixing time of the lazy random walk. In contrast to previous approaches, our proof is based on a simple application of the switching method., Comment: 10 pages

We consider bond percolation on random graphs with given degrees and bounded average degree. In particular, we consider the order of the largest component after the random deletion of the edges of such a random graph. We give a rough characterisation of those degree distributions for which bond percolation with high probability leaves a component of linear order, known usually as a giant component. We show that essentially the critical condition has to do with the tail of the degree distribution. Our proof makes use of recent technique introduced by Joos et al. [FOCS 2016, pp. 695--703], which is based on the switching method and avoids the use of the classic configuration model as well as the hypothesis of having a limiting object. Thus our results hold for sparse degree sequences without the usual restrictions that accompany the configuration model., Comment: Final version - has been published in the SIAM Journal on Discrete Mathematics 36 (2022)

We prove that the set of long cycles has the edge-Erd\H{o}s-P\'osa property: for every fixed integer $\ell\ge 3$ and every $k\in\mathbb{N}$, every graph $G$ either contains $k$ edge-disjoint cycles of length at least $\ell$ (long cycles) or an edge set $X$ of size $O(k^2\log k + \ell k)$ such that $G-X$ does not contain any long cycle. This answers a question of Birmel\'e, Bondy, and Reed (Combinatorica 27 (2007), 135--145)., Comment: 29 pages, 6 figures

We prove that if $T_1,\dots, T_n$ is a sequence of bounded degree trees so that $T_i$ has $i$ vertices, then $K_n$ has a decomposition into $T_1,\dots, T_n$. This shows that the tree packing conjecture of Gy\'arf\'as and Lehel from 1976 holds for all bounded degree trees (in fact, we can allow the first $o(n)$ trees to have arbitrary degrees). Similarly, we show that Ringel's conjecture from 1963 holds for all bounded degree trees. We deduce these results from a more general theorem, which yields decompositions of dense quasi-random graphs into suitable families of bounded degree graphs. Our proofs involve Szemer\'{e}di's regularity lemma, results on Hamilton decompositions of robust expanders, random walks, iterative absorption as well as a recent blow-up lemma for approximate decompositions., Comment: To appear in J. Eur. Math. Soc. (JEMS); final version (December 2017); 56 pages

A doubly group-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups $\Gamma_1,\Gamma_2$. A cycle in a doubly group-labeled graph is $(\Gamma_1,\Gamma_2)$-non-zero if it is non-zero in both coordinates. Our main result is a generalization of the Flat Wall Theorem of Robertson and Seymour to doubly group-labeled graphs. As an application, we determine all canonical obstructions to the Erd\H{o}s-P\'osa property for $(\Gamma_1,\Gamma_2)$-non-zero cycles in doubly group-labeled graphs. The obstructions imply that the half-integral Erd\H{o}s-P\'osa property always holds for $(\Gamma_1,\Gamma_2)$-non-zero cycles. Moreover, our approach gives a unified framework for proving packing results for constrained cycles in graphs. For example, as immediate corollaries we recover the Erd\H{o}s-P\'osa property for cycles and $S$-cycles and the half-integral Erd\H{o}s-P\'osa property for odd cycles and odd $S$-cycles. Furthermore, we recover Reed's Escher-wall Theorem. We also prove many new packing results as immediate corollaries. For example, we show that the half-integral Erd\H{o}s-P\'osa property holds for cycles not homologous to zero, odd cycles not homologous to zero, and $S$-cycles not homologous to zero. Moreover, the (full) Erd\H{o}s-P\'osa property holds for $S_1$-$S_2$-cycles and cycles not homologous to zero on an orientable surface. Finally, we also describe the canonical obstructions to the Erd\H{o}s-P\'osa property for cycles not homologous to zero and for odd $S$-cycles., Comment: 37 pages. In this version, we correct a small flaw in the proof of Lemma 20 pointed out by Robin Thomas and Youngho Yoo. Hence there is a worse dependence of the parameters in the statement of Lemma 20. This does not affect the overall argument and no parts appearing later in the paper. This flaw also appears in the version published by Combinatorica

For a fixed degree sequence $\mathcal{D}=(d_1,...,d_n)$, let $G(\mathcal{D})$ be a uniformly chosen (simple) graph on $\{1,...,n\}$ where the vertex $i$ has degree $d_i$. In this paper we determine whether $G(\mathcal{D})$ has a giant component with high probability, essentially imposing no conditions on $\mathcal{D}$. We simply insist that the sum of the degrees in $\mathcal{D}$ which are not 2 is at least $\lambda(n)$ for some function $\lambda$ going to infinity with $n$. This is a relatively minor technical condition, and when $\mathcal{D}$ does not satisfy it, both the probability that $G(\mathcal{D})$ has a giant component and the probability that $G(\mathcal{D})$ has no giant component are bounded away from $1$., Comment: 42 pages, to appear in Probability Theory and Related Fields

For a graph $G$ and $p\in [0,1]$, let $G_p$ arise from $G$ by deleting every edge mutually independently with probability $1-p$. The random graph model $(K_n)_p$ is certainly the most investigated random graph model and also known as the $G(n,p)$-model. We show that several results concerning the length of the longest path/cycle naturally translate to $G_p$ if $G$ is an arbitrary graph of minimum degree at least $n-1$. For a constant $c$, we show that asymptotically almost surely the length of the longest path is at least $(1-(1+\epsilon(c))ce^{-c})n$ for some function $\epsilon(c)\to 0$ as $c\to \infty$, and the length of the longest cycle is a least $(1-O(c^{- \frac{1}{5}}))n$. The first result is asymptotically best-possible. This extents several known results on the length of the longest path/cycle of a random graph in the $G(n,p)$-model., Comment: 13 pages

We prove $\chi_s'(G)\leq 1.93 \Delta(G)^2$ for graphs of sufficiently large maximum degree where $\chi_s'(G)$ is the strong chromatic index of $G$. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where it is allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable., Comment: 22 pages

We prove that for every graph, any vertex subset $S$, and given integers $k,\ell$: there are $k$ disjoint cycles of length at least $\ell$ that each contain at least one vertex from $S$, or a vertex set of size $O(\ell \cdot k \log k)$ that meets all such cycles. This generalises previous results of Fiorini and Hendrickx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in $O(k \log k \cdot s^2 \cdot (f(\ell) \cdot n+m))$ time, where $s$ denotes the cardinality of $S$., Comment: 11 pages

We show the following for every sufficiently connected graph $G$, any vertex subset $S$ of $G$, and given integer $k$: there are $k$ disjoint odd cycles in $G$ each containing a vertex of $S$ or there is set $X$ of at most $2k-2$ vertices such that $G-X$ does not contain any odd cycle that contains a vertex of $S$. We prove this via an extension of Kawarabayashi and Reed's result about parity-$k$-linked graphs (Combinatorica 29, 215-225). From this result it is easy to deduce several other well known results about the Erd\H{o}s-P\'osa property of odd cycles in highly connected graphs. This strengthens results due to Thomassen (Combinatorica 21, 321-333), and Rautenbach and Reed (Combinatorica 21, 267-278), respectively., Comment: 12 pages, referees' comments incorporated

For a graph $G$, let $\nu_s(G)$ be the induced matching number of $G$. We prove the sharp bound $\nu_s(G)\geq \frac{n(G)}{9}$ for every graph $G$ of maximum degree at most $4$ and without isolated vertices that does not contain a certain blown up $5$-cycle as a component. This result implies a consequence of the well known conjecture of Erd\H{o}s and Ne\v{s}et\v{r}il, saying that the strong chromatic index $\chi_s'(G)$ of a graph $G$ is at most $\frac{5}{4}\Delta(G)^2$, because $\nu_s(G)\geq \frac{m(G)}{\chi_s'(G)}$ and $n(G)\geq \frac{m(G)\Delta(G)}{2}$. Furthermore, it is shown that there is polynomial-time algorithm that computes induced matchings of size at least $\frac{n(G)}{9}$., Comment: 12 pages

For a graph $G$, let $\nu_s(G)$ be the induced matching number of $G$. We prove that $\nu_s(G) \geq \frac{n(G)}{(\lceil\frac{\Delta}{2}\rceil+1) (\lfloor\frac{\Delta}{2}\rfloor+1)}$ for every graph of sufficiently large maximum degree $\Delta$ and without isolated vertices. This bound is sharp. Moreover, there is polynomial-time algorithm which computes induced matchings of size as stated above., Comment: 7 pages

We show that a cubic graph $G$ of order $n$ has an induced $2$-regular subgraph of order at least a) $\frac{n-2}{4-\frac{4}{k}}$, if $G$ has no induced cycle of length more than $k$, b) $\frac{5n+6}{8}$, if $G$ has no induced cycle of length more than $4$, and $n>6$, and c) $\left(\frac{1}{4}+\epsilon\right)n$, if the independence number of $G$ is at most $\left(\frac{3}{8}-\epsilon\right)n$. To show the second result we give a precise structural description of cubic $4$-chordal graphs., Comment: 10 pages

The maximum cardinality of an induced $2$-regular subgraph of a graph $G$ is denoted by $c_{\rm ind}(G)$. We prove that if $G$ is an $r$-regular graph of order $n$, then $c_{\rm ind}(G) \geq \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}$ and we prove that if $G$ is a cubic claw-free graph on order $n$, then $c_{\rm ind}(G) > 13n/20$ and this bound is asymptotically best possible., Comment: 17 pages

The intersection graphs of stars in some tree are known as substar graphs. In this paper we give a characterization of substar graphs by the list of minimal forbidden induced subgraphs. This corrects a flaw in the main result of Chang, Jacobson, Monma and West (Subtree and substar intersection numbers, Discrete Appl. Math. 44, 205-220 (1993)) and this leads to a different list of minimal forbidden induced subgraphs., Comment: 7 pages

We characterize the graphs for which the independence number equals the packing number. As a consequence we obtain simple structural descriptions of the graphs for which (i) the distance-$k$-packing number equals the distance-$2k$-packing number, and (ii) the distance-$k$-matching number equals the distance-$2k$-matching number. This last result considerably simplifies and extends previous results of Cameron and Walker (The graphs with maximum induced matching and maximum matching the same size, Discrete Math. 299 (2005) 49-55). For positive integers $k_1$ and $k_2$ with $k_1

The boxicity of a graph $G$ is the least integer $d$ such that $G$ has an intersection model of axis-aligned $d$-dimensional boxes. Boxicity, the problem of deciding whether a given graph $G$ has boxicity at most $d$, is NP-complete for every fixed $d \ge 2$. We show that boxicity is fixed-parameter tractable when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Adiga et al., that boxicity is fixed-parameter tractable in the vertex cover number. Moreover, we show that boxicity admits an additive $1$-approximation when parameterized by the pathwidth of the input graph. Finally, we provide evidence in favor of a conjecture of Adiga et al. that boxicity remains NP-complete when parameterized by the treewidth., Comment: 19 pages