[Facets-of-complexity] Invitation to Monday Lecture on July 10, 16:00 s.t.: Anand Srivastav (Kiel), Maker Breaker Subgraph Game

[Günter Rote <rote@inf.fu-berlin.de>]

Our next Monday Lecture takes place on July 10 at 16:00 sharp at FU Berlin.

*_Location_*

*Great Lecture Hall - Ground Floor*
Freie Universität Berlin
Takustr. 9
14195 Berlin

*_Time_: *Monday, July 10, 2023, 16:00*

*_Lecture_: Anand Srivastav (Universität Kiel)

*_Title_: Recent Advances in the Maker Breaker Subgraph Game

*_Abstract_:*

The triangle game introduced by Chvátal and Erdős (1978) is one of
the old and famous combinatorial games. For n, q ∈ N, the
(n,q)-triangle game is played by two players, called Maker and Breaker,
on the complete graph K_n .

Alternately Maker claims one edge and thereafter Breaker claims q edges
of the graph. Maker wins the game if he can claim all three edges
of a triangle. Otherwise Breaker wins. Chvátal and Erdős (1978) proved
that for q < sqrt(n/2), Maker has a winning strategy, while
for q > 2 sqrt(n), Breaker wins. So, the threshold bias must be
in the interval [sqrt(1/2)sqrt(n) , 2 sqrt(n)].
Since then, the problem of finding the exact constant (and an associated
Breaker strategy) for the threshold bias of the triangle game has been
one of the interesting open problems in combinatorial game theory.
In fact, the constant is not known for any graph with a cycle and
we do not even know if such a constant exists. Balogh and Samotij (2011)
slightly improved the Chvátal-Erdős constant for Breaker’s winning
strategy from 2 to 1.935 with a randomized approach. Thereafter,
no progress was made. In this work, we present a new deterministic
strategy for Breaker leading to his win if q > sqrt(8/3) sqrt(n), for sufficiently large 
n. This almost matches the Chvátal-Erdős bound of sqrt(1/2)sqrt(n) for Maker's win 
(Glazik, Srivastav, Europ.J.Comb.2022).
In contrast to previous (greedy) strategies, we introduce a suitable
non-linear potential function on the set of nodes. By keeping the
potential small, Breaker picks edges that neutralize the
most ‘dangerous’ nodes with incident Maker edges blocking
Maker triangles. A characteristic property of the dynamics of the game
is that the total potential is not monotone decreasing. In fact,
the total potential of the game may increase, even for several turns,
but finally Breaker’s strategy prevents the total potential of the game
from exceeding a critical level, which results in Breaker’s win.
We further survey recent results for cycles of length k, and a
general potential function theorem (Sowa, Srivastav 2023).

This is joint work with Christian Glazik, Christian Schielke and
Mathias Sowa, Kiel University.

*_Tea break_:*

Before the talk, at 15:30, there will be a coffee and tea "break" at the usual
place, Room 134 (glass door, straight from the stairs) in the first floor.

*_Mittagsseminar on Tuesday_:*

On Tuesday, July 11, 12:00-12:30, Anand Srivastav will give a talk
in the Mittagsseminar, Room 055 or 053:
The Chromatic Number of Randomly Augmented Graphs