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  &lt\; sqrt( n /2)\, Maker has a winning stra
 tegy\, while for  q  &gt\; 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  &gt\; 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:20230706T055000
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:135036680@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20230710-L-Srivastav.html
END:VEVENT
END:VCALENDAR