Source author record

Julia Ehrenmüller

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

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

The Bandwidth Theorem in Sparse Graphs

The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any $n$ -vertex graph $G$ with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)n$ contains all $n$ -vertex $k$ -colourable graphs $H$ with bounded maximum degree and bandwidth $o(n)$ . We provide sparse analogues of this statement in random graphs as well as pseudorandom graphs. More precisely, we show that for $p\gg \big(\tfrac{\log n}{n}\big)^{1/Δ}$ asymptotically almost surely each spanning subgraph $G$ of $G(n,p)$ with minimum degree $\big(\tfrac{k-1}{k}+o(1)\big)pn$ contains all $n$ -vertex $k$ -colourable graphs $H$ with maximum degree $Δ$ , bandwidth $o(n)$ , and at least $C p^{-2}$ vertices not contained in any triangle. A similar result is shown for sufficiently bijumbled graphs, which, to the best of our knowledge, is the first resilience result in pseudorandom graphs for a rich class of spanning subgraphs. Finally, we provide improved results for $H$ with small degeneracy, which in particular imply a resilience result in $G(n,p)$ with respect to the containment of spanning bounded degree trees for $p\gg \big(\tfrac{\log n}{n}\big)^{1/3}$ .

preprint2015arXiv

An improved bound on the sizes of matchings guaranteeing a rainbow matching

A conjecture by Aharoni and Berger states that every family of $n$ matchings of size $n+1$ in a bipartite multigraph contains a rainbow matching of size $n$ . In this paper we prove that matching sizes of $(3/2 + o(1)) n$ suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best known one in case we only aim to find a rainbow matching of size $n-1$ . This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.

preprint2015arXiv

Nonempty Intersection of Longest Paths in Series-Parallel Graphs

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes of graphs, as for instance connected outerplanar graphs, connected split graphs, and 2-trees. A graph is series-parallel if it does not contain $K_4$ as a minor. Series-parallel graphs are also known as partial 2-trees, which are arbitrary subgraphs of 2-trees. We present a proof that every connected series-parallel graph has a vertex that is common to all of its longest paths. Since 2-trees are maximal series-parallel graphs, and outerplanar graphs are also series-parallel, our result captures these two classes in one proof and strengthens them to a larger class of graphs. We also describe how this vertex can be found in linear time.

preprint2015arXiv

On sets not belonging to algebras and rainbow matchings in graphs

Motivated by a question of Grinblat, we study the minimal number $\mathfrak{v}(n)$ that satisfies the following. If $A_1,\ldots, A_n$ are equivalence relations on a set $X$ such that for every $i\in[n]$ there are at least $\mathfrak{v}(n)$ elements whose equivalence classes with respect to $A_i$ are nontrivial, then $A_1, \ldots, A_n$ contain a rainbow matching, i.e. there exist $2n$ distinct elements $x_1,y_1,\ldots,x_n,y_n\in X$ with $x_i\sim_{A_i} y_i$ for each $i\in [n]$ . Grinblat asked whether $\mathfrak{v}(n) = 3n-2$ for every $n\geq 4$ . The best-known upper bound was $\mathfrak{v}(n) \leq 16n/5 + \mathcal{O}(1)$ due to Nivash and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that $\mathfrak{v}(n) = 3n+o(n)$ .

preprint2015arXiv

Spanning trees in random series-parallel graphs

By means of analytic techniques we show that the expected number of spanning trees in a connected labelled series-parallel graph on $n$ vertices chosen uniformly at random satisfies an estimate of the form $s \varrho^{-n} (1+o(1))$ , where $s$ and $\varrho$ are computable constants, the values of which are approximately $s \approx 0.09063$ and $\varrho^{-1} \approx 2.08415$ . We obtain analogue results for subfamilies of series-parallel graphs including 2-connected series-parallel graphs, 2-trees, and series-parallel graphs with fixed excess.

preprint2014arXiv

Keeping Avoider's graph almost acyclic

We consider biased $(1:b)$ Avoider-Enforcer games in the monotone and strict versions. In particular, we show that Avoider can keep his graph being a forest for every but maybe the last round of the game if $b \geq 200 n \ln n$ . By this we obtain essentially optimal upper bounds on the threshold biases for the non-planarity game, the non- $k$ -colorability game, and the $K_t$ -minor game thus addressing a question and improving the results of Hefetz, Krivelevich, Stojaković, and Szabó. Moreover, we give a slight improvement for the lower bound in the non-planarity game.

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.

Julia Ehrenmüller

Research overview

Is this your work?

6 publications

The Bandwidth Theorem in Sparse Graphs

An improved bound on the sizes of matchings guaranteeing a rainbow matching

Nonempty Intersection of Longest Paths in Series-Parallel Graphs

On sets not belonging to algebras and rainbow matchings in graphs

Spanning trees in random series-parallel graphs

Keeping Avoider's graph almost acyclic

See the researcher in context

Building this map preview