Source author record

Stefan Ehard

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

4works

2topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

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.

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

Biholes in balanced bipartite graphs

A bihole in a bipartite graph $G$ with partite sets $A$ and $B$ is an independent set $I$ in $G$ with $|I\cap A|=|I\cap B|$ . We prove lower bounds on the largest order of biholes in balanced bipartite graphs subject to conditions involving the vertex degrees and the average degree.

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.