Andreas Noever

activity

20142019

most citedThe edge-statistics conjecture for

ℓ ≪ k^{6/5}

5 citations · 9 across the 4 of their papers we have counts for

collaborators

10 papers

math.CO2019

Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs

Charlotte Knierim, Maxime Larcher, Anders Martinsson +1

Hajós conjectured in 1968 that every Eulerian $n$-vertex graph can be decomposed into at most $⌊(n - 1) /2 ⌋$ edge-disjoint cycles. This has been confirmed for some spec…

math.CO2018★ 5 cited

The edge-statistics conjecture for $ℓ ≪ k^{6/5}$

Anders Martinsson, Frank Mousset, Andreas Noever +1

Let $k$ and $ℓ$ be positive integers. We prove that if $1 \leq ℓ \leq o_{k} (k^{6/5})$ , then in every large enough graph $G$ , the fraction of $k$ -vertex subsets that induce exac…

math.CO2017

On the probability of nonexistence in binomial subsets

Frank Mousset, Andreas Noever, Konstantinos Panagiotou +1

Given a hypergraph $Γ = (Ω, X)$ and a sequence $p = (p_{ω})_{ω \in Ω}$ of values in $(0, 1)$ , let $Ω_{p}$ be the random subset of $Ω$ obtained by keeping every…

cs.DS2017★ 2 cited

Tight Analysis of Randomized Greedy MIS

Manuela Fischer, Andreas Noever

We provide a tight analysis which settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fine…

math.CO2017

Smaller subgraphs of minimum degree k

Frank Mousset, Andreas Noever, Nemanja Škorić

In 1990 Erdős, Faudree, Rousseau and Schelp proved that for $k \geq 2$ , every graph with $n \geq k + 1$ vertices and $(k - 1) (n - k + 2) + (2 k - 2) + 1$ edges contains a subgraph of minimu…

cs.DM2016

A general lower bound for collaborative tree exploration

Yann Disser, Frank Mousset, Andreas Noever +2

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 ver…