From rote@zedat.fu-berlin.de Thu Jul 06 16:12:54 2023 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1qHPj3-002VNH-CU; Thu, 06 Jul 2023 16:12:53 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1qHPj3-000SfA-9j; Thu, 06 Jul 2023 16:12:53 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1qHPj3-000LGc-4d; Thu, 06 Jul 2023 16:12:53 +0200 Message-ID: <3f3d536a-1120-0bb9-b2a0-a8ebb171a849@inf.fu-berlin.de> Date: Thu, 6 Jul 2023 16:12:52 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de Cc: Anand Srivastav References: <0bd785e9-2845-d200-e81e-be66404fc91d@inf.fu-berlin.de> Content-Language: en-US In-Reply-To: <0bd785e9-2845-d200-e81e-be66404fc91d@inf.fu-berlin.de> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 160.45.40.209 X-ZEDAT-Hint: PO X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1688652773-6DDA4C71-D434643A/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED, T_SCC_BODY_TEXT_LINE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture on July 10, 16:00 s.t.: Anand Srivastav (Kiel), Maker Breaker Subgraph Game X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.29 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 06 Jul 2023 14:12:54 -0000 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