From rote@zedat.fu-berlin.de Fri Jan 07 16:26:35 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1n5r8U-0012Uh-MP; Fri, 07 Jan 2022 16:26:34 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1n5r8U-002Zza-Je; Fri, 07 Jan 2022 16:26:34 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1n5r8U-002mf8-Ef; Fri, 07 Jan 2022 16:26:34 +0100 Message-ID: Date: Fri, 7 Jan 2022 16:26:34 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.4.1 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: <147fe76c-7f8c-0aea-94df-3ea570a624f5@inf.fu-berlin.de> Content-Language: en-US In-Reply-To: <147fe76c-7f8c-0aea-94df-3ea570a624f5@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-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1641569194-0009FB93-80D288D3/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.167864, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED X-Spam-Checker-Version: SpamAssassin 3.4.6 on Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture - Jan 10 2022, 2:15 p.m., online via zoom 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, 07 Jan 2022 15:26:35 -0000 Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 Time: Monday, Jan 10, 2022 - 14:15 h Lecture: Vera Traub (ETH Zürich): Better-Than-2 Approximations for Weighted Tree Augmentation The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. There are many standard techniques that lead to a 2-approximation for WTAP, but despite much progress on special cases, the factor 2 remained unbeaten for several decades. In this talk we present two algorithms for WTAP that improve on the longstanding approximation ratio of 2. The first algorithm is a relative greedy algorithm, which starts with a simple, though weak, solution and iteratively replaces parts of this starting solution by stronger components. This algorithm achieves an approximation ratio of (1 + ln 2 + ε) < 1.7. Second, we present a local search algorithm that achieves an approximation ratio of 1.5 + ε (for any constant ε > 0). This is joint work with Rico Zenklusen. ===== There will be no colloquium on this Monday. From itabrunke@zedat.fu-berlin.de Wed Jan 12 18:03:37 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1n7h28-001hzQ-Tv; Wed, 12 Jan 2022 18:03:37 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1n7h28-0047vA-QT; Wed, 12 Jan 2022 18:03:36 +0100 Received: from ip5f5af673.dynamic.kabel-deutschland.de ([95.90.246.115] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1n7h28-000NdJ-F7; Wed, 12 Jan 2022 18:03:36 +0100 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 12 Jan 2022 18:03:36 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------59902AFFCF5977DBDD90F08C" X-Antivirus: Avast (VPS 220112-2, 12.1.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.246.115 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1642007016-00086027-91307092/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.034948, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday's Lecture & Colloquium Jan.17 - online via Zoom. 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, 12 Jan 2022 17:03:37 -0000 This is a multi-part message in MIME format. --------------59902AFFCF5977DBDD90F08C Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place *online via Zoom* on January 17.* Please find link to Zoom Meeting here: ** **https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 * *A password is not required!** *** *You all are cordially invited!* *_Location_**: ** * *Online via Zoom.* *_Monday's Lecture_: María A. Hernández Cifre (Universitdad de Murcia)* *_Time_: **Monday, January 17 - 14:15 h* *_Title_: On discrete Brunn-Minkowski type inequalities* *_Abstract_:* The classical Brunn-Minkowski inequality in the n-dimensional Euclidean space asserts that the volume (Lebesgue measure) to the power 1/n is a concave functional when dealing with convex bodies (non-empty compact convex sets). This result has become not only a cornerstone of the Brunn-Minkowski theory, but also a powerful tool in other related fields of mathematics. In this talk we will make a brief walk on this inequality, as well as on its extensions to the Lp-setting, for non-negative values of p. Then, we will move to the discrete world, either considering the integer lattice endowed with the cardinality, or working with the lattice point enumerator, which provides with the number of integer points contained in a given convex body: we will discuss and show certain discrete analogues of the above mentioned Brunn-Minkowski type inequalities in both cases. This is about joint works with Eduardo Lucas and Jesús Yepes Nicolás. *Break* *_Monday's Colloquium_: Ji Hoon Chun (Technische Universität Berlin)* *_Time_: **Monday, January 17**- 16:00 h s.t.* *_Title_: The Sausage Conjecture in dimension 4* *_Abstract_:* The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco. *You all are cordially invited!* -- -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------59902AFFCF5977DBDD90F08C Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on January 17.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!
You all are cordially invited!

Location:

Online via Zoom.


Monday's Lecture: María A. Hernández Cifre (Universitdad de Murcia)

Time: Monday, January 17 - 14:15 h

Title: On discrete Brunn-Minkowski type inequalities

Abstract:

The classical Brunn-Minkowski inequality in the n-dimensional Euclidean space asserts that the volume (Lebesgue measure) to the power 1/n is a concave functional when dealing with convex bodies (non-empty compact convex sets). This result has become not only a cornerstone of the Brunn-Minkowski theory, but also a powerful tool in other related fields of mathematics.
In this talk we will make a brief walk on this inequality, as well as on its extensions to the Lp-setting, for non-negative values of p. Then, we will move to the discrete world, either considering the integer lattice endowed with the cardinality, or working with the lattice point enumerator, which provides with the number of integer points contained in a given convex body: we will discuss and show certain discrete analogues of the above mentioned Brunn-Minkowski type inequalities in both cases.
This is about joint works with Eduardo Lucas and Jesús Yepes Nicolás.


Break

Monday's Colloquium: Ji Hoon Chun (Technische Universität Berlin)

Time: Monday, January 17 - 16:00 h s.t.

Title: The Sausage Conjecture in dimension 4

Abstract:

The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco.

You all are cordially invited! 
--

Virenfrei. www.avast.com
--------------59902AFFCF5977DBDD90F08C-- From itabrunke@zedat.fu-berlin.de Wed Jan 12 20:19:45 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1n7j9p-001tRp-RR; Wed, 12 Jan 2022 20:19:42 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1n7j9p-000eAe-Nr; Wed, 12 Jan 2022 20:19:41 +0100 Received: from ip5f5af673.dynamic.kabel-deutschland.de ([95.90.246.115] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1n7j9p-000cUJ-CI; Wed, 12 Jan 2022 20:19:41 +0100 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: <77828c69-4280-1c18-e234-b9edc266a4fa@fu-berlin.de> Date: Wed, 12 Jan 2022 20:19:40 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------DDF8389FDBE11A37B741CB4E" X-Antivirus: Avast (VPS 220112-2, 12.1.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.246.115 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1642015181-0003D58E-B11FE71A/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.050686, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Korrektur Title Coll.: Invitation to Monday's Lecture & Colloquium Jan.17. 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, 12 Jan 2022 19:19:46 -0000 This is a multi-part message in MIME format. --------------DDF8389FDBE11A37B741CB4E Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place *online via Zoom* on January 17.* Please find link to Zoom Meeting here: ** **https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 * *A password is not required!** *** *You all are cordially invited!* *_Location_**: ** * *Online via Zoom.* *_Monday's Lecture_: María A. Hernández Cifre (Universitdad de Murcia)* *_Time_: **Monday, January 17 - 14:15 h* *_Title_: On discrete Brunn-Minkowski type inequalities* *_Abstract_:* The classical Brunn-Minkowski inequality in the n-dimensional Euclidean space asserts that the volume (Lebesgue measure) to the power 1/n is a concave functional when dealing with convex bodies (non-empty compact convex sets). This result has become not only a cornerstone of the Brunn-Minkowski theory, but also a powerful tool in other related fields of mathematics. In this talk we will make a brief walk on this inequality, as well as on its extensions to the Lp-setting, for non-negative values of p. Then, we will move to the discrete world, either considering the integer lattice endowed with the cardinality, or working with the lattice point enumerator, which provides with the number of integer points contained in a given convex body: we will discuss and show certain discrete analogues of the above mentioned Brunn-Minkowski type inequalities in both cases. This is about joint works with Eduardo Lucas and Jesús Yepes Nicolás. *Break* *_Monday's Colloquium_: Ji Hoon Chun (Technische Universität Berlin)* *_Time_: **Monday, January 17**- 16:00 h s.t.* *_Title_: The Sausage Catastrophe **in dimension 4* *_Abstract_:* The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco. *You all are cordially invited!* -- -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------DDF8389FDBE11A37B741CB4E Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on January 17.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!
You all are cordially invited!

Location:

Online via Zoom.


Monday's Lecture: María A. Hernández Cifre (Universitdad de Murcia)

Time: Monday, January 17 - 14:15 h

Title: On discrete Brunn-Minkowski type inequalities

Abstract:

The classical Brunn-Minkowski inequality in the n-dimensional Euclidean space asserts that the volume (Lebesgue measure) to the power 1/n is a concave functional when dealing with convex bodies (non-empty compact convex sets). This result has become not only a cornerstone of the Brunn-Minkowski theory, but also a powerful tool in other related fields of mathematics.
In this talk we will make a brief walk on this inequality, as well as on its extensions to the Lp-setting, for non-negative values of p. Then, we will move to the discrete world, either considering the integer lattice endowed with the cardinality, or working with the lattice point enumerator, which provides with the number of integer points contained in a given convex body: we will discuss and show certain discrete analogues of the above mentioned Brunn-Minkowski type inequalities in both cases.
This is about joint works with Eduardo Lucas and Jesús Yepes Nicolás.


Break

Monday's Colloquium: Ji Hoon Chun (Technische Universität Berlin)

Time: Monday, January 17 - 16:00 h s.t.

Title: The Sausage Catastrophe in dimension 4

Abstract:

The Sausage Catastrophe (Jörg Wills) is the observation that in d = 3 and d = 4, the densest packing of n spheres is a sausage for small n and jumps to a full-dimensional packing for large n without passing through any intermediate dimensions. We denote the smallest value of n for which the densest packing is full-dimensional by k_d. We discuss some upper and lower bounds for k_3 and k_4, including k_3 ≤ 56 by Wills (1985) and k_4 < 375,769 by Gandini and Zucco (1992). We present some initial improvements to the upper bound for k_4 via extending the work of Gandini and Zucco.

You all are cordially invited! 
--

Virenfrei. www.avast.com
--------------DDF8389FDBE11A37B741CB4E-- From itabrunke@zedat.fu-berlin.de Wed Jan 19 18:26:59 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nAEja-002WT5-Pm; Wed, 19 Jan 2022 18:26:58 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nAEja-002r65-Mc; Wed, 19 Jan 2022 18:26:58 +0100 Received: from ip5f5af450.dynamic.kabel-deutschland.de ([95.90.244.80] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1nAEja-001RFp-CV; Wed, 19 Jan 2022 18:26:58 +0100 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 19 Jan 2022 18:26:57 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------326CB802BCCAE5BA804DFB96" X-Antivirus: Avast (VPS 220119-4, 19.1.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.244.80 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1642613218-0006CA84-51AC9EA9/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.036759, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED, HTML_IMAGE_ONLY_32,HTML_MESSAGE,T_REMOTE_IMAGE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday's Lecture Jan.24 - online via Zoom. 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, 19 Jan 2022 17:26:59 -0000 This is a multi-part message in MIME format. --------------326CB802BCCAE5BA804DFB96 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture will take place *online via Zoom* on January 24.* Please find link to Zoom Meeting here: ** **https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 * A password is *not* required! *You all are cordially invited!* *_Location_**: ** * *Online via Zoom.* *_Monday's Lecture_: Günter Rote (Freie Universität Berlin)* *_Time_: **Monday, January 24 - 14:15 h* *_Title_: The maximum number of minimal dominating sets in a tree* *_Abstract_:* A tree with n vertices has at most 95^n/13 minimal dominating sets. The growth constant λ=^13 √95≈1.4194908 is best possible. It is obtained in a semi-automatic way as a kind of "/dominant eigenvalue/" of a bilinear operation on sextuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of λ. This technique is generalizable to other counting problems, and it raises interesting questions about the "growth" of a general bilinear operation. We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions. *You all are cordially invited!* -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------326CB802BCCAE5BA804DFB96 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit Dear all,

next Monday's Lecture will take place online via Zoom on January 24.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!

You all are cordially invited!

Location:

Online via Zoom.

Monday's Lecture: Günter Rote (Freie Universität Berlin)

Time: Monday, January 24 - 14:15 h

Title: The maximum number of minimal dominating sets in a tree

Abstract:

A tree with n vertices has at most 95n/13 minimal dominating sets. The growth constant λ=13√95≈1.4194908 is best possible. It is obtained in a semi-automatic way as a kind of "dominant eigenvalue" of a bilinear operation on sextuples that is derived from the dynamic-programming recursion for computing the number of minimal dominating sets of a tree. The core of the method tries to enclose a set of sextuples in a six-dimensional geometric body with certain properties, which depend on some putative value of λ. This technique is generalizable to other counting problems, and it raises interesting questions about the "growth" of a general bilinear operation.

We also derive an output-sensitive algorithm for listing all minimal dominating sets with linear set-up time and linear delay between successive solutions.


You all are cordially invited!


Virenfrei. www.avast.com
--------------326CB802BCCAE5BA804DFB96-- From itabrunke@zedat.fu-berlin.de Wed Jan 26 16:03:50 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nCjpu-003jed-60; Wed, 26 Jan 2022 16:03:50 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nCjpt-002VVc-FT; Wed, 26 Jan 2022 16:03:49 +0100 Received: from [95.90.243.185] (helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1nCjpt-003Yyt-54; Wed, 26 Jan 2022 16:03:49 +0100 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 26 Jan 2022 16:03:48 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------03D02541362135FF76D80A2C" X-Antivirus: Avast (VPS 220126-4, 26.1.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.243.185 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1643209430-00086027-8EE10F99/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,HTML_MESSAGE, T_REMOTE_IMAGE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday's Lecture & Colloquium Jan.31 - online via Zoom. 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, 26 Jan 2022 15:03:50 -0000 This is a multi-part message in MIME format. --------------03D02541362135FF76D80A2C Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place *online via Zoom* on January 31.* Please find link to Zoom Meeting here: ** **https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 * A password is not required!* *** *You all are cordially invited!* *_Location_**: ** * *Online via Zoom.* *_Monday's Lecture_: George Mertzios (Durham University)* *_Time_: **Monday, January 31 - 14:15 h* *_Title_: Algorithmic Problems on Temporal Graphs* *_Abstract_:* A temporal graph is a graph whose edge set changes over a sequence of discrete time steps. This can be viewed as a discrete sequence G_1, G_2, ... of static graphs, each with a fixed vertex set V. Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different, and often substantially more difficult, when the time dimension is additionally taken into account. In this talk we will discuss some natural but only recently introduced temporal problems and some algorithmic approaches to them. *Break* *_Monday's Colloquium_: Klaus Heeger (Technische Universität Berlin)* *_Time_: **Monday, January 31**- 16:00 h s.t.* *_Title_: Stable Matchings Beyond Stable Marriage* *_Abstract_:* Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar". *You all are cordially invited!* -- -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------03D02541362135FF76D80A2C Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on January 31.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!
You all are cordially invited!

Location:

Online via Zoom.


Monday's Lecture: George Mertzios (Durham University)

Time: Monday, January 31 - 14:15 h

Title: Algorithmic Problems on Temporal Graphs

Abstract:

A temporal graph is a graph whose edge set changes over a sequence of discrete time steps. This can be viewed as a discrete sequence G_1, G_2, ... of static graphs, each with a fixed vertex set V. Research in this area is motivated by the fact that many modern systems are highly dynamic and relations (edges) between objects (vertices) vary with time. Although static graphs have been extensively studied for decades from an algorithmic point of view, we are still far from having a concrete set of structural and algorithmic principles for temporal graphs. Many notions and algorithms from the static case can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. In particular, some problems become radically different, and often substantially more difficult, when the time dimension is additionally taken into account. In this talk we will discuss some natural but only recently introduced temporal problems and some algorithmic approaches to them.


Break

Monday's Colloquium: Klaus Heeger (Technische Universität Berlin)

Time: Monday, January 31 - 16:00 h s.t.

Title: Stable Matchings Beyond Stable Marriage

Abstract:

Stable matchings are well-studied from computer science, mathematics, and economics. In the most basic setting, called Stable Marriage, there are two sets of agents. Each agent from one set has preferences over the agents from the other set. A matching assigns the agents into groups of two agents. A matching is called stable if there are no two agents preferring each other to the partners assigned to them. In this talk, we will review important parts of my forthcoming PhD thesis concerning the computational complexity of two extensions of this basic model: First, we assume that an instance of Stable Marriage is given, and the aim is to modify the instance (using as few "modifications" as possible) such that a given edge is part of some stable matching. Second, we assume that agents have preferences over sets of d-1 other agents (for some d>2). In this case, a matching matches agents into groups of size d, and a matching is stable if there are no d agents preferring to be matched together to being unmatched. While since 1991 this problem is known to be NP-complete, we study the case that the preferences of all agents are "similar".

You all are cordially invited! 
--

Virenfrei. www.avast.com
--------------03D02541362135FF76D80A2C-- From itabrunke@zedat.fu-berlin.de Wed Feb 02 18:10:00 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nFJ8q-000BMa-4N; Wed, 02 Feb 2022 18:10:00 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nFJ8p-000qWn-AB; Wed, 02 Feb 2022 18:09:59 +0100 Received: from ip5f5af673.dynamic.kabel-deutschland.de ([95.90.246.115] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1nFJ8p-000Kzm-18; Wed, 02 Feb 2022 18:09:59 +0100 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de, Neil Olver , Manuel Radons Message-ID: <63b682c2-fcb1-fea5-2a13-6c756f3f3a4b@fu-berlin.de> Date: Wed, 2 Feb 2022 18:09:58 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------B5D5BF46D67DC54F118CC3FD" X-Antivirus: Avast (VPS 220202-0, 2.2.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.246.115 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1643821800-00000547-D0E68B94/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.028035, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE,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's Lecture & Colloquium Feb.7 - online via Zoom. 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, 02 Feb 2022 17:10:00 -0000 This is a multi-part message in MIME format. --------------B5D5BF46D67DC54F118CC3FD Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place *online via Zoom* on February 7.* Please find link to Zoom Meeting here: ** **https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 * A password is not required!* *** *You all are cordially invited!* *_Location_**: ** * *Online via Zoom.* *_Monday's Lecture_: Neil Olver (London School of Economics and Political Science)* *_Time_: **Monday, February 7 - 14:15 h* *_Title_: Continuity, Uniqueness and Long-Term Behaviour of Nash Flows Over Time* *_Abstract_:* We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modelled via queues, which form whenever the inflow into a link exceeds its capacity. We answer some rather basic questions about equilibria in this model: in particular /uniqueness/ (in an appropriate sense), and /continuity/: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions. To prove these results, we make a surprising connection to another question: whether, assuming constant inflow into the network at the source, do equilibria always eventually settle into a "steady state" where all queue delays change linearly forever more? Cominetti et al. proved this under an assumption that the inflow rate is not larger than the capacity of the network - eventually, queues remain constant forever. We resolve the more general question positively. (Joint work with Leon Sering and Laura Vargas Koch). *Break* *_Monday's Colloquium_: Manuel Radons (Technische Universität Berlin)* *_Time_: **Monday, February 7**- 16:00 h s.t.* *_Title_: Nearly flat polytopes in the context of Dürer's problem* *_Abstract_:* Dürer's problem asks whether every 3-polytope P has a net. Is there always a spanning tree T of its edge graph, so that if we cut P along T the resulting surface can be unfolded into the plane without self-overlaps? A common technique in recent works is to fix a spanning tree and then study the deformations of the corresponding unfolding induced by an affine stretching or flattening of P. In the first part of my talk I will highlight landmark results by Ghomi, O'Rourke and Tarasov that emanated from this approach. In the second part I will present my own work on the unfoldability of nested prismatoids, which follows a similar ansatz. *You all are cordially invited!* -- -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------B5D5BF46D67DC54F118CC3FD Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on February 7.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!
You all are cordially invited!

Location:

Online via Zoom.


Monday's Lecture: Neil Olver (London School of Economics and Political Science)

Time: Monday, February 7 - 14:15 h

Title: Continuity, Uniqueness and Long-Term Behaviour of Nash Flows Over Time

Abstract:

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from a source to destination as quickly as possible. Flow patterns vary over time, and congestion effects are modelled via queues, which form whenever the inflow into a link exceeds its capacity. We answer some rather basic questions about equilibria in this model: in particular uniqueness (in an appropriate sense), and continuity: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions.

To prove these results, we make a surprising connection to another question: whether, assuming constant inflow into the network at the source, do equilibria always eventually settle into a "steady state" where all queue delays change linearly forever more? Cominetti et al. proved this under an assumption that the inflow rate is not larger than the capacity of the network - eventually, queues remain constant forever. We resolve the more general question positively.

(Joint work with Leon Sering and Laura Vargas Koch).


Break

Monday's Colloquium: Manuel Radons (Technische Universität Berlin)

Time: Monday, February 7 - 16:00 h s.t.

Title: Nearly flat polytopes in the context of Dürer's problem

Abstract:

Dürer's problem asks whether every 3-polytope P has a net. Is there always a spanning tree T of its edge graph, so that if we cut P along T the resulting surface can be unfolded into the plane without self-overlaps? A common technique in recent works is to fix a spanning tree and then study the deformations of the corresponding unfolding induced by an affine stretching or flattening of P. In the first part of my talk I will highlight landmark results by Ghomi, O'Rourke and Tarasov that emanated from this approach. In the second part I will present my own work on the unfoldability of nested prismatoids, which follows a similar ansatz.

You all are cordially invited! 
--

Virenfrei. www.avast.com
--------------B5D5BF46D67DC54F118CC3FD-- From itabrunke@zedat.fu-berlin.de Tue Feb 08 16:58:35 2022 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nHSsx-00457P-0N; Tue, 08 Feb 2022 16:58:31 +0100 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from ) id 1nHSsw-000LjI-Tx; Tue, 08 Feb 2022 16:58:30 +0100 Received: from [95.90.244.135] (helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1nHSsw-001WeG-JT; Tue, 08 Feb 2022 16:58:30 +0100 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Tue, 8 Feb 2022 16:58:30 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.2 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------28DEB4948E24B457586F0BBC" X-Antivirus: Avast (VPS 220208-2, 8.2.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.244.135 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1644335911-00000498-755A2A09/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000570, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE,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's Lecture & Colloquium Feb.14 - online via Zoom. 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, 08 Feb 2022 15:58:35 -0000 This is a multi-part message in MIME format. --------------28DEB4948E24B457586F0BBC Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place *online via Zoom* on February 14.* Please find link to Zoom Meeting here: ** **https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 * A password is not required!* *** *You all are cordially invited!* *_Location_**: ** * *Online via Zoom.* *_Monday's Lecture_: Carlos Amendola (Technische Universität München)* *_Time_: **Monday, February 14 - 14:15 h* *_Title_: Estimating Gaussian mixtures using sparse polynomial moment systems* *_Abstract_:* The method of moments is a statistical technique for density estimation that solves a system of moment equations to estimate the parameters of an unknown distribution. A fundamental question critical to understanding identifiability asks how many moment equations are needed to get finitely many solutions and how many solutions there are. Since the moments of a mixture of Gaussians are polynomial expressions in the means, variances and mixture weights, one can address this question from the perspective of algebraic geometry. With the help of tools from polyhedral geometry, we answer this fundamental question for several classes of Gaussian mixture models. Furthermore, these results allow us to present an algorithm that performs parameter recovery and density estimation, applicable even in the high dimensional case. Based on joint work with Julia Lindberg and Jose Rodriguez (University of Wisconsin-Madison). *Break* *_Monday's Colloquium_: Marie Brandenburg (Max Planck Institut Leipzig)* *_Time_: **Monday, February 14**- 16:00 h s.t.* *_Title_: Intersection Bodies of Polytopes* *_Abstract_:* Intersection bodies are classical objects from convex geometry, that are constructed from given convex body. In the past, they have mainly been studied from the point of view of convex analysis. In this talk we investigate combinatorial and algebraic structures of intersection bodies of polytopes. We consider an algorithm to compute both the radial function and the algebraic boundary of these intersection bodies, and provide an upper bound for their degree. This is joint work with Katalin Berlow, Chiara Meroni and Isabelle Shankar. *You all are cordially invited!* -- -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------28DEB4948E24B457586F0BBC Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit Dear all,

next Monday's Lecture and Colloquium will take place online via Zoom on February 14.

Please find link to Zoom Meeting here:

https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09

A password is not required!
You all are cordially invited!

Location:

Online via Zoom.


Monday's Lecture: Carlos Amendola (Technische Universität München)

Time: Monday, February 14 - 14:15 h

Title: Estimating Gaussian mixtures using sparse polynomial moment systems

Abstract:

The method of moments is a statistical technique for density estimation that solves a system of moment equations to estimate the parameters of an unknown distribution. A fundamental question critical to understanding identifiability asks how many moment equations are needed to get finitely many solutions and how many solutions there are. 

Since the moments of a mixture of Gaussians are polynomial expressions in the means, variances and mixture weights, one can address this question from the perspective of algebraic geometry. With the help of tools from polyhedral geometry, we answer this fundamental question for several classes of Gaussian mixture models. Furthermore, these results allow us to present an algorithm that performs parameter recovery and density estimation, applicable even in the high dimensional case.

Based on joint work with Julia Lindberg and Jose Rodriguez (University of Wisconsin-Madison).


Break

Monday's Colloquium: Marie Brandenburg (Max Planck Institut Leipzig)

Time: Monday, February 14 - 16:00 h s.t.

Title: Intersection Bodies of Polytopes

Abstract:

Intersection bodies are classical objects from convex geometry, that are constructed from given convex body. In the past, they have mainly been studied from the point of view of convex analysis. In this talk we investigate combinatorial and algebraic structures of intersection bodies of polytopes. We consider an algorithm to compute both the radial function and the algebraic boundary of these intersection bodies, and provide an upper bound for their degree. This is joint work with Katalin Berlow, Chiara Meroni and Isabelle Shankar.

You all are cordially invited! 
--

Virenfrei. www.avast.com
--------------28DEB4948E24B457586F0BBC-- From itabrunke@zedat.fu-berlin.de Wed Apr 27 01:17:54 2022 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 1njURN-0008Sb-Kg; Wed, 27 Apr 2022 01:17:54 +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 1njURL-0017d1-V5; Wed, 27 Apr 2022 01:17:51 +0200 Received: from ip5f5af706.dynamic.kabel-deutschland.de ([95.90.247.6] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1njURL-0027PW-JE; Wed, 27 Apr 2022 01:17:51 +0200 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: <33f83d25-6991-1bc9-7e06-7e3f0f5a97d4@fu-berlin.de> Date: Wed, 27 Apr 2022 01:17:59 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.11.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------C8349726656C04829AF028BF" X-Antivirus: Avast (VPS 220426-4, 26.4.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.247.6 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1651015073-0000DE99-354A6199/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.181402, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday's Lecture & Colloquium May 2 - back in attendance. 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, 26 Apr 2022 23:17:54 -0000 This is a multi-part message in MIME format. --------------C8349726656C04829AF028BF Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on May 2, back in attendance, at 14:15 h & 16:00 h at HU Berlin. *You all are cordially invited. * *_Location_**: ** * *Humboldt-Kabinett - between House 3&4 *Johann von Neumann-Haus - 1st Floor [British Reading] Humboldt-Universität zu Berlin Rudower Chaussee 25 12489 Berlin *_Time_: **Monday, May 2 - 14:15* *_Lecture_: Tomáš Masarik (Charles University Prague)* *_Title_: Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument* *_Abstract_:* We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw St,t,t as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2O(n√logn) and a quasipolynomial-time approximation scheme with improved running time 2O(ε−1log5n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in Pt-free graphs, ensures that given an n-vertex Pt-free graph, in polynomial time we can find a set P of at most t−1 vertices, such that every connected component of G−N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for St,t,t-free graphs: given an n-vertex St,t,t-free graph, in polynomial time we can find a set P of O(tlogn) vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G−N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices. In the talk, we first show how Gyárfás' path argument works on Pt-free graphs. Then we will sketch-prove our main result with as few technical details as possible. Joint work with: Konrad Majewski, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski _*Coffee & Tea Break*_*:* outside *Humboldt-Kabinett - between House 3&4 *Johann von Neumann-Haus - 1st Floor [British Reading] ** *_Time_: **Monday, May 2 **- 16:00 s.t.* *_Colloquium_: Jana Novotna (University of Warsaw)* *_Title_: Taming Creatures * *_Abstract_:* A graph class is tame if it admits a polynomial bound on the number of minimal separators, and feral if it contains infinitely many graphs with exponential number of minimal separators. The former entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set, and many other problems, when restricted to an input graph from a tame class, by a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015]. In the talk, we show a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame and feral. To obtain the full dichotomy, we confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class C there exists a constant k such that no member of C contains a k-creature or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every graph G from C contains at most p(|V(G)|) minimal separators. Joint work with Jakub Gajarský, Lars Jafke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------C8349726656C04829AF028BF Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on May 2, back in attendance, at 14:15 h & 16:00 h at HU Berlin.

You all are cordially invited.

Location:

Humboldt-Kabinett - between House 3&4
Johann von Neumann-Haus - 1st Floor [British Reading]
Humboldt-Universität zu Berlin
Rudower Chaussee 25
12489 Berlin 

Time: Monday, May 2 - 14:15

Lecture: Tomáš Masarik (Charles University Prague)

Title: Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument

Abstract:

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw St,t,t as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2O(n√logn) and a quasipolynomial-time approximation scheme with improved running time 2O(ε−1log5n).

The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in Pt-free graphs, ensures that given an n-vertex Pt-free graph, in polynomial time we can find a set P of at most t−1 vertices, such that every connected component of G−N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for St,t,t-free graphs: given an n-vertex St,t,t-free graph, in polynomial time we can find a set P of O(tlogn) vertices and
an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G−N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices.

In the talk, we first show how Gyárfás' path argument works on Pt-free graphs. Then we will sketch-prove our main result with as few technical details as possible.

Joint work with: Konrad Majewski, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski


Coffee & Tea Break :

outside Humboldt-Kabinett - between House 3&4
Johann von Neumann-Haus - 1st Floor [British Reading]


Time: Monday, May 2 - 16:00 s.t.

Colloquium: Jana Novotna (University of Warsaw)

Title: Taming Creatures

Abstract:

A graph class is tame if it admits a polynomial bound on the number of minimal separators, and feral if it contains infinitely many graphs with exponential number of minimal separators. The former entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set, and many other problems, when restricted to an input graph from a tame class, by a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015]. 
In the talk, we show a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame and feral. To obtain the full dichotomy, we confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class C there exists a constant k such that no member of C contains a k-creature or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every graph G from C contains at most p(|V(G)|) minimal separators. 
Joint work with Jakub Gajarský, Lars Jafke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza.


Virenfrei. www.avast.com
--------------C8349726656C04829AF028BF-- From kratsch@informatik.hu-berlin.de Mon May 02 13:49:22 2022 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) 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 1nlUYL-0008HQ-MT; Mon, 02 May 2022 13:49:21 +0200 Received: from mailout1.informatik.hu-berlin.de ([141.20.20.101]) by relay1.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 1nlUYL-002pCZ-Jm; Mon, 02 May 2022 13:49:21 +0200 Received: from mailbox.informatik.hu-berlin.de (mailbox [141.20.20.63]) by mail.informatik.hu-berlin.de (8.15.1/8.15.1/INF-2.0-MA-SOLARIS-2.10-25) with ESMTPS id 242Bn3Lw024827 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL) for ; Mon, 2 May 2022 13:49:04 +0200 (MEST) Received: from [10.5.33.163] ([141.20.217.9]) (authenticated bits=0) by mailbox.informatik.hu-berlin.de (8.15.1/8.15.1/INF-2.0-MA-SOLARIS-2.10-AUTH-26-465-587) with ESMTPSA id 242Bn3CF024822 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=OK); Mon, 2 May 2022 13:49:03 +0200 (MEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=informatik.hu-berlin.de; s=mailbox; t=1651492143; bh=Sm2VVPIL+pkNgY0i7VI1JGHFx1VLjRMT0kuvDZ+yD/Q=; h=Date:To:From:Subject; b=mX27lD0Ye5DzyTNUMUMw7526ZeoNF2+PfTClzx2jWNyRljJ2cYQRfflAjmyDEIbx7 Ixwz+zrD9qoXuzSvV0ZeNaIBac8qxgEY+BeZSn1281DxdoS0YnHCuygbOLYwkdUkCB NAEi0RS2q7M5KzwoB2SID6cQOCcMWhV0DJ++d1HI= Message-ID: <0034370d-bcea-ae92-0a8b-9849b699aaf3@informatik.hu-berlin.de> Date: Mon, 2 May 2022 13:49:01 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.8.1 To: facets-of-complexity@lists.fu-berlin.de From: Stefan Kratsch Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg=sha-512; boundary="------------ms030706070400010701080403" X-Virus-Scanned: clamav-milter 0.103.5 at mailbox X-Virus-Status: Clean X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.1 (mail.informatik.hu-berlin.de [141.20.20.50]); Mon, 02 May 2022 13:49:04 +0200 (MEST) X-Originating-IP: 141.20.20.101 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1651492161-00059D48-654B49B4/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000070, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-2.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,RCVD_IN_DNSWL_MED,SPF_HELO_NONE,SPF_PASS, 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] Zoom for today 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, 02 May 2022 11:49:22 -0000 This is a cryptographically signed message in MIME format. --------------ms030706070400010701080403 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, here is the Zoom Meeting for those who cannot make it in person. Best, Stefan -- Thema: Talk T. Masařík / J. Novotna Uhrzeit: 2.Mai.2022 02:00 PM Amsterdam, Berlin, Rom, Stockholm, Wien Zoom-Meeting beitreten https://hu-berlin.zoom.us/j/64124015166?pwd=VmtKM21jN2l2cktKUGxZY20va1E1dz09 Meeting-ID: 641 2401 5166 Passwort: 668789 --------------ms030706070400010701080403 Content-Type: application/pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="smime.p7s" Content-Description: S/MIME Cryptographic Signature MIAGCSqGSIb3DQEHAqCAMIACAQExDzANBglghkgBZQMEAgMFADCABgkqhkiG9w0BBwEAAKCC Dk4wggbmMIIEzqADAgECAhAxAnDUNb6bJJr4VtDh4oVJMA0GCSqGSIb3DQEBDAUAMIGIMQsw CQYDVQQGEwJVUzETMBEGA1UECBMKTmV3IEplcnNleTEUMBIGA1UEBxMLSmVyc2V5IENpdHkx HjAcBgNVBAoTFVRoZSBVU0VSVFJVU1QgTmV0d29yazEuMCwGA1UEAxMlVVNFUlRydXN0IFJT QSBDZXJ0aWZpY2F0aW9uIEF1dGhvcml0eTAeFw0yMDAyMTgwMDAwMDBaFw0zMzA1MDEyMzU5 NTlaMEYxCzAJBgNVBAYTAk5MMRkwFwYDVQQKExBHRUFOVCBWZXJlbmlnaW5nMRwwGgYDVQQD ExNHRUFOVCBQZXJzb25hbCBDQSA0MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEA s0riIl4nW+kEWxQENTIgFK600jFAxs1QwB6hRMqvnkphfy2Q3mKbM2otpELKlgE8/3AQPYBo 7p7yeORuPMnAuA+oMGRb2wbeSaLcZbpwXgfCvnKxmq97/kQkOFX706F9O7/h0yehHhDjUdyM yT0zMs4AMBDRrAFn/b2vR3j0BSYgoQs16oSqadM3p+d0vvH/YrRMtOhkvGpLuzL8m+LTAQWv QJ92NwCyKiHspoP4mLPJvVpEpDMnpDbRUQdftSpZzVKTNORvPrGPRLnJ0EEVCHR82LL6oz91 5WkrgeCY9ImuulBn4uVsd9ZpubCgM/EXvVBlViKqusChSsZEn7juIsGIiDyaIhhLsd3amm8B S3bgK6AxdSMROND6hiHT182Lmf8C+gRHxQG9McvG35uUvRu8v7bPZiJRaT7ZC2f50P4lTlnb LvWpXv5yv7hheO8bMXltiyLweLB+VNvg+GnfL6TW3Aq1yF1yrZAZzR4MbpjTWdEdSLKvz8+0 wCwscQ81nbDOwDt9vyZ+0eJXbRkWZiqScnwAg5/B1NUD4TrYlrI4n6zFp2pyYUOiuzP+as/A Znz63GvjFK69WODR2W/TK4D7VikEMhg18vhuRf4hxnWZOy0vhfDR/g3aJbdsGac+diahjEwz yB+UKJOCyzvecG8bZ/u/U8PsEMZg07iIPi8CAwEAAaOCAYswggGHMB8GA1UdIwQYMBaAFFN5 v1qqK0rPVIDh2JvAnfKyA2bLMB0GA1UdDgQWBBRpAKHHIVj44MUbILAK3adRvxPZ5DAOBgNV HQ8BAf8EBAMCAYYwEgYDVR0TAQH/BAgwBgEB/wIBADAdBgNVHSUEFjAUBggrBgEFBQcDAgYI KwYBBQUHAwQwOAYDVR0gBDEwLzAtBgRVHSAAMCUwIwYIKwYBBQUHAgEWF2h0dHBzOi8vc2Vj dGlnby5jb20vQ1BTMFAGA1UdHwRJMEcwRaBDoEGGP2h0dHA6Ly9jcmwudXNlcnRydXN0LmNv bS9VU0VSVHJ1c3RSU0FDZXJ0aWZpY2F0aW9uQXV0aG9yaXR5LmNybDB2BggrBgEFBQcBAQRq MGgwPwYIKwYBBQUHMAKGM2h0dHA6Ly9jcnQudXNlcnRydXN0LmNvbS9VU0VSVHJ1c3RSU0FB ZGRUcnVzdENBLmNydDAlBggrBgEFBQcwAYYZaHR0cDovL29jc3AudXNlcnRydXN0LmNvbTAN BgkqhkiG9w0BAQwFAAOCAgEACgVOew2PHxM5AP1v7GLGw+3tF6rjAcx43D9Hl110Q+BABABg lkrPkES/VyMZsfuds8fcDGvGE3o5UfjSno4sij0xdKut8zMazv8/4VMKPCA3EUS0tDUoL01u gDdqwlyXuYizeXyH2ICAQfXMtS+raz7mf741CZvO50OxMUMxqljeRfVPDJQJNHOYi2pxuxgj KDYx4hdZ9G2o+oLlHhu5+anMDkE8g0tffjRKn8I1D1BmrDdWR/IdbBOj6870abYvqys1qYlP otv5N5dm+XxQ8vlrvY7+kfQaAYeO3rP1DM8BGdpEqyFVa+I0rpJPhaZkeWW7cImDQFerHW9b KzBrCC815a3WrEhNpxh72ZJZNs1HYJ+29NTB6uu4NJjaMxpk+g2puNSm4b9uVjBbPO9V6sFS G+IBqE9ckX/1XjzJtY8Grqoo4SiRb6zcHhp3mxj3oqWi8SKNohAOKnUc7RIP6ss1hqIFyv0x XZor4N9tnzD0Fo0JDIURjDPEgo5WTdti/MdGTmKFQNqxyZuT9uSI2Xvhz8p+4pCYkiZqpahZ lHqMFxdw9XRZQgrP+cgtOkWEaiNkRBbvtvLdp7MCL2OsQhQEdEbUvDM9slzZXdI7NjJokVBq 3O4pls3VD2z3L/bHVBe0rBERjyM2C/HSIh84rfmAqBgklzIOqXhd+4RzadUwggdgMIIFSKAD AgECAhEAjW1HDU2wQR7DFNyO7KBvVzANBgkqhkiG9w0BAQwFADBGMQswCQYDVQQGEwJOTDEZ MBcGA1UEChMQR0VBTlQgVmVyZW5pZ2luZzEcMBoGA1UEAxMTR0VBTlQgUGVyc29uYWwgQ0Eg NDAeFw0yMjA0MDUwMDAwMDBaFw0yNTA0MDQyMzU5NTlaMIG+MQ4wDAYDVQQREwUxMDA5OTEo MCYGA1UEChMfSHVtYm9sZHQtVW5pdmVyc2l0YWV0IHp1IEJlcmxpbjEbMBkGA1UECRMSVW50 ZXIgZGVuIExpbmRlbiA2MQ8wDQYDVQQIEwZCZXJsaW4xCzAJBgNVBAYTAkRFMRcwFQYDVQQD Ew5TdGVmYW4gS3JhdHNjaDEuMCwGCSqGSIb3DQEJARYfa3JhdHNjaEBpbmZvcm1hdGlrLmh1 LWJlcmxpbi5kZTCCAiIwDQYJKoZIhvcNAQEBBQADggIPADCCAgoCggIBALQXQAQ+j/qIqlI8 hrFChd8laACsoRTQkE0aPBBfCCCVN5htwVAmid55rQTw7v1xWkcxrkAcPLpo4jkapwUMCHhu pEJ++v6yORuAZ27J4q8GnvUa76TkefE044sSzazz+cLUP+RYCjIZCDIU8tjpEeWeCE3HhWwC XUMtpVnQgDYrHnLxl2xA6Vpr8i1e4ZyKMFbKb8JUgUQjl/z8iTfi5MK8wVqUKl1J4Um0ghWe JoaiIEmleVuYKh+8pGyzt7irPj6Kg4DW+AHNavcQRztxnpZfrSMUCxh2b+2JvoZQ/ObaiF2i ZjFSfOGngmHTpw+XVfJrne5JWvWqfFZNmqDQ9TnFFZAumsRWBpgPFuKAs1d4nsiAJVOc3Z8s NSpdKJ38hjiq0tQxzzCGvgE4hzwWkJZ7Wx0Eaen93y4lIBk+/3eWEs7EHguqFOn1vRNbZoNz 642B0RJzcolGG87s0PwBphzcEytVwm3GlABrJdUg3m4n3h5durHWrhLb6T6IL2IUY9Lz+YM9 ksVHgz1W4jo4AmKbN8OKBBDZecdDtQFAqEqvTqJHTrUYrBQeOAhd5sNx03+5wCFQCOWj99aA j3+eqV9Xoi6CydPKSMFmy9ikOotsRjo6er7kF59BzeF8lB2mNPD1gMLNkVxVmOSsKBHSfbPT 5IRRVGmZc5EdmDuTALB1AgMBAAGjggHOMIIByjAfBgNVHSMEGDAWgBRpAKHHIVj44MUbILAK 3adRvxPZ5DAdBgNVHQ4EFgQUiZW5W0arG+5OU+L9Ra1YelJAc1MwDgYDVR0PAQH/BAQDAgWg MAwGA1UdEwEB/wQCMAAwHQYDVR0lBBYwFAYIKwYBBQUHAwQGCCsGAQUFBwMCMD8GA1UdIAQ4 MDYwNAYLKwYBBAGyMQECAk8wJTAjBggrBgEFBQcCARYXaHR0cHM6Ly9zZWN0aWdvLmNvbS9D UFMwQgYDVR0fBDswOTA3oDWgM4YxaHR0cDovL0dFQU5ULmNybC5zZWN0aWdvLmNvbS9HRUFO VFBlcnNvbmFsQ0E0LmNybDB4BggrBgEFBQcBAQRsMGowPQYIKwYBBQUHMAKGMWh0dHA6Ly9H RUFOVC5jcnQuc2VjdGlnby5jb20vR0VBTlRQZXJzb25hbENBNC5jcnQwKQYIKwYBBQUHMAGG HWh0dHA6Ly9HRUFOVC5vY3NwLnNlY3RpZ28uY29tMEwGA1UdEQRFMEOBIGtyYXRzY2hzQGlu Zm9ybWF0aWsuaHUtYmVybGluLmRlgR9rcmF0c2NoQGluZm9ybWF0aWsuaHUtYmVybGluLmRl MA0GCSqGSIb3DQEBDAUAA4ICAQCfuIFju0dQHPc5gwJOaaErse5TFwK8zrfpJaYhKdyO+mWF kTPFZGqtao7LtXr5JEtIW4YbgEJlThv/KbsiJ9AsqU0uyG3JiAhqrvNF9BAG1SPcebbJCXWs qfEYUjFvanrrTRY50VdN3QEEvpDed0mzwuxUX9Rtif5krdgx0eyfC/6r+xw4cdGEKERvVOt3 VnEQ6qQNCfYrpFJDWxo49AirgjadEndkG89UveHh+w4WMffqo2HkO1PfRKoQjHhHA3sARcXH GM7dNSKcB8qFCzvpt54rCQLiU3xD9Qu6PrziGzrIRP+ozjM/k6kZ7LkxkyzgNNItL3kuiABB eKLzwzdunMmWlq1SVmIy0VCYgprrFDWJQAujgfI+AAdFl7VSP3wJ1OId8s3fEbN/TN52UULT hxfvsfH3L7sjiAlbmQVeAa3+OFi6v5xMGCHfEcwweSxihSH37wOH5BshCDm6d504PAcUY516 WCNpP/tYa8umHjQGCa5d1ymTBeIdNSRHl5H+TX9xUv2s1C3erb/wOuyMJlNAhZ6sOPlMft2j fowGfwj6JoqSdEMM2zyoZFFeb07gkcK3Ntu1UaA0WxnF62sjehIjcQorHhexH0y6ZXkj0zE7 cHz2b+is1dCR7Kc3Q/IQE/8kpT2xKvF9tsmzIc68FshZAY6jfyKZMm/OiQ2wozGCBFswggRX AgEBMFswRjELMAkGA1UEBhMCTkwxGTAXBgNVBAoTEEdFQU5UIFZlcmVuaWdpbmcxHDAaBgNV BAMTE0dFQU5UIFBlcnNvbmFsIENBIDQCEQCNbUcNTbBBHsMU3I7soG9XMA0GCWCGSAFlAwQC AwUAoIIB0TAYBgkqhkiG9w0BCQMxCwYJKoZIhvcNAQcBMBwGCSqGSIb3DQEJBTEPFw0yMjA1 MDIxMTQ5MDJaME8GCSqGSIb3DQEJBDFCBECworL2GJj0cFSQesON0MsMo5hUvqGg48t9swl1 vJQMuu8FZvMZiHZ/fuY71cA7tghWFSMjgcdjNjtv+dLy9mDhMGoGCSsGAQQBgjcQBDFdMFsw RjELMAkGA1UEBhMCTkwxGTAXBgNVBAoTEEdFQU5UIFZlcmVuaWdpbmcxHDAaBgNVBAMTE0dF QU5UIFBlcnNvbmFsIENBIDQCEQCNbUcNTbBBHsMU3I7soG9XMGwGCSqGSIb3DQEJDzFfMF0w CwYJYIZIAWUDBAEqMAsGCWCGSAFlAwQBAjAKBggqhkiG9w0DBzAOBggqhkiG9w0DAgICAIAw DQYIKoZIhvcNAwICAUAwBwYFKw4DAgcwDQYIKoZIhvcNAwICASgwbAYLKoZIhvcNAQkQAgsx XaBbMEYxCzAJBgNVBAYTAk5MMRkwFwYDVQQKExBHRUFOVCBWZXJlbmlnaW5nMRwwGgYDVQQD ExNHRUFOVCBQZXJzb25hbCBDQSA0AhEAjW1HDU2wQR7DFNyO7KBvVzANBgkqhkiG9w0BAQEF AASCAgBcFkuT2Jl9KP4ZrVD9jI32+hqwA43nqKzj3B/NzrO4IXVYBot4oVwaixNQszV2AyYK CloG9/JgGEDfRHtXpBPH8UsJnSCEZ1RodJA/eZ+2ZqGrFt63rWLcWAZ7bzWDc9Jr8PVe6y0L wlhSUq0YlKWZ++UWB5Ke1MnG3PrvsPYvc3Vq0FIEKBaO0rrDLHKXB1i/ycrS9kMQKLS5kOdD CkxBl/Iyr/QmtjtcK3nUU5JYM2KDgJWNBGGMe0zDo0y3TC7SHxuxZzN+2YWlWDzecRxv9GcM HujQjjFlIN26r/JOqxu9f15izQf3W3qM6cUJciUBUyDV4937QqkR6sBVluaRbphcOm1zqfMy fndxdpgj0Lm0xQkLiwDVGpRz79ENKHLzczVnzfepw4DwY1H63w0TtM3Var7R9qGXO8Smjnzl j+DzButiU2+NLR8muCAP94EmWnzVFbxJBt0SCfRXy72RyhJ5KUqHl2RFu4O+7rDv+6l06K9O dpaIt3Yu9hoAoLjNaozxQq/j4cy8vjvqstLIJgE+C+iRs4S0/IGFyyb+t284J/Uqw8QBYGQf RNAoCVqMN8NqapVtDpQTyDBv7KMb/tgb/WO3ztlubJn9zAlr79T1qaJqSsbvc8/t73udP92I n79cdwo4ePrG8quh/F+ODmAvBQw8neqBnD+hwy46rQAAAAAAAA== --------------ms030706070400010701080403-- From itabrunke@zedat.fu-berlin.de Tue May 03 17:09:38 2022 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 1nlu9e-0039dm-6E; Tue, 03 May 2022 17:09:34 +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 1nlu9d-0032Hr-D6; Tue, 03 May 2022 17:09:33 +0200 Received: from ip5f5af4e2.dynamic.kabel-deutschland.de ([95.90.244.226] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1nlu9c-002Ppr-SI; Tue, 03 May 2022 17:09:33 +0200 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Tue, 3 May 2022 17:09:32 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.11.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------6B1DC146A114C923589E50D3" X-Antivirus: Avast (VPS 220503-6, 3.5.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.244.226 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1651590574-00013334-FFD28D24/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000019, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE,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's Lecture & Colloquium May 9. 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, 03 May 2022 15:09:38 -0000 This is a multi-part message in MIME format. --------------6B1DC146A114C923589E50D3 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on May 9, back in attendance, at 14:15 & 16:00 at FU Berlin. There will also be a Zoom link for those who can not make it in attendance. Invitation link for Zoom meeting: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *You all are cordially invited. * *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, May 9 - 14:15* *_Lecture_: Andrew Newman (Carnegie Mellon University, Pittsburgh)* *_Title_: Complexes of nearly maximum diameter* *_Abstract_:* The combinatorial diameter of a simplicial complex is the diameter of its dual graph. Using a probabilistic approach we determine the right first-order asymptotics for the maximum possible diameter among all d-complexes on n vertices as well as among all d-pseudomanifolds on n vertices. This is joint work with Tom Bohman. _*Coffee & Tea Break*_*:* *Room 134 - 1st Floor * ** *_Time_: **Monday, May 9 **- 16:00 s.t.* *_Colloquium_: Marcel Celaya (ETH, Zürich)* *_Title_: Improving the Cook et al. Proximity Bound Given Integral Valued Constraints* *_Abstract_:* Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel. -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------6B1DC146A114C923589E50D3 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on May 9, back in attendance, at 14:15 & 16:00 at FU Berlin. There will also be a Zoom link for those who can not make it in attendance.

Invitation link for Zoom meeting:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password is required.

You all are cordially invited.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, May 9 - 14:15

Lecture: Andrew Newman (Carnegie Mellon University, Pittsburgh)

Title: Complexes of nearly maximum diameter

Abstract:

The combinatorial diameter of a simplicial complex is the diameter of its dual graph. Using a probabilistic approach we determine the right first-order asymptotics for the maximum possible diameter among all d-complexes on n vertices as well as among all d-pseudomanifolds on n vertices. This is joint work with Tom Bohman.


Coffee & Tea Break :

Room 134 - 1st Floor


Time: Monday, May 9 - 16:00 s.t.

Colloquium: Marcel Celaya (ETH, Zürich)

Title: Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Abstract:

Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.


Virenfrei. www.avast.com
--------------6B1DC146A114C923589E50D3-- From itabrunke@zedat.fu-berlin.de Wed May 11 19:48:02 2022 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 1noqRJ-001sBQ-V7; Wed, 11 May 2022 19:47:58 +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 1noqRJ-001QGg-Ip; Wed, 11 May 2022 19:47:57 +0200 Received: from ip5f5af638.dynamic.kabel-deutschland.de ([95.90.246.56] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (envelope-from ) id 1noqRJ-000VvO-3Z; Wed, 11 May 2022 19:47:57 +0200 From: "I.Brunke" To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 11 May 2022 19:47:56 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.11.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------79206BE6AB2459C228DCECE8" X-Antivirus: Avast (VPS 220510-12, 10.5.2022), Outbound message X-Antivirus-Status: Clean X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.246.56 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1652291277-00059D48-298E5928/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000056, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, T_REMOTE_IMAGE,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's Lecture & Colloquium May 16. 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, 11 May 2022 17:48:02 -0000 This is a multi-part message in MIME format. --------------79206BE6AB2459C228DCECE8 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, our next Monday's Lecture and Colloquium will take place on May 16, back in attendance, at 14:15 & 16:00 at TU Berlin. There will also be a Zoom link for those who can not make it in person. Invitation link for Zoom meeting: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *You all are cordially invited. * *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, May 16 - 14:15* *_Lecture_: Torsten Ueckerdt (Karlsruher Institut für Technologie, KIT)* *_Title_: Stack and Queue Layouts of Planar Graphs* *_Abstract_:* A colored linear layout of a graph is a total ordering of its vertices together with a partition of its edges into color classes. In a stack layout each color class is crossing-free, in a queue layout each color class is nesting-free, while in both cases our goal is to minimize the number of colors. In this talk we discuss on a higher level approaches to find good stack or queue layouts for planar graphs, including some recent breakthroughs and open problems. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor* *_Time_: **Monday, May 16 **- 16:00 s.t.* *_Colloquium_: Sandro Roch (Technische Universität Berlin)* *_Title_: Arrangements of Pseudocircles: On Digons and Triangles* *_Abstract_:* A pseudocircle is a simple closed curve in the plane. An intersecting arrangement of pseudocircles is a finite collection of pseudocircles so that any two intersect in exactly two points where they cross. Grünbaum conjectured in the 1970's that in the case of simple arrangements there are at most 2n - 2 digon cells, i.e. cells which have exactly two crossings on its boundary. I will present a result by Agarwal et al. (2004) which proves this conjecture for the special case of cylindrical arrangements. Based on that we show that the conjecture also holds whenever the arrangement contains three pseudocircles which pairwise form a digon cell. Moreover, I will present a result concerning the number of triangles in digon free arrangements, which disproves another conjecture by Grünbaum. (Joint with S.Felsner and M.Scheucher) -- Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft. https://www.avast.com/antivirus --------------79206BE6AB2459C228DCECE8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

our next Monday's Lecture and Colloquium will take place on May 16, back in attendance, at 14:15 & 16:00 at TU Berlin. There will also be a Zoom link for those who can not make it in person.

Invitation link for Zoom meeting:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password is required.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, May 16 - 14:15

Lecture: Torsten Ueckerdt (Karlsruher Institut für Technologie, KIT)

Title: Stack and Queue Layouts of Planar Graphs

Abstract:

A colored linear layout of a graph is a total ordering of its vertices together with a partition of its edges into color classes. In a stack layout each color class is crossing-free, in a queue layout each color class is nesting-free, while in both cases our goal is to minimize the number of colors. In this talk we discuss on a higher level approaches to find good stack or queue layouts for planar graphs, including some recent breakthroughs and open problems.


Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, May 16 - 16:00 s.t.

Colloquium: Sandro Roch (Technische Universität Berlin)

Title: Arrangements of Pseudocircles: On Digons and Triangles

Abstract:

A pseudocircle is a simple closed curve in the plane. An intersecting arrangement of pseudocircles is a finite collection of pseudocircles so that any two intersect in exactly two points where they cross. Grünbaum conjectured in the 1970's that in the case of simple arrangements there are at most 2n - 2 digon cells, i.e. cells which have exactly two crossings on its boundary. I will present a result by Agarwal et al. (2004) which proves this conjecture for the special case of cylindrical arrangements. Based on that we show that the conjecture also holds whenever the arrangement contains three pseudocircles which pairwise form a digon cell. Moreover, I will present a result concerning the number of triangles in digon free arrangements, which disproves another conjecture by Grünbaum.
(Joint with S.Felsner and M.Scheucher)


Virenfrei. www.avast.com
--------------79206BE6AB2459C228DCECE8-- From rote@zedat.fu-berlin.de Fri May 20 17:15:30 2022 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 1ns4Li-003RrC-0g; Fri, 20 May 2022 17:15:30 +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 1ns4Lh-000Sjx-Ua; Fri, 20 May 2022 17:15:29 +0200 Received: from dslb-094-222-013-156.094.222.pools.vodafone-ip.de ([94.222.13.156] helo=[192.168.178.46]) 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 1ns4Lh-002Q4C-KY; Fri, 20 May 2022 17:15:29 +0200 Message-ID: Date: Fri, 20 May 2022 17:15:24 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.8.1 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: Content-Language: en-US In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 94.222.13.156 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1653059730-00059D48-7B2FE2E6/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.002062, 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's Lecture May 23 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, 20 May 2022 15:15:30 -0000 Our next Monday's Lecture will take place on May 23, in attendance, at 14:15 at FU Berlin. *_Location_* *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, May 23 - 14:15* *_Lecture_: Katharina Jochemko (KTH Stockholm) *_Title_: The Eulerian transformation *_Abstract_:* Many polynomials arising in combinatorics are known or conjectured to have only real roots. One approach to these questions is to study transformations that preserve the real-rootedness property. This talk is centered around the Eulerian transformation which is the linear transformation that sends the i-th standard monomial to the i-th Eulerian polynomial. Eulerian polynomials appear in various guises in enumerative and geometric combinatorics and have many favorable properties, in particular, they are real-rooted and symmetric. We discuss how these properties carry over to the Eulerian transformation. In particular, we disprove a conjecture by Brenti (1989) concerning the preservation of real roots, extend recent results on binomial Eulerian polynomials and provide enumerative and geometric interpretations. This is joint work with Petter Brändén. There will be no zoom link, no Coffee & Tea Break, and no colloquium, but there will be a grill party after the lecture. From rote@zedat.fu-berlin.de Wed May 25 14:17:56 2022 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 1ntpxb-000TPn-Nv; Wed, 25 May 2022 14:17:55 +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 1ntpxb-002hDw-Lc; Wed, 25 May 2022 14:17:55 +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 1ntpxb-000bn2-GS; Wed, 25 May 2022 14:17:55 +0200 Message-ID: <9661c873-ff0d-d102-1909-477f479dd179@inf.fu-berlin.de> Date: Wed, 25 May 2022 14:17:55 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.0 Content-Language: en-US References: From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de 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-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1653481075-A617FDF4-6D2037B7/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.195161, 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 two Monday Lectures May 30 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, 25 May 2022 12:17:56 -0000 Our next Monday Lectures will take place on May 30, in attendance, at 14:15 at FU Berlin. There will be TWO lectures. _ATTENTION! Changed Location_ Hörsaal A Institut für Mathematik Arnimallee 22 14195 Berlin (across the street from the usual location) _Time_: Monday, May 30, 2022 - 14:15 _First Lecture_: János Pach (Rényi Institute, Budapest) _Title_: *Facets of Simplicity* _Abstract_: We discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures are of bounded complexity: they can be embedded in a bounded-dimensional space, or have small VC-dimension, or a short algebraic description. What are the advantages of low complexity? I will suggest a few possible answers to this question, and illustrate them with classical examples. *_Coffee & Tea Break_: Inner yard of Arnimallee 22 _Time_: Monday, May 30 - 16:00 _Second Lecture_: Imre Bárány (Rényi Institute, Budapest) _Title_: *Cells in the box and a hyperplane* _Abstract_: It is well known that a line can intersect at most 2n−1 cells of the n×n chessboard. What happens in higher dimensions: how many cells of the d-dimensional box [0,n]^d can a hyperplane intersect? We answer this question asymptotically. We also prove the integer analogue of the following fact. If K,L are convex bodies in R^d and K ⊂ L, then the surface area K is smaller than that of L. This is joint work with Péter Frankl. From rote@zedat.fu-berlin.de Mon May 30 00:20:08 2022 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 1nvRGW-0009qF-Lr; Mon, 30 May 2022 00:20:04 +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 1nvRGW-002Qp8-JS; Mon, 30 May 2022 00:20:04 +0200 Received: from dslb-178-005-227-128.178.005.pools.vodafone-ip.de ([178.5.227.128] helo=[192.168.178.46]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1nvRGW-003eMv-CS; Mon, 30 May 2022 00:20:04 +0200 Message-ID: Date: Mon, 30 May 2022 00:20:03 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.9.1 From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de References: Content-Language: en-US In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 178.5.227.128 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1653862804-A617FDF4-C5D2C9C2/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.124847, 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 two Monday Lectures May 30 (UPDATED INFO ON THE LOCATION) 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: Sun, 29 May 2022 22:20:09 -0000 Today's Monday Lectures will take place in attendance, at 14:15 at FU Berlin. There will be TWO lectures. _ATTENTION! Different locations of the lectures and of the break_ Hörsaal A, Chemistry building Arnimallee 22 14195 Berlin (a short walk along Arnimalle from the usual location) _Time_: Monday, May 30, 2022 - 14:15 _First Lecture_: János Pach (Rényi Institute, Budapest) _Title_: *Facets of Simplicity* _Abstract_: We discuss some notoriously hard combinatorial problems for large classes of graphs and hypergraphs arising in geometric, algebraic, and practical applications. These structures are of bounded complexity: they can be embedded in a bounded-dimensional space, or have small VC-dimension, or a short algebraic description. What are the advantages of low complexity? I will suggest a few possible answers to this question, and illustrate them with classical examples. *_Coffee & Tea Break_: *Zuse-Institute* (ZIB), Takustraße 7 _Time_: Monday, May 30 - 16:00 _Second Lecture_: Imre Bárány (Rényi Institute, Budapest) _Title_: *Cells in the box and a hyperplane* _Abstract_: It is well known that a line can intersect at most 2n−1 cells of the n×n chessboard. What happens in higher dimensions: how many cells of the d-dimensional box [0,n]^d can a hyperplane intersect? We answer this question asymptotically. We also prove the integer analog of the following fact. If K,L are convex bodies in R^d and K ⊂ L, then the surface area K is smaller than that of L. This is joint work with Péter Frankl. From itabrunke@zedat.fu-berlin.de Thu Jun 09 21:06:14 2022 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 1nzNTx-0015WC-LZ; Thu, 09 Jun 2022 21:06:13 +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 1nzNTx-002mkZ-Ih; Thu, 09 Jun 2022 21:06:13 +0200 Received: from ip5f5af521.dynamic.kabel-deutschland.de ([95.90.245.33] helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1nzNTx-0003bs-9A; Thu, 09 Jun 2022 21:06:13 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Thu, 9 Jun 2022 21:06:12 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------849654FDF290C431A56FDF8D" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.245.33 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1654801573-9624A6ED-E4EED9AD/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000012, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, 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's Lecture & Colloquium June 13. 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, 09 Jun 2022 19:06:14 -0000 This is a multi-part message in MIME format. --------------849654FDF290C431A56FDF8D Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on June 13 in attendance at 14:15 & 16:00 at TU Berlin. *You all are cordially invited. * *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, June 13 - 14:15* *_Lecture_: Matthias Beck (San Francisco State University)* *_Title_: Boundary h*-polynomials of rational polytopes* *_Abstract_:* If P is a *lattice polytope* (i.e., P is the convex hull of finitely many integer points in R^d), Ehrhart's famous theorem asserts that the integer-point counting function ||mP \cap Z^d|| is a polynomial in the integer variable m. Equivalently, the generating function \sum_{m \ge 0} ||mP \cap Z^d|| t^m is a rational function of the form h*(t)/(1-t)^{d+1}; we call h*(t) the *Ehrhart h**-*polynomial* of P. We know several necessary conditions for h*-polynomials, including results by Hibi, Stanley, and Stapledon, who used an interplay of arithmetic (integer-point structure) and topological (local h-vectors of triangulations) data of a given polytope. We introduce an alternative *ansatz* to understand Ehrhart theory through the h*-polynomial of the *boundary* of a polytope, recovering all of the above results and their extensions for rational polytopes in a unifying manner. This is joint work with Esme Bajo (UC Berkeley). _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor* *_Time_: **Monday, June 13 **- 16:00 s.t.* *_Colloquium_: Andrei Comăneci (Technische Universität Berlin)* *_Title_: Tropical Medians by Transportation* *_Abstract_:* The Fermat-Weber problem seeks a point that minimizes the average distance from a given sample. The problem was studied by Lin and Yoshida (2018) using the standard tropical metric with the purpose of analyzing phylogenetic data. In this talk, we argue that using a related asymmetric distance we have better geometric and algorithmic properties. The new formulation is strongly related to tropical convexity and is equivalent to a transportation problem. This gives a geometric perspective to the transportation problem, which was exploited by Tokuyama and Nakano (1995) to obtain efficient algorithms. At the end, we will see an application to computational biology: a new method for computing consensus trees. The talk is based on joint work with Michael Joswig. --------------849654FDF290C431A56FDF8D Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on June 13 in attendance at 14:15 & 16:00 at TU Berlin.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, June 13 - 14:15

Lecture: Matthias Beck (San Francisco State University)

Title: Boundary h*-polynomials of rational polytopes

Abstract:

If P is a lattice polytope (i.e., P is the convex hull of finitely many integer points in R^d), Ehrhart's famous theorem asserts that the integer-point counting function |mP \cap Z^d| is a polynomial in the integer variable m. Equivalently, the generating function \sum_{m \ge 0} |mP \cap Z^d| t^m is a rational function of the form h*(t)/(1-t)^{d+1}; we call h*(t) the Ehrhart h*-polynomial of P. We know several necessary conditions for h*-polynomials, including results by Hibi, Stanley, and Stapledon, who used an interplay of arithmetic (integer-point structure) and topological (local h-vectors of triangulations) data of a given polytope. We introduce an alternative ansatz to understand Ehrhart theory through the h*-polynomial of the boundary of a polytope, recovering all of the above results and their extensions for rational polytopes in a unifying manner.

This is joint work with Esme Bajo (UC Berkeley).


Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, June 13 - 16:00 s.t.

Colloquium: Andrei Comăneci (Technische Universität Berlin)

Title: Tropical Medians by Transportation

Abstract:

The Fermat-Weber problem seeks a point that minimizes the average distance from a given sample. The problem was studied by Lin and Yoshida (2018) using the standard tropical metric with the purpose of analyzing phylogenetic data. In this talk, we argue that using a related asymmetric distance we have better geometric and algorithmic properties. The new formulation is strongly related to tropical convexity and is equivalent to a transportation problem. This gives a geometric perspective to the transportation problem, which was exploited by Tokuyama and Nakano (1995) to obtain efficient algorithms. At the end, we will see an application to computational biology: a new method for computing consensus trees. The talk is based on joint work with Michael Joswig.

--------------849654FDF290C431A56FDF8D-- From itabrunke@zedat.fu-berlin.de Wed Jun 15 19:42:00 2022 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 1o1X1f-000sTC-RO; Wed, 15 Jun 2022 19:41:55 +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 1o1X1f-001NXf-Os; Wed, 15 Jun 2022 19:41:55 +0200 Received: from ip5f5af22b.dynamic.kabel-deutschland.de ([95.90.242.43] helo=[192.168.0.2]) 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 1o1X1e-000WYh-CP; Wed, 15 Jun 2022 19:41:55 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <4f3a4090-b52f-4198-7af7-d052f75205fa@fu-berlin.de> Date: Wed, 15 Jun 2022 19:41:53 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------FB5F6183B698A5BFBA43380E" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.242.43 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1655314915-53D439AE-D5B5D9F1/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.127334, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, 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's Lecture & Colloquium June 20. 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, 15 Jun 2022 17:42:00 -0000 This is a multi-part message in MIME format. --------------FB5F6183B698A5BFBA43380E Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on June 20 in attendance at 14:15 & 16:00 at TU Berlin. *You all are cordially invited. * *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, June 20 - 14:15* *_Lecture_: Karoly Böröczky (Rényi Institute, Budapest)* *_Title_: Facets of the Brascamp-Lieb Inequality and its Reverse form* *_Abstract_:* The Brascamp-Lieb inequality, a generalization of Holder's inequality, is introduced, together with its reverse form generalizing the Prekopa-Leindler due to Barthe. Under certain conditions, the optimal factor in either of inequalities can be obtained using Gaussian test functions. These conditions give rise to the so-called Brascamp Lieb polytope. Algorithmic aspects of approximating the optimal factor  are also discussed. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor* *_Time_: **Monday, June 20 **- 16:00 s.t.* *_Colloquium_: Christian Kipp (Technische Universität Berlin)* *_Title_: Affine Subspace Concentration Conditions for Polytopes* *_Abstract_:* Given an n-dimensional polytope P and one of its facets F, the cone volume corresponding to F is the volume of conv(0,F). P is said to satisfy the subspace concentration condition w.r.t. a d-dimensional linear subspace L if the total cone volume of the facets with normal vectors in L is at most d/n*vol(P). The subspace concentration condition plays an important role in the context of the (discrete) logarithmic Minkowski problem, i.e., the question: What conditions ensure that a given list of normal vectors and cone volumes can be realized by a polytope? Recently, an affine version of the subspace concentration condition was introduced by Wu for certain lattice polytopes. In this talk, I will focus on the affine case and discuss possible generalizations. This is joint work with Ansgar Freyer and Martin Henk. --------------FB5F6183B698A5BFBA43380E Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on June 20 in attendance at 14:15 & 16:00 at TU Berlin.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, June 20 - 14:15

Lecture: Karoly Böröczky (Rényi Institute, Budapest)

Title: Facets of the Brascamp-Lieb Inequality and its Reverse form

Abstract:

The Brascamp-Lieb inequality, a generalization of Holder's inequality, is introduced, together with its reverse form generalizing the Prekopa-Leindler due to Barthe. Under certain conditions, the optimal factor in either of inequalities can be obtained using Gaussian test functions. These conditions give rise to the so-called Brascamp Lieb polytope. Algorithmic aspects of approximating the optimal factor  are also discussed.


Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, June 20 - 16:00 s.t.

Colloquium: Christian Kipp (Technische Universität Berlin)

Title: Affine Subspace Concentration Conditions for Polytopes

Abstract:

Given an n-dimensional polytope P and one of its facets F, the cone volume corresponding to F is the volume of conv(0,F). P is said to satisfy the subspace concentration condition w.r.t. a d-dimensional linear subspace L if the total cone volume of the facets with normal vectors in L is at most d/n*vol(P). The subspace concentration condition plays an important role in the context of the (discrete) logarithmic Minkowski problem, i.e., the question: What conditions ensure that a given list of normal vectors and cone volumes can be realized by a polytope? Recently, an affine version of the subspace concentration condition was introduced by Wu for certain lattice polytopes. In this talk, I will focus on the affine case and discuss possible generalizations. This is joint work with Ansgar Freyer and Martin Henk.

--------------FB5F6183B698A5BFBA43380E-- From itabrunke@zedat.fu-berlin.de Fri Jun 24 16:16:45 2022 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 1o4k72-001JKn-Fs; Fri, 24 Jun 2022 16:16:44 +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 1o4k72-003Xbm-D9; Fri, 24 Jun 2022 16:16:44 +0200 Received: from ip5f5af167.dynamic.kabel-deutschland.de ([95.90.241.103] helo=[192.168.0.2]) 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 1o4k71-003ah1-Tu; Fri, 24 Jun 2022 16:16:44 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Fri, 24 Jun 2022 16:16:42 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------680E2E030AFE07E3CB994BD3" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.241.103 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1656080204-A617FDF4-2931EE17/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,HTML_MESSAGE, 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's Lecture & Colloquium June 27. 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, 24 Jun 2022 14:16:45 -0000 This is a multi-part message in MIME format. --------------680E2E030AFE07E3CB994BD3 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on June 27 in attendance at 14:15 & 16:00 at FU Berlin. *You all are cordially invited. * *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, June 20 - 14:15* *_Lecture_: Wolfgang Mulzer (Freie Universität Berlin)* *_Title_: Long Alternating Paths Exist* *_Abstract_:* Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length l is a sequence p_1, ..., p_l of l points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points p_i, p_{i+1} have different colors; and (iii) any two segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors, for i /= j. We show that there is an absolute constant eps > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + eps)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + eps)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3 + o(n). Based on joint work with Pavel Valtr. _*Coffee & Tea Break*_*:* *Room 134 - 1st Floor * *_Time_: **Monday, June 20 **- 16:00 s.t.* *_Colloquium_: Michaela Borzechowski (Freie Universität Berlin)* *_Title_: Unique Sink Orientations of Grids is in Unique End of Potential Line* *_Abstract_:* The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. PUEOPL captures search problems where the instances are promised to have a unique solution. UEOPL captures total search versions of these promise problems. The promise problems can be made total by defining violations that are returned as a short certificate of an unfulfilled promise. GridUSO is the problem of finding the sink in a grid with a unique sink orientation. It was introduced by Gärtner et al. in 2008. We describe a promise preserving reduction from GridUSO to UniqueForwardEOPL, a UEOPL-complete problem. Thus, we show that GridUSO is in UEOPL and its promise version is in PUEOPL. --------------680E2E030AFE07E3CB994BD3 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on June 27 in attendance at 14:15 & 16:00 at FU Berlin.

You all are cordially invited.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, June 20 - 14:15

Lecture: Wolfgang Mulzer (Freie Universität Berlin)

Title: Long Alternating Paths Exist

Abstract:

Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length l is a sequence p_1, ..., p_l of l points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points p_i, p_{i+1} have different colors; and (iii) any two segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors,
for i /= j.

We show that there is an absolute constant eps > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + eps)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + eps)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by a common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3 + o(n).

Based on joint work with Pavel Valtr.


Coffee & Tea Break :

Room 134 - 1st Floor


Time: Monday, June 20 - 16:00 s.t.

Colloquium: Michaela Borzechowski (Freie Universität Berlin)

Title: Unique Sink Orientations of Grids is in Unique End of Potential Line

Abstract:

The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. PUEOPL captures search problems where the instances are promised to have a unique solution. UEOPL captures total search versions of these promise problems. The promise problems can be made total by defining violations that are returned as a short certificate of an unfulfilled promise.

GridUSO is the problem of finding the sink in a grid with a unique sink orientation. It was introduced by Gärtner et al. in 2008. We describe a promise preserving reduction from GridUSO to UniqueForwardEOPL, a UEOPL-complete problem. Thus, we show that GridUSO is in UEOPL and its promise version is in PUEOPL.

--------------680E2E030AFE07E3CB994BD3-- From itabrunke@zedat.fu-berlin.de Thu Jun 30 19:14:22 2022 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 1o6xkA-0020Oi-3W; Thu, 30 Jun 2022 19:14:18 +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 1o6xkA-001RWE-11; Thu, 30 Jun 2022 19:14:18 +0200 Received: from ip5f5af7b7.dynamic.kabel-deutschland.de ([95.90.247.183] helo=[192.168.0.2]) 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 1o6xk9-00104i-LK; Thu, 30 Jun 2022 19:14:17 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Thu, 30 Jun 2022 19:14:16 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------58531C513A1B574B5C266324" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.247.183 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1656609258-5EEAF476-08D67539/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000115, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, 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's Lecture & Colloquium July 4. 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, 30 Jun 2022 17:14:23 -0000 This is a multi-part message in MIME format. --------------58531C513A1B574B5C266324 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on July 4 in attendance at 14:15 & 16:00 at TU Berlin. *You all are cordially invited. * *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, July 4 - 14:15* *_Lecture_: Myfanwy Evans (Universität Potsdam)* *_Title_: Enumerating triply-periodic tangles* *_Abstract_:* Using periodic surfaces as a scaffold is a convenient route to making periodic entanglements. I will present a systematic way of enumerating new tangled periodic structures, using low-dimensional topology and combinatorics, posing the question of how to best characterise these new patterns. I will also give an insight into applications of these structures. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor* *_Time_: **Monday, July 4 **- 16:00 s.t.* *_Colloquium_: Marcel Celaya (ETH, Zürich)* *_Title_: Improving the Cook et al. Proximity Bound Given Integral Valued Constraints* *_Abstract_:* Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel. --------------58531C513A1B574B5C266324 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on July 4 in attendance at 14:15 & 16:00 at TU Berlin.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, July 4 - 14:15

Lecture: Myfanwy Evans (Universität Potsdam)

Title: Enumerating triply-periodic tangles

Abstract:

Using periodic surfaces as a scaffold is a convenient route to making periodic entanglements. I will present a systematic way of enumerating new tangled periodic structures, using low-dimensional topology and combinatorics, posing the question of how to best characterise these new patterns. I will also give an insight into applications of these structures.


Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, July 4 - 16:00 s.t.

Colloquium: Marcel Celaya (ETH, Zürich)

Title: Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Abstract:

Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.
--------------58531C513A1B574B5C266324-- From itabrunke@zedat.fu-berlin.de Mon Jul 04 18:49:06 2022 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 1o8PFt-001dOr-BT; Mon, 04 Jul 2022 18:49:01 +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 1o8PFt-000HyM-8p; Mon, 04 Jul 2022 18:49:01 +0200 Received: from ip5f5af788.dynamic.kabel-deutschland.de ([95.90.247.136] helo=[192.168.0.2]) 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 1o8PFs-000sQ7-Ve; Mon, 04 Jul 2022 18:49:01 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <11c7cf6d-3ece-a25d-b424-f0467adadd0d@fu-berlin.de> Date: Mon, 4 Jul 2022 18:49:00 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------E9189D12200AC3D0AE8DDCAE" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.247.136 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1656953341-23B84EE9-C11DFC02/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.483639, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, 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 & Colloquium July 11. 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, 04 Jul 2022 16:49:06 -0000 This is a multi-part message in MIME format. --------------E9189D12200AC3D0AE8DDCAE Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, next Monday's Lecture and Colloquium will take place on July 11 at 14:15 & 16:00 at TU Berlin. *You all are cordially invited. * *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, July 11 - 14:15* *_Lecture_: Bill Zwicker (Union College, USA)* *_Title_: Higher-order Condorcet cycles* *_Abstract_:* In an ordinary Condorcet cycle one can identify, for each candidate, a second candidate preferred, by a majority of voters, to the first.  In a */Condorcet cycle of order 2/* one can identify, for each pair of candidates, a third candidate preferred, by a majority of voters, to both.  We construct two Condorcet cycles of order 2.  The first, with 11 alternatives and 11 voters, improves the example of 15 alternatives and 15 voters given in [1].  The second, with 7 alternatives and 21 voters, shows that the lower bound on alternatives established in [4] and [3] (and independently in [1]) is sharp. Both our constructions use the method of */horizontal rotation/*, introduced here, which generalizes the more typical form of rotation used to construct standard Condorcet cycles. The second example also makes use of a beautifully symmetric tournament constructed in [3]. William S. Zwicker^a (joint work with Davide P. Cervone^b ) keywords: Condorcet cycle of order 2, Condorcet winning set, tournament [1] Elkind, E., Lang, J., and Saffidine, A., Condorcet Winning Sets, /Soc Choice Welf /44, 493-517 (2015) [2] Erdös, P., On a problem of graph theory, /Math Gaz/ 47, 220-223 (1963) [3] Graham, R.L. and Spencer, J.H., A constructive solution to a tournament problem, /Can Math Bul/ 14, 45-48 (1971) [4] Szekeres, E. and Szekeres,G., On a problem of Schütte and Erdös, /Math Gaz/ 49, 290-293 (1965) ^a William D Williams Professor of Mathematics Emeritus, Union College, New York; and Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University ^b Mathematics Department, Union College, New York _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor* *_Time_: **Monday, July 11 **- 16:00 s.t.* *_Colloquium_: Warut Suksompong (National University of Singapore)* *_Title_: The Price of Connectivity in Fair Division* *_Abstract_:* We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems. Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu. --------------E9189D12200AC3D0AE8DDCAE Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

next Monday's Lecture and Colloquium will take place on July 11 at 14:15 & 16:00 at TU Berlin.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, July 11 - 14:15

Lecture: Bill Zwicker (Union College, USA)

Title: Higher-order Condorcet cycles

Abstract:

In an ordinary Condorcet cycle one can identify, for each candidate, a second candidate preferred, by a majority of voters, to the first.  In a Condorcet cycle of order 2 one can identify, for each pair of candidates, a third candidate preferred, by a majority of voters, to both.  We construct two Condorcet cycles of order 2.  The first, with 11 alternatives and 11 voters, improves the example of 15 alternatives and 15 voters given in [1].  The second, with 7 alternatives and 21 voters, shows that the lower bound on alternatives established in [4] and [3] (and independently in [1]) is sharp. Both our constructions use the method of horizontal rotation, introduced here, which generalizes the more typical form of rotation used to construct standard Condorcet cycles. The second example also makes use of a beautifully symmetric tournament constructed in [3].

William S. Zwickera (joint work with Davide P. Cervoneb)

keywords: Condorcet cycle of order 2, Condorcet winning set, tournament

[1] Elkind, E., Lang, J., and Saffidine, A., Condorcet Winning Sets, Soc Choice Welf 44, 493-517 (2015)

[2] Erdös, P., On a problem of graph theory, Math Gaz 47, 220-223 (1963)

[3] Graham, R.L. and Spencer, J.H., A constructive solution to a tournament problem, Can Math Bul 14, 45-48 (1971)

[4] Szekeres, E. and Szekeres,G., On a problem of Schütte and Erdös, Math Gaz 49, 290-293 (1965)

aWilliam D Williams Professor of Mathematics Emeritus, Union College, New York; and Murat Sertel Center for Advanced Economic Studies, Istanbul Bilgi University

bMathematics Department, Union College, New York



Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, July 11 - 16:00 s.t.

Colloquium: Warut Suksompong (National University of Singapore)

Title: The Price of Connectivity in Fair Division

Abstract:

We study the allocation of indivisible goods that form an undirected graph and quantify the loss of fairness when we impose a constraint that each agent must receive a connected subgraph. Our focus is on well-studied fairness notions including envy-freeness and maximin share fairness. We introduce the price of connectivity to capture the largest gap between the graph-specific and the unconstrained maximin share, and derive bounds on this quantity which are tight for large classes of graphs in the case of two agents and for paths and stars in the general case. For instance, with two agents we show that for biconnected graphs it is possible to obtain at least 3/4 of the maximin share with connected allocations, while for the remaining graphs the guarantee is at most 1/2. In addition, we determine the optimal relaxation of envy-freeness that can be obtained with each graph for two agents, and characterize the set of trees and complete bipartite graphs that always admit an allocation satisfying envy-freeness up to one good (EF1) for three agents. Our work demonstrates several applications of graph-theoretic tools and concepts to fair division problems. Joint work with Xiaohui Bei, Ayumi Igarashi, and Xinhang Lu.
--------------E9189D12200AC3D0AE8DDCAE-- From itabrunke@zedat.fu-berlin.de Thu Jul 14 00:26:14 2022 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 1oBko5-000fxw-Gq; Thu, 14 Jul 2022 00:26:09 +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 1oBko5-001wiX-EC; Thu, 14 Jul 2022 00:26:09 +0200 Received: from [95.90.244.183] (helo=[192.168.0.2]) 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 1oBko1-0012t5-Na; Thu, 14 Jul 2022 00:26:09 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Thu, 14 Jul 2022 00:26:06 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------3148DE9D6317A94A000310CB" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.244.183 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1657751169-2B8B2E82-0254887D/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.002328, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, 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's Lecture & Colloquium July 18. 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, 13 Jul 2022 22:26:14 -0000 This is a multi-part message in MIME format. --------------3148DE9D6317A94A000310CB Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, our next and last Monday's Lecture and Colloquium will take place on July 18 at 14:15 & 16:00 at FU Berlin. *You are all cordially invited. * *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, July 18 - 14:15* *_Lecture_: Herman Haverkort (Universität Bonn)* *_Title_: Space-filling curves: properties, applications and challenges* *_Abstract_:* A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve. _*Coffee & Tea Break*_*:* *Room 134 - 1st Floor * *_Time_: **Monday, July 18 **- 16:00 s.t.* *_Colloquium_: Andrea Jiménez (Universidad de Varparaíso, Chile)* *_Title_: Groundstates of the Ising Model on antiferromagnetic triangulations* *_Abstract_:* We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovasz and Plummer. The dual version is formulated as follows "Every triangulation of an orientable surface has exponentially many groundstates'', where groundstates are the states at the lowest energy in the antiferromagnetic Ising Model. According to physicists, this dual formulation holds. In this talk, I show a counterexample to the dual formulation, a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and, if time allows, some open problems. This is joint work with Marcos Kiwi and Martin Loebl. --------------3148DE9D6317A94A000310CB Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

our next and last Monday's Lecture and Colloquium will take place on July 18 at 14:15 & 16:00 at FU Berlin.

You are all cordially invited.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, July 18 - 14:15

Lecture: Herman Haverkort (Universität Bonn)

Title: Space-filling curves: properties, applications and challenges

Abstract:

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.


Coffee & Tea Break :

Room 134 - 1st Floor


Time: Monday, July 18 - 16:00 s.t.

Colloquium: Andrea Jiménez (Universidad de Varparaíso, Chile)

Title: Groundstates of the Ising Model on antiferromagnetic triangulations

Abstract:

We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovasz and Plummer. The dual version is formulated as follows "Every triangulation of an orientable surface has exponentially many groundstates'', where groundstates are the states at the lowest energy in the antiferromagnetic Ising Model.

According to physicists, this dual formulation holds. In this talk, I show a counterexample to the dual formulation, a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and, if time allows, some open problems.

This is joint work with Marcos Kiwi and Martin Loebl.

--------------3148DE9D6317A94A000310CB-- From itabrunke@zedat.fu-berlin.de Thu Jul 14 00:34:09 2022 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 1oBkvk-000h4N-AJ; Thu, 14 Jul 2022 00:34:04 +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 1oBkvj-001yBq-OF; Thu, 14 Jul 2022 00:34:03 +0200 Received: from [95.90.244.183] (helo=[192.168.0.2]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1oBkvg-0013Wy-Na; Thu, 14 Jul 2022 00:34:03 +0200 To: facets-of-complexity@lists.fu-berlin.de Cc: Andrea Jimenez From: Ita Brunke Message-ID: Date: Thu, 14 Jul 2022 00:34:01 +0200 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.12 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------3DA271733B18AC3E0DC96E4B" X-Original-Sender: i.brunke@fu-berlin.de X-Originating-IP: 95.90.244.183 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1657751644-7B232F4B-C2AD4C73/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,HTML_MESSAGE, 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's Lecture & Colloquium July 18. Program. 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, 13 Jul 2022 22:34:09 -0000 This is a multi-part message in MIME format. --------------3DA271733B18AC3E0DC96E4B Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear all, there may be a change of program for the colloquium. Our next and last Monday's Lecture and Colloquium will take place on July 18 at 14:15 & 16:00 at FU Berlin. *You are all cordially invited. * *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, July 18 - 14:15* *_Lecture_: Herman Haverkort (Universität Bonn)* *_Title_: Space-filling curves: properties, applications and challenges* *_Abstract_:* A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve. _*Coffee & Tea Break*_*:* *Room 134 - 1st Floor * *_Time_: **Monday, July 18 **- 16:00 s.t.* *_Colloquium_: Andrea Jiménez (Universidad de Varparaíso, Chile)* *_Title_: Grid subdivisions, wall minors and treewidth in planar graphs* *_Abstract_:* Minors, subdivisions and treewidth are classical notions that appear for example in the seminal characterization of planar graphs by Kuratowski and in the celebrated Graph Minor Theorem by Robertson and Seymour. The importance of grid/wall minors comes from one of the results of Robertson and Seymour, which roughly claims that a graph of large treewidth necessarily contains a large grid/wall minor. The concept of treewidth is fundamental in algorithmic graph theory since many problems which are hard to solve in general, can be efficiently solved when restricted to classes of graphs with bounded treewidth. In this talk, we discuss the computational complexity of the Minor Problem, the Subdivision Problem and the Treewidth Problem with input: grids/walls and planar graphs. Surprisingly, some of these problems are still open. We describe two reductions which prove that the respective GridSubdivision Problem and the WallMinor Problem are NP-complete problems. This is joint work with//Tina Janne Schmidt and with Carla Lintzmayer and Maycon Sambinelli. --------------3DA271733B18AC3E0DC96E4B Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear all,

there may be a change of program for the colloquium.

Our next and last Monday's Lecture and Colloquium will take place on July 18 at 14:15 & 16:00 at FU Berlin.

You are all cordially invited.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, July 18 - 14:15

Lecture: Herman Haverkort (Universität Bonn)

Title: Space-filling curves: properties, applications and challenges

Abstract:

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.


Coffee & Tea Break :

Room 134 - 1st Floor


Time: Monday, July 18 - 16:00 s.t.

Colloquium: Andrea Jiménez (Universidad de Varparaíso, Chile)

Title: Grid subdivisions, wall minors and treewidth in planar graphs

Abstract:

Minors, subdivisions and treewidth are classical notions that appear for example in the seminal characterization of planar graphs by Kuratowski and in the celebrated Graph Minor Theorem by Robertson and Seymour. The importance of grid/wall minors comes from one of the results of Robertson and Seymour, which roughly claims that a graph of large treewidth necessarily contains a large grid/wall minor. The concept of treewidth is fundamental in algorithmic graph theory since many problems which are hard to solve in general, can be efficiently solved when restricted to classes of graphs with bounded treewidth.

In this talk, we discuss the computational complexity of the Minor Problem, the Subdivision Problem and the Treewidth Problem with input: grids/walls and planar graphs. Surprisingly, some of these problems are still open. We describe two reductions which prove that the respective GridSubdivision Problem and the WallMinor Problem are NP-complete problems.

This is joint work with Tina Janne Schmidt and with Carla Lintzmayer and Maycon Sambinelli.
--------------3DA271733B18AC3E0DC96E4B-- From szabo@zedat.fu-berlin.de Thu Sep 22 12:06:29 2022 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 1obJ68-000UYk-Ld; Thu, 22 Sep 2022 12:06:24 +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 1obJ68-002f0C-Ho; Thu, 22 Sep 2022 12:06:24 +0200 Received: from ip5f5aeaf2.dynamic.kabel-deutschland.de ([95.90.234.242] helo=[192.168.0.8]) by inpost2.zedat.fu-berlin.de (Exim 4.95) with esmtpsa (TLS1.3) tls TLS_AES_128_GCM_SHA256 (envelope-from ) id 1obJ68-001PJy-Ba; Thu, 22 Sep 2022 12:06:24 +0200 Content-Type: multipart/alternative; boundary="------------mcYTkca8NEGbD2Z1TcmIiEuE" Message-ID: Date: Thu, 22 Sep 2022 12:06:23 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:91.0) Gecko/20100101 Thunderbird/91.13.0 Content-Language: en-US From: Tibor Szabo To: facets-of-complexity@lists.fu-berlin.de, m-profs@math.fu-berlin.de, i-prof@inf.fu-berlin.de, m-wimis@math.fu-berlin.de, i-wimi@inf.fu-berlin.de Cc: Olaf Parczyk , Sabrina Nordt , =?UTF-8?Q?Let=c3=adcia_Mattos?= References: <3ccff1fb-a2d2-6b82-3b7f-d84fc31f8f1c@zedat.fu-berlin.de> <89eedbfd-db19-8a0d-3f4e-90d7cb5c756d@zedat.fu-berlin.de> In-Reply-To: <89eedbfd-db19-8a0d-3f4e-90d7cb5c756d@zedat.fu-berlin.de> X-Originating-IP: 95.90.234.242 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1663841184-BFB59D5B-43C6D654/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.009103, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-50.0 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE X-Spam-Checker-Version: SpamAssassin 3.4.6 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: X-Mailman-Approved-At: Thu, 22 Sep 2022 12:10:00 +0200 Subject: [Facets-of-complexity] Aigner 80 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, 22 Sep 2022 10:06:29 -0000 This is a multi-part message in MIME format. --------------mcYTkca8NEGbD2Z1TcmIiEuE Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Dear Colleagues, in 2022 Martin Aigner has turned 80. On the afternoon (14:00-18:00) of the 7th of November we will celebrate this occasion with a Festkolloquium. Invited speakers include Mathias Schacht (Hamburg), Emo Welzl (Zurich), and Günther Ziegler (Berlin). There is no registration fee, however, if you are interested in attending, please indicate this *by the end of September:* **https://docs.google.com/forms/d/e/1FAIpQLSfEsxz0FD9RDZQT2PosE86UD-HFHjgGFDBQTE8hvD4ETsb-dg/viewform so we can estimate the number of participants. Best regards, Tibor Szabó --------------mcYTkca8NEGbD2Z1TcmIiEuE Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Dear Colleagues,

in 2022 Martin Aigner has turned 80. On the afternoon (14:00-18:00) of the 7th of November we will celebrate this occasion with a Festkolloquium. Invited speakers include Mathias Schacht (Hamburg), Emo Welzl (Zurich), and Günther Ziegler (Berlin). There is no registration fee, however, if you are interested in attending, please indicate this by the end of September:

https://docs.google.com/forms/d/e/1FAIpQLSfEsxz0FD9RDZQT2PosE86UD-HFHjgGFDBQTE8hvD4ETsb-dg/viewform

so we can estimate the number of participants.

Best regards,

Tibor Szabó

--------------mcYTkca8NEGbD2Z1TcmIiEuE--