13 citations · 19 across the 11 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…