Felix Joos

Conflict-free hypergraph matchings

A celebrated theorem of Pippenger, and Frankl and Rödl 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''.

Hypergraph regularity and random sampling

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.

Percolation on random graphs with a fixed degree sequence

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.

Ramsey theory constructions from hypergraph matchings

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üredi 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ős and Gyárfás that was recently answered by Bennett, Cushman, Dudek, and Pralat by analyzing a colored modification of the triangle removal process.

preprint2021arXiv

Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree

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ühn, Osthus and Tyomkyn; and Glock, Kühn 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.

preprint2021arXiv

Fractional cycle decompositions in hypergraphs

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ühn 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.

preprint2021arXiv

Resolution of the Oberwolfach problem

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

preprint2020arXiv

A short proof of the blow-up lemma for approximate decompositions

Kim, Kühn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655--4742) greatly extended the well-known blow-up lemma of Komlós, Sárközy and Szemerédi 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ühn and Osthus to prove the tree packing conjecture due to Gyárfás 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ühn 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}$ .

preprint2020arXiv

Euler tours in hypergraphs

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.

preprint2016arXiv

Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs

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ős-Pósa 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.

preprint2015arXiv

A stronger bound for the strong chromatic index

We prove $χ_s'(G)\leq 1.93 Δ(G)^2$ for graphs of sufficiently large maximum degree where $χ_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.

preprint2015arXiv

Long cycles through prescribed vertices have the Erdős-Pósa property

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

preprint2015arXiv

Long paths and cycles in random subgraphs of graphs with large minimum degree

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+ε(c))ce^{-c})n$ for some function $ε(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.

A Characterization of Mixed Unit Interval Graphs

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach and Szwarcfiter (Mixed unit interval graphs, Discrete Math. 312, 3357-3363 (2012)).

A Characterization of Substar Graphs

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.

Equality of Distance Packing Numbers

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<k_2$ and $\lceil(3k_2+1)/2\rceil\leq 2k_1+1$ , we prove that it is NP-hard to determine for a given graph whether its distance- $k_1$ -packing number equals its distance- $k_2$ -packing number.

Induced 2-Regular Subgraphs in k-Chordal Cubic Graphs

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}+ε\right)n$ , if the independence number of $G$ is at most $\left(\frac{3}{8}-ε\right)n$ . To show the second result we give a precise structural description of cubic $4$ -chordal graphs.

Induced Cycles in Graphs

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.

Induced Matchings in Graphs of Bounded Maximum Degree

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

Induced Matchings in Graphs of Maximum Degree 4

For a graph $G$ , let $ν_s(G)$ be the induced matching number of $G$ . We prove the sharp bound $ν_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ős and Nešetřil, saying that the strong chromatic index $χ_s'(G)$ of a graph $G$ is at most $\frac{5}{4}Δ(G)^2$ , because $ν_s(G)\geq \frac{m(G)}{χ_s'(G)}$ and $n(G)\geq \frac{m(G)Δ(G)}{2}$ . Furthermore, it is shown that there is polynomial-time algorithm that computes induced matchings of size at least $\frac{n(G)}{9}$ .

Structural parameterizations for boxicity

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.

Forests and Trees among Gallai Graphs

The Gallai graph $Γ(G)$ of a graph $G$ has the edges of $G$ as its vertices and two distinct vertices $e$ and $f$ of $Γ(G)$ are adjacent in $Γ(G)$ if the edges $e$ and $f$ of $G$ are adjacent in $G$ but do not span a triangle in $G$ . Clearly, $Γ(G)$ is a subgraph of the line graph of $G$ . While line graphs can be recognized efficiently the complexity of recognizing Gallai graphs is unknown. In the present paper we characterize those graphs whose Gallai graphs are forests or trees, respectively.

Independence and Matching Number in Graphs with Maximum Degree 4

We prove that $\frac{7}{4}α(G)+β(G)\geq n(G)$ and $α(G)+\frac{3}{2}β(G)\geq n(G)$ for every triangle-free graph $G$ with maximum degree at most $4$ , where $α(G)$ is the independence number and $β(G)$ is the matching number of $G$ , respectively. These results are sharp for a graph on $13$ vertices. Furthermore we show $χ(G)\leq \frac{7}{4}ω(G)$ for $\{3K_1,K_1\cup K_5\}$ -free graphs, where $χ(G)$ is the chromatic number and $ω(G)$ is the clique number of $G$ , respectively.

Induced Matchings in Subcubic Graphs

We prove that a cubic graph with $m$ edges has an induced matching with at least $m/9$ edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (Induced matchings in subcubic planar graphs, SIAM J. Discrete Math. 26 (2012) 1383-1411) and solves a conjecture of Henning and Rautenbach (Induced matchings in subcubic graphs without short cycles, to appear in Discrete Math.).

Longest Paths in Circular Arc Graphs

As observed by Rautenbach and Sereni (arXiv:1302.5503) there is a gap in the proof of the theorem of Balister et al. (Longest paths in circular arc graphs, Combin. Probab. Comput., 13, No. 3, 311-317 (2004)), which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.

Random Subgraphs in Sparse Graphs

We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solve the problem for Cartesian powers of arbitrary graphs. In detail, let $G$ be a connected graph on $k$ vertices, $G^n$ the $n$ -th Cartesian power of $G$ , $α_i$ be the number of vertices of degree $i$ of $G$ , $λ$ be a positive real number, and $G^n_p$ be the graph obtained from $G^n$ by deleting every edge independently with probability $1-p$ . If $\sum_{i}α_i(1-p)^i=λ^{\frac{1}{n}}$ , then $\lim_{n\rightarrow \infty}\mathbb{P}[G^n_p {\rm\ is\ connected}]=\exp(-λ)$ . This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of $G$ itself, but only on the degree sequence of the graph.