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--