BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: The triangle game introduced by Chvátal and Erdős (1978) is on
e 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 there
after 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 Er
dős (1978) proved that for q <\; sqrt( n /2)\, Maker has a winning stra
tegy\, while for q >\; 2 sqrt( n )\, Breaker wins. So\, the threshold b
ias 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 str
ategy) for the threshold bias of the triangle game has been one of the inte
resting 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 c
onstant 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 randomize
d 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át
al-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 intro
duce a suitable non-linear potential function on the set of nodes. By keepi
ng the potential small\, Breaker picks edges that neutralize the most ‘dang
erous’ nodes with incident Maker edges blocking Maker triangles. A characte
ristic 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 incr
ease\, even for several turns\, but finally Breaker’s strategy prevents the
total potential of the game from exceeding a critical level\, which result
s in Breaker’s win. We further survey recent results for cycles of length
k \, and a general potential function theorem (Sowa\, Srivastav 2023). Th
is is joint work with Christian Glazik\, Christian Schielke and Mathias Sow
a\, Kiel University.
DTSTAMP:20230706T055600
DTSTART:20230710T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Great Lecture Hall (Ground Floor)
SEQUENCE:0
SUMMARY:Anand Srivastav (Kiel): Recent Advances in the Maker Breaker Subgra
ph Game
UID:135299521@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/math/dates/colloquium/2022/20230710-L-Sriva
stav.html
END:VEVENT
END:VCALENDAR