BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Julia Ehrenmüller

Julia Ehrenmüller appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.LO

Catalog footprint

What is connected

6works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

6 published item(s)

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

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access