From rote@zedat.fu-berlin.de Tue May 02 17:13:48 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 1ptrhM-003sj0-LV; Tue, 02 May 2023 17:13:48 +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 1ptrhM-003xR1-J6; Tue, 02 May 2023 17:13:48 +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 1ptrhM-002OMq-Dl; Tue, 02 May 2023 17:13:48 +0200 Message-ID: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@inf.fu-berlin.de> Date: Tue, 2 May 2023 17:13:48 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.10.0 Content-Language: en-US References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= Cc: Tamara Knoll In-Reply-To: X-Forwarded-Message-Id: 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::1683040428-EC2C2B99-EF12D90E/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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday's Lecture May 15, 16:00 s.t. 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: Tue, 02 May 2023 15:13:49 -0000 Our next Monday Lecture will take place on May 15, at 16:00 sharp (unusual time and place!) at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, May 15, 2023, 16:00* *_Lecture_: Günter Rote (FU Berlin) *_Title_: The Generalized Combinatorial Lasoń-Alon-Zippel-Schwartz Nullstellensatz Lemma *_Abstract_:* We survey strengthenings and generalizations of the Schwartz-Zippel Lemma and Alon’s Combinatorial Nullstellensatz. Both lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges. From rote@zedat.fu-berlin.de Wed May 31 11:40:31 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 1q4IJj-002H8Q-Je; Wed, 31 May 2023 11:40:31 +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 1q4IJj-000fHa-H1; Wed, 31 May 2023 11:40:31 +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 1q4IJj-0039EF-Bd; Wed, 31 May 2023 11:40:31 +0200 Message-ID: Date: Wed, 31 May 2023 11:40:26 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Content-Language: en-US References: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@inf.fu-berlin.de> To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= Cc: Tamara Knoll In-Reply-To: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@inf.fu-berlin.de> X-Forwarded-Message-Id: <5e027433-1fea-1d3a-fe6b-81ad3fe84cb6@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::1685526031-55B29CF5-86515CB7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.001614, 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 Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture June 5, 16:00 s.t.: Grid Peeling and the Affine Curve-Shortening Flow 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: Wed, 31 May 2023 09:40:31 -0000 Our next Monday Lecture will take place on June 5 at 16:00 sharp (unusual time and place!) at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, June 5, 2023, 16:00* *_Lecture_: Günter Rote (FU Berlin) *_Title_: Grid Peeling and the Affine Curve-Shortening Flow *_Abstract_:* Grid Peeling is the process of taking the integer grid points inside a convex region and repeatedly removing the convex hull vertices. By contrast, the Affine Curve-Shortening Flow (ACSF) is defined as a particular deformation of a smooth curve. It has been observed in 2017 by Eppstein, Har-Peled, and Nivasch, that, as the grid is refined, Grid Peeling converges to the Affine Curve-Shortening Flow. As part of the M.Ed. thesis of Moritz Rüber, we have investigated the grid peeling process for special parabolas, and we could observe some striking phenomena. This has lead to the precise value of the constant that relates the two processes. With Morteza Saghafian from IST Austria, we could prove the convergence of grid peeling for the class of parabolas with vertical axis. *_Tea break_:* Before the talk, at 15:30, there will be a "tea break" at the usual place, Room 134 (glass door, straight from the stairs) in the first floor. From rote@zedat.fu-berlin.de Thu Jun 08 16:29:25 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 1q7Gdh-003YKP-9J; Thu, 08 Jun 2023 16:29:25 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1q7Gdh-002jNn-6s; Thu, 08 Jun 2023 16:29:25 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1q7Gdh-000mFU-1k; Thu, 08 Jun 2023 16:29:25 +0200 Message-ID: <20c02dd2-6042-4240-01d2-a29f18431b5b@inf.fu-berlin.de> Date: Thu, 8 Jun 2023 16:29:24 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0 Content-Language: en-US References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= In-Reply-To: X-Forwarded-Message-Id: 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::1686234565-40359743-98A6C0A7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.175251, 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 Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture June 12, 16:00 s.t.: The Multiplicative-Weights-Update Method 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, 08 Jun 2023 14:29:25 -0000 Our next Monday Lecture will take place on June 12 at 16:00 sharp at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* (Hörsaal Informatik) Freie Universität Berlin Department of Computer Science Takustr. 9 14195 Berlin *_Time_: *Monday, June 12, 2023, 16:00* *_Lecture_: Wolfgang Mulzer (FU Berlin) *_Title_: The Multiplicative-Weights-Update Method *_Abstract_:* The multiplicative weights update method is a design paradigm for algorithms that is used in many different areas of theoretical computer science and machine learning. A famous survey by Arora, Hazan, and Kale provides an excellent overview over the method and its applications. Together with Nabil Mustafa, we are currently working on a monograph that explores the method in more detail. I will give an overview of the method and share some nuggets that we encountered. Based on joint work with Nabil Mustafa. *_Tea break_:* Before the talk, at 15:30, there will be a tea "break" at the usual place, Room 134 in the first floor (glass door, facing the exit from the stairway). From rote@zedat.fu-berlin.de Mon Jun 19 16:10:02 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 1qBFZy-001RyH-Jd; Mon, 19 Jun 2023 16:10:02 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1qBFZy-001kDT-H5; Mon, 19 Jun 2023 16:10:02 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1qBFZy-003rIo-CG; Mon, 19 Jun 2023 16:10:02 +0200 Message-ID: <43bf3188-5883-20d2-4acb-da952483f37c@inf.fu-berlin.de> Date: Mon, 19 Jun 2023 16:10:02 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Content-Language: en-US References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= In-Reply-To: X-Forwarded-Message-Id: 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::1687183802-531C58E4-50B69D90/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.294559, 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 Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture on June 26, 16:00 s.t.: Topology at the North Pole / max-min allocation / Santa Claus problem 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: Mon, 19 Jun 2023 14:10:03 -0000 Our next Monday Lecture takes place on June 26 at 16:00 sharp at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, June 26, 2023, 16:00* *_Lecture_: Tibor Szabó (FU Berlin) *_Title_: Topology at the North Pole *_Abstract_:* In the max-min allocation problem, disjoint subsets of a set R of indivisible resources are to be allocated to a set P of players, such that the minimum utility among all players is maximized. We study the restricted variant, also known as the Santa Claus problem, where each resource has an intrinsic positive value, and each player covets a subset of the resources. Bezakova and Dani showed that this problem is NP-hard to approximate within a factor less than 2, consequently a great deal of work has focused on approximate solutions. The principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko. Accordingly, there has been much interest in bounding the integrality gap of this CLP. The existing algorithms and integrality gap estimations are all based one way or another on the combinatorial augmenting tree argument of Haxell for finding perfect matchings in certain hypergraphs. Here we introduce the use of topological tools for the restricted max-min allocation problem. This approach yields substantial improvements in the integrality gap of the CLP. In particular we improve the previously best known bound of 3.808 to 3.534. The talk represents joint work with Penny Haxell. *_Tea break_:* Before the talk, at 15:30, there will be a "tea break" at the usual place, Room 134 (glass door, straight from the stairs) in the first floor. From rote@zedat.fu-berlin.de Fri Jun 30 14:56:19 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 1qFDff-002ex2-0J; Fri, 30 Jun 2023 14:56:19 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1qFDfe-001AsT-U7; Fri, 30 Jun 2023 14:56:18 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1qFDfe-002pMt-On; Fri, 30 Jun 2023 14:56:18 +0200 Message-ID: <0bd785e9-2845-d200-e81e-be66404fc91d@inf.fu-berlin.de> Date: Fri, 30 Jun 2023 14:56:18 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Content-Language: en-US References: <43bf3188-5883-20d2-4acb-da952483f37c@inf.fu-berlin.de> From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de In-Reply-To: <43bf3188-5883-20d2-4acb-da952483f37c@inf.fu-berlin.de> X-Forwarded-Message-Id: <43bf3188-5883-20d2-4acb-da952483f37c@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::1688129779-CB1BEBA1-672451B1/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.105387, 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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture on July 3, 16:00 s.t.: Initial degenerations of Grassmannian via matroid subdivisions of hypersimplices 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: Fri, 30 Jun 2023 12:56:19 -0000 Our next Monday Lecture takes place on July 3 at 16:00 sharp at FU Berlin. *_Location_* *Great Lecture Hall - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: *Monday, July 3, 2023, 16:00* *_Lecture_: Dante Luber (TU Berlin) *_Title_: Initial degenerations of the Grassmannian via matroid subdivisions of hypersimplices *_Abstract_:* Nonempty initial degenerations of the Grassmannian are induced by weight functions in its tropicalization. On the other hand, the same weight function induces a regular matroidal subdivision of the hypersimplex. Hence, we study initial degenerations of the (3,8) Grassmannian via matroidal subdivisions of the (3,8) hypersimplex. Our techniques employ tropical, algebraic, and polyhedral geometry, as well as matroid theory, commutative algebra, and computation. *_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. 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 From rote@zedat.fu-berlin.de Thu Nov 23 10:43:26 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 1r66F3-002EdH-RY; Thu, 23 Nov 2023 10:43:25 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.3) tls TLS_AES_256_GCM_SHA384 (envelope-from ) id 1r66F3-001TWi-Ox; Thu, 23 Nov 2023 10:43:25 +0100 Received: from i59f7abf8.versanet.de ([89.247.171.248] helo=[192.168.178.20]) by inpost2.zedat.fu-berlin.de (Exim 4.95) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1r66F3-001IhZ-J7; Thu, 23 Nov 2023 10:43:25 +0100 Message-ID: <73a7c121-c881-44cb-930f-0755f07f0f8a@inf.fu-berlin.de> Date: Thu, 23 Nov 2023 10:43:25 +0100 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird To: facets-of-complexity@lists.fu-berlin.de Content-Language: en-US From: =?UTF-8?Q?G=C3=BCnter_Rote?= Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 89.247.171.248 X-ZEDAT-Hint: PO X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1700732605-DF98DCDE-16D27BC9/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 Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] talk by Daniel Huson on periodic tilings, Friday Nov. 23 in Potsdam/Golm 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, 23 Nov 2023 09:43:26 -0000 Dear Facets! Tomorrow there will be a lecture that might be interesting to some of us. (Beware: it is in Golm behind Potsdam; it takes a while to get there.) On 24.11, at 10:00 am, there will be a talk by Prof. Daniel Huson, University of Tübingen: A galaxy of periodic tilings This talk has four parts. In the first part - topology -, we recall the classification of two dimensions manifolds and orbifolds, and introduce their Conway notation. In the second part - geometry -, we discuss two-dimensional periodic tilings and their classification. In the third part - combinatorics -, we introduce Delaney-Dress symbols and indicate how they can be used to systematically enumerate periodic tilings. Finally, in the fourth part - algorithms and software -, we present Tegula (http://tegula.husonlab.org), a new computer program that can be used the explore the “galaxy” of all 2.4 billion periodic tilings of the euclidean plane, sphere and hyperbolic plane, of low Dress-complexity. This is joint work with Olaf Delgado and Rüdiger Zeller. It will take place in House 9 of the Golm Campus at the University of Potsdam. Room 1.22 ******** Prof. Dr. Myfanwy E. Evans Applied Geometry and Topology Institute for Mathematics, University of Potsdam The fastest connection from Berlin is the train RB23 through Berlin Zoologischer Garten via Wannsee to Potsdam, Golm Bhf. There is also RB21 from Potsdam Hauptbahnhof to Potsdam, Golm Bhf.