13 citations · 19 across the 11 of their papers we have counts for
11 papers
The random graph intuition for the tournament game
Dennis Clemens, Heidi Gebauer, Anita Liebenau
In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph on n vertices and selecting one of the two…
On Rainbow Cycles and Paths
Heidi Gebauer, Frank Mousset
In a properly edge colored graph, a subgraph using every color at most once is called rainbow. In this thesis, we study rainbow cycles and paths in proper edge colorings of complet…
Not All Saturated 3-Forests Are Tight
Heidi Gebauer, Anna Gundert, Robin A. Moser +1
A basic statement in graph theory is that every inclusion-maximal forest is connected, i.e. a tree. Using a definiton for higher dimensional forests by Graham and Lovasz and the co…
A Doubly Exponentially Crumbled Cake
Tobias Christ, Andrea Francke, Heidi Gebauer +2
We consider the following cake cutting game: Alice chooses a set P of n points in the square (cake) [0,1]^2, where (0,0) is in P; Bob cuts out n axis-parallel rectangles with disjo…
Maker Can Construct a Sparse Graph on a Small Board
Heidi Gebauer
We study Maker/Breaker games on the edges of sparse graphs. Maker and Breaker take turns in claiming previously unclaimed edges of a given graph H. Maker aims to occupy a given tar…
The Local Lemma is asymptotically tight for SAT
Heidi Gebauer, Tibor Szabo, Gabor Tardos
The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptot…