BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:69618ef8-0c11-4c90-872a-5e3e1274a699
X-WR-CALNAME:[gt.go] - 'The Maker-Breaker positional game' by Florian Galli
 ot
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:69618ef8-0c11-4c90-872a-5e3e1274a699
DTSTAMP:20260421T113543Z
CLASS:PUBLIC
DESCRIPTION:/Exposé en anglais/Talk in english/ \n\nThe Maker-Breaker game 
 is played on a hypergraph H. Maker and Breaker take turns coloring vertice
 s of H\, in red and blue respectively. Maker wins if she gets a monochroma
 tic red edge at any point\, otherwise Breaker wins. We present some state 
 of the art around this game and then proceed with our own results. Our stu
 dy is centered on the notion of danger at x\, which is a subhypergraph rep
 resenting an urgent threat that Breaker must hit with his next pick if Mak
 er picks x. Applying this concept in hypergraphs of rank 3 i.e. in which a
 ll edges are of size at most 3\, we provide a structural characterization 
 of the winner with perfect play\, as well as optimal strategies for both p
 layers based on danger intersections. A crucial corollary is that Maker ha
 s a winning strategy on H if and only if she can guarantee the appearance\
 , within the first three rounds of play\, of a very specific elementary su
 bhypergraph on which she easily wins. As a consequence\, we are able to de
 termine the algorithmic complexity of deciding which player has a winning 
 strategy on a given hypergraph: this problem\, which is known to be PSPACE
 -complete on 6-uniform hypergraphs\, is in polynomial time on hypergraphs 
 of rank 3. Another consequence is that\, if Maker has a winning strategy o
 n a hypergraph H of rank 3\, then she can get a monochromatic red edge in 
 just O(log(|V(H)|)) rounds of play. \n\n[Florian Galliot] (ATER au LaBRI )
  \nhttps:///www-fourier.univ-grenoble-alpes.fr/~galliotf/index.php \n\nRem
 arks / Remarques \n\nFind all the information of the working group on this
  [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en
  | web page ] . \nRetrouvez toutes les informations du GT sur cette [ http
 s://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .
DTSTART;TZID=Europe/Paris:20231006T140000
DTEND;TZID=Europe/Paris:20231006T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'The Maker-Breaker positional game' by Florian Galliot
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
