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

Andreas Noever

Andreas Noever appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRData Structures and AlgorithmsDiscrete Mathematics

Catalog footprint

What is connected

6works
4topics
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

Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Hajós conjectured in 1968 that every Eulerian \(n\)-vertex graph can be decomposed into at most $\lfloor (n-1)/2\rfloor$ edge-disjoint cycles. This has been confirmed for some special graph classes, but the general case remains open. In a sequence of papers by Bienia and Meyniel (1986), Dean (1986), and Bollobás and Scott (1996) it was analogously conjectured that every \emph{directed} Eulerian graph can be decomposed into $O(n)$ cycles. In this paper, we show that every directed Eulerian graph can be decomposed into $O(n \log Δ)$ disjoint cycles, thus making progress towards the conjecture by Bollobás and Scott. Our approach is based on finding heavy cycles in certain edge-weightings of directed graphs. As a further consequence of our techniques, we prove that for every edge-weighted digraph in which every vertex has out-weight at least $1$, there exists a cycle with weight at least $Ω(\log \log n/{\log n})$, thus resolving a question by Bollobás and Scott.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A general lower bound for collaborative tree exploration

We consider collaborative graph exploration with a set of $k$ agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other vertices. We assume agents are deterministic, vertices are distinguishable, moves are simultaneous, and we allow agents to communicate globally. For this setting, we give the first non-trivial lower bounds that bridge the gap between small ($k \leq \sqrt n$) and large ($k \geq n$) teams of agents. Remarkably, our bounds tightly connect to existing results in both domains. First, we significantly extend a lower bound of $Ω(\log k / \log\log k)$ by Dynia et al. on the competitive ratio of a collaborative tree exploration strategy to the range $k \leq n \log^c n$ for any $c \in \mathbb{N}$. Second, we provide a tight lower bound on the number of agents needed for any competitive exploration algorithm. In particular, we show that any collaborative tree exploration algorithm with $k = Dn^{1+o(1)}$ agents has a competitive ratio of $ω(1)$, while Dereniowski et al. gave an algorithm with $k = Dn^{1+\varepsilon}$ agents and competitive ratio $O(1)$, for any $\varepsilon > 0$ and with $D$ denoting the diameter of the graph. Lastly, we show that, for any exploration algorithm using $k = n$ agents, there exist trees of arbitrarily large height $D$ that require $Ω(D^2)$ rounds, and we provide a simple algorithm that matches this bound for all trees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A tight Erdős-Pósa function for long cycles

A classic result of Erdős and Pósa says that any graph contains either $k$ vertex-disjoint cycles or can be made acyclic by deleting at most $O(k \log k)$ vertices. Here we generalize this result by showing that for all numbers $k$ and $l$ and for every graph $G$, either $G$ contains $k$ vertex-disjoint cycles of length at least $l$, or there exists a set $X$ of $\mathcal O(kl+k\log k)$ vertices that meets all cycles of length at least $l$ in $G$. As a corollary, the tree-width of any graph $G$ that does not contain $k$ vertex-disjoint cycles of length at least $l$ is of order $\mathcal O(kl+k\log k)$. These results improve on the work of Birmelé, Bondy and Reed '07 and Fiorini and Herinckx '14 and are optimal up to constant factors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Local resilience for squares of almost spanning cycles in sparse random graphs

In 1962, Pósa conjectured that a graph $G=(V, E)$ contains a square of a Hamiltonian cycle if $δ(G)\ge 2n/3$. Only more than thirty years later Komlós, Sárkőzy, and Szemerédi proved this conjecture using the so-called Blow-Up Lemma. Here we extend their result to a random graph setting. We show that for every $ε> 0$ and $p=n^{-1/2+ε}$ a.a.s. every subgraph of $G_{n,p}$ with minimum degree at least $(2/3+ε)np$ contains the square of a cycle on $(1-o(1))n$ vertices. This is almost best possible in three ways: (1) for $p\ll n^{-1/2}$ the random graph will not contain any square of a long cycle (2) one cannot hope for a resilience version for the square of a spanning cycle (as deleting all edges in the neighborhood of single vertex destroys this property) and (3) for $c<2/3$ a.a.s. $G_{n,p}$ contains a subgraph with minimum degree at least $cnp$ which does not contain the square of a path on $(1/3+c)n$ vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Online Ramsey Games for more than two colors

Consider the following one-player game played on an initially empty graph with $n$ vertices. At each stage a randomly selected new edge is added and the player must immediately color the edge with one of $r$ available colors. Her objective is to color as many edges as possible without creating a monochromatic copy of a fixed graph $F$. We use container and sparse regularity techniques to prove a tight upper bound on the typical duration of this game with an arbitrary, but fixed, number of colors for a family of $2$-balanced graphs. The bound confirms a conjecture of Marciniszyn, Spöhel and Steger and yields the first tight result for online graph avoidance games with more than two colors.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Robust hamiltonicity of random directed graphs

In his seminal paper from 1952 Dirac showed that the complete graph on $n\geq 3$ vertices remains Hamiltonian even if we allow an adversary to remove $\lfloor n/2\rfloor$ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on $n\geq 3$ vertices with minimum in- and out-degree at least $n/2$ contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of \emph{local resilience}. The local resilience of a graph (digraph) $G$ with respect to a property $\mathcal{P}$ is the maximum number $r$ such that $G$ has the property $\mathcal{P}$ even if we allow an adversary to remove an $r$-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is $1/2$. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability $p=ω(\log n /n)$ with respect to Hamiltonicity is $1/2\pm o(1)$. For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability $p=ω(\log n/\sqrt{n})$. In this paper we significantly improve their result to $p=ω(\log^8 n/ n)$, which is optimal up to the polylogarithmic factor.

0 citations0 reviewsNo code linkedOpen access