From itabrunke@zedat.fu-berlin.de Mon Apr 12 15:51:06 2021 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 1lVwxy-003o2Y-8w; Mon, 12 Apr 2021 15:51:02 +0200 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 1lVwxx-0032u6-Rr; Mon, 12 Apr 2021 15:51:01 +0200 Received: from ip5f5af57b.dynamic.kabel-deutschland.de ([95.90.245.123] 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 1lVwxx-003vXa-IB; Mon, 12 Apr 2021 15:51:01 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <8695b0d5-0c4d-d7c1-c5cd-4f3e9b9baf31@inf.fu-berlin.de> Date: Mon, 12 Apr 2021 15:51:02 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.245.123 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1618235461-000004C4-91417C3A/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000002, 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.5 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Thematic Einstein Semester "Geometric and Topological Structure of Materials" 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, 12 Apr 2021 13:51:06 -0000 Dear all, please find below the invitation to the Thematic Einstein Semester on "Geometric and Topological Structure of Materials". All the best, Ita. ---------------------- CALL FOR PARTICIPATION ---------------------- Dear Scientists and Mathematicians, We wish to announce the opening event (April 13 + 14, 2021) of the upcoming **************************************************************************    Thematic Einstein Semester        "Geometric and Topological Structure of Materials"    TU Berlin, Summer 2021 https://www3.math.tu-berlin.de/mathplus/TES-Summer2021/ ************************************************************************** This fourth Berlin Thematic Einstein Semester (postponed from 2020) is devoted to recent developments in the field of computational materials science. It aims to bring together experts from the sciences with experts from computational topology, computational algebraic, discrete differential and stochastic geometry working on the structure and function of materials. The semester is organized within the framework of the Berlin Mathematics Research Center MATH+ and is supported by the Einstein Foundation Berlin. Opening Event: ------------- April 13, 2021, Time Zone: Berlin Time (Central European Summer Time, CEST)    02:15 pm to 02:45 pm   Virtual get-together    02:45 pm to 03:00 pm   Welcome address by Christof Schütte                           (President of ZIB Berlin, Chair of MATH+)    03:00 pm to 03:40 pm   Ileana Streinu (Smith College)    03:50 pm to 04:30 pm   Daphne Klotsa (U North Carolina at Chapel Hill)    04:30 pm to 05:00 pm   Virtual coffee break    05:00 pm to 05:40 pm   Herbert Edelsbrunner (IST Austria) April 14, 2021, Time Zone: Berlin Time (Central European Summer Time, CEST)    09:00 am to 09:40 am   Stephen Hyde (U Sydney)    09:50 am to 10:30 am   Motoko Kotani (Tohoku U)    10:30 am to 11:00 am   Virtual coffee break    11:00 am to 11:40 am   Yasuaki Hiraoka (Kyoto U) Participation: ------------- free Registration: ------------ Please register via this form: https://docs.google.com/forms/d/e/1FAIpQLSdW_OVSvdTWHsZHdzqrTTvd54pTaCCnu6Snw_ui7TOT4XbHkA/viewform Registered participants will receive the links for the semester by email. Organizers: ----------    Myfanwy Evans (U Potsdam)    Kathryn Hess Bellwald (EPFL)    Frank Lutz (TU Berlin)    Dmitriy Morozov (LBNL)    Ileana Streinu (Smith College) From itabrunke@zedat.fu-berlin.de Fri Apr 23 16:17:42 2021 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 1lZwck-000y3t-KR; Fri, 23 Apr 2021 16:17:38 +0200 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 1lZwcg-001vod-LQ; Fri, 23 Apr 2021 16:17:34 +0200 Received: from [95.90.242.218] (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 1lZwcg-002d8A-5X; Fri, 23 Apr 2021 16:17:34 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Fri, 23 Apr 2021 16:17:34 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------CA9FAD0069990D70BDA834A2" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.242.218 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1619187458-000004C0-5BFD7581/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.029619, 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.5 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - April 26th 2021 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, 23 Apr 2021 14:17:42 -0000 This is a multi-part message in MIME format. --------------CA9FAD0069990D70BDA834A2 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit You are cordially invited to our next Monday Lecture & Colloquium on April 26th at 14:15 h & 16:00 h, online via Zoom. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, April 26th - 14:15 h* *_Lecture_: Kolja Knauer (Universitat de Barcelona**)* *_Title_: On sensitivity in Cayley graphs* *_Abstract_:* Recently, Huang proved the Sensitivity Conjecture, by showing that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$. This is tight by a result of Chung, F\"uredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. In this lecture we study Huang's question on Cayley graphs of groups. We show that high symmetry alone does not guarantee similar behavior and present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree $1$ on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret. On the positive side, we consider Cayley graphs of Coxeter groups, where a lower bound similar to Huang's can be shown. A generalization of the construction of Chung, F\"uredi, Graham, and Seymour shows that this bound is tight for products of Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$, most exceptional cases and not far from optimal in general. Then, we show that also induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This yields more classes of Cayley graphs with properties similar to the ones provided by Huang's results. However, in contrast to Coxeter groups these graphs have no large subcubes. Joint with Ignacio Garcia-Marco. *Break* *_Time_: **Monday, **April 26th**- 16:00 h s.t.* *_Colloquium_: Matthieu Rosenfeld (LIRMM)* *_Title_: Bounding the number of sets defined by a given MSO formula on trees* *_Abstract_:* Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets, or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order n is at most 95^(n/13) and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second-order formula. I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique. --------------CA9FAD0069990D70BDA834A2 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit

You are cordially invited to our next Monday Lecture & Colloquium on April 26th at 14:15 h & 16:00 h, online via Zoom.

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

Online via:
Zoom - Invitation

Time: Monday, April 26th - 14:15 h

Lecture: Kolja Knauer (Universitat de Barcelona)

Title: On sensitivity in Cayley graphs

Abstract:

Recently, Huang proved the Sensitivity Conjecture, by showing that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$. This is tight by a result of Chung, F\"uredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. In this lecture we study Huang's question on Cayley graphs of groups.

We show that high symmetry alone does not guarantee similar behavior and present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree $1$ on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret.

On the positive side, we consider Cayley graphs of Coxeter groups, where a lower bound similar to Huang's can be shown. A generalization of the construction of Chung, F\"uredi, Graham, and Seymour shows that this bound is tight for products of Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$, most exceptional cases and not far from optimal in general.
Then, we show that also induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This yields more classes of Cayley graphs with properties similar to the ones provided by Huang's results. However, in contrast to Coxeter groups these graphs have no large subcubes.
Joint with Ignacio Garcia-Marco.


Break

Time: Monday, April 26th - 16:00 h s.t.

Colloquium: Matthieu Rosenfeld (LIRMM)

Title: Bounding the number of sets defined by a given MSO formula on trees

Abstract:

Monadic second order logic can be used to express many classical notions of sets of vertices of a graph as for instance: dominating sets, induced matchings, perfect codes, independent sets, or irredundant sets. Bounds on the number of sets of any such family of sets are interesting from a combinatorial point of view and have algorithmic applications. Many such bounds on different families of sets over different classes of graphs are already provided in the literature. In particular, Rote recently showed that the number of minimal dominating sets in trees of order n is at most 95^(n/13) and that this bound is asymptotically sharp up to a multiplicative constant. We build on his work to show that what he did for minimal dominating sets can be done for any family of sets definable by a monadic second-order formula.
I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique.
--------------CA9FAD0069990D70BDA834A2-- From itabrunke@zedat.fu-berlin.de Mon Apr 26 19:14:12 2021 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 1lb4oC-001jaU-Tr; Mon, 26 Apr 2021 19:14:08 +0200 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 1lb4o9-002ZfT-VK; Mon, 26 Apr 2021 19:14:06 +0200 Received: from ip5f5af536.dynamic.kabel-deutschland.de ([95.90.245.54] 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 1lb4o9-002k6Z-Ay; Mon, 26 Apr 2021 19:14:05 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <5cb533e6-a5ec-1856-d839-257668b79cf3@inf.fu-berlin.de> Date: Mon, 26 Apr 2021 19:14:06 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------B36D404131B85FED86BDA878" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.245.54 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1619457248-000004F9-59374219/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 X-Spam-Checker-Version: SpamAssassin 3.4.6 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture May 3rd 2021 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, 26 Apr 2021 17:14:12 -0000 This is a multi-part message in MIME format. --------------B36D404131B85FED86BDA878 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture on May 3rd. Exceptionally, there will only be the Lecture. Exceptionally this Lecture will be at*16:30.* Lecture will be given online via Zoom. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, May 3rd - 16:30 h !!* *_Lecture_: Chris Eur (Stanford University)* *_Title_: Tautological classes of matroids* *_Abstract_:* We introduce certain torus-equivariant classes on permutohedral varieties which we call "tautological classes of matroids" as a new geometric framework for studying matroids. Using this framework, we unify and extend many recent developments in matroid theory arising from its interaction with algebraic geometry. We achieve this by establishing a Chow-theoretic description and a log-concavity property for a 4-variable transformation of the Tutte polynomial, and by establishing an exceptional Hirzebruch-Riemann-Roch-type formula for permutohedral varieties that translates between K-theory and Chow theory.  This is a joint work with Andrew Berget, Hunter Spink, and Dennis Tseng. --------------B36D404131B85FED86BDA878 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture on May 3rd.
Exceptionally, there will only be the Lecture.
Exceptionally this Lecture will be at 16:30.

Lecture will be given online via Zoom.

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

Online via:
Zoom - Invitation

Time: Monday, May 3rd - 16:30 h !!

Lecture: Chris Eur (Stanford University)

Title: Tautological classes of matroids

Abstract:

We introduce certain torus-equivariant classes on permutohedral varieties which we call "tautological classes of matroids" as a new geometric framework for studying matroids. Using this framework, we unify and extend many recent developments in matroid theory arising from its interaction with algebraic geometry. We achieve this by establishing a Chow-theoretic description and a log-concavity property for a 4-variable transformation of the Tutte polynomial, and by establishing an exceptional Hirzebruch-Riemann-Roch-type formula for permutohedral varieties that translates between K-theory and Chow theory.  This is a joint work with Andrew Berget, Hunter Spink, and Dennis Tseng.

--------------B36D404131B85FED86BDA878-- From itabrunke@zedat.fu-berlin.de Wed May 05 19:12:57 2021 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 1leL4v-003xOi-Dp; Wed, 05 May 2021 19:12:53 +0200 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 1leL4t-0030P3-A4; Wed, 05 May 2021 19:12:51 +0200 Received: from ip5f5af31f.dynamic.kabel-deutschland.de ([95.90.243.31] 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 1leL4t-002p7s-36; Wed, 05 May 2021 19:12:51 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 5 May 2021 19:12:51 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------49B4EDFC7554157E59AC272D" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.243.31 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1620234773-000004C4-A40128F9/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 X-Spam-Checker-Version: SpamAssassin 3.4.6 on Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - May 10th 2021 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, 05 May 2021 17:12:57 -0000 This is a multi-part message in MIME format. --------------49B4EDFC7554157E59AC272D Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on May 10th at 14:15 h & 16:00 h, online via Zoom. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, May 10th - 14:15 h* *_Lecture_: Max Klimm (Technische Universität Berlin**)* *_Title_: tba* *_Abstract_:* tba *Break* *_Time_: **Monday, **May 10th**- 16:00 h s.t.* *_Colloquium_: Aniket Shah (Ohio State University)* *_Title_: A q-analogue of Brion's identity* *_Abstract_:* Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0. --------------49B4EDFC7554157E59AC272D Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on May 10th at 14:15 h & 16:00 h, online via Zoom.

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

Online via:
Zoom - Invitation

Time: Monday, May 10th - 14:15 h

Lecture: Max Klimm (Technische Universität Berlin)

Title: tba

Abstract:

tba


Break

Time: Monday, May 10th - 16:00 h s.t.

Colloquium: Aniket Shah (Ohio State University)

Title: A q-analogue of Brion's identity

Abstract:

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.

--------------49B4EDFC7554157E59AC272D-- From itabrunke@zedat.fu-berlin.de Thu May 06 15:28:05 2021 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 1lee2q-001phH-Vo; Thu, 06 May 2021 15:28:01 +0200 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 1lee2p-002bvj-KS; Thu, 06 May 2021 15:27:59 +0200 Received: from ip5f5af30c.dynamic.kabel-deutschland.de ([95.90.243.12] 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 1lee2p-000w4H-9X; Thu, 06 May 2021 15:27:59 +0200 To: facets-of-complexity@lists.fu-berlin.de From: Ita Brunke Message-ID: <54808f79-0e27-3bfc-37e5-8fca5cd59324@inf.fu-berlin.de> Date: Thu, 6 May 2021 15:27:59 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------D50532DAD8442909C2F28B0D" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.243.12 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1620307680-000004C8-2011B3CF/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.113785, 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 Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - May 10th 2021 X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.29 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 06 May 2021 13:28:05 -0000 This is a multi-part message in MIME format. --------------D50532DAD8442909C2F28B0D Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on May 10th at 14:15 h & 16:00 h, online via Zoom. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, May 10th - 14:15 h* *_Lecture_: Max Klimm (Technische Universität Berlin**)* *_Title_: Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games* *_Abstract_:* We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions as we show that the computation is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. These insights give rise to a path following formulation eventually putting the problem into PPAD. For the PPAD—hardness, we reduce from computing an approximate equilibrium for bimatrix win-lose games. As a byproduct of our analyse, we obtain that also computing a multi-class Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As another byproduct, we obtain an algorithm that computes a continuum of equilibria parametrised by the players’ flow demand. For games with player-independent costs, this yields an output-polynomial algorithm. (Joint work with Philipp Warode) *Break* *_Time_: **Monday, **May 10th**- 16:00 h s.t.* *_Colloquium_: Aniket Shah (Ohio State University)* *_Title_: A q-analogue of Brion's identity* *_Abstract_:* Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0. --------------D50532DAD8442909C2F28B0D Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on May 10th at 14:15 h & 16:00 h, online via Zoom.

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

Online via:
Zoom - Invitation

Time: Monday, May 10th - 14:15 h

Lecture: Max Klimm (Technische Universität Berlin)

Title: Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games

Abstract:

We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions as we show that the computation is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. These insights give rise to a path following formulation eventually putting the problem into PPAD. For the PPAD—hardness, we reduce from computing an approximate equilibrium for bimatrix win-lose games. As a byproduct of our analyse, we obtain that also computing a multi-class Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As another byproduct, we obtain an algorithm that computes a continuum of equilibria parametrised by the players’ flow demand. For games with player-independent costs, this yields an output-polynomial algorithm. (Joint work with Philipp Warode)

Break

Time: Monday, May 10th - 16:00 h s.t.

Colloquium: Aniket Shah (Ohio State University)

Title: A q-analogue of Brion's identity

Abstract:

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.
--------------D50532DAD8442909C2F28B0D-- From rote@zedat.fu-berlin.de Mon May 10 16:32:03 2021 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 1lg6ww-001s54-PF; Mon, 10 May 2021 16:31:58 +0200 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 1lg6ww-0048oX-Mi; Mon, 10 May 2021 16:31:58 +0200 Received: from dslb-094-222-013-103.094.222.pools.vodafone-ip.de ([94.222.13.103] helo=[192.168.178.35]) 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 1lg6ww-0009bQ-FR; Mon, 10 May 2021 16:31:58 +0200 References: To: facets-of-complexity@lists.fu-berlin.de From: =?UTF-8?Q?G=c3=bcnter_Rote?= X-Forwarded-Message-Id: Message-ID: <33b2a2e5-57f6-064a-682c-e6f35dffe157@inf.fu-berlin.de> Date: Mon, 10 May 2021 18:32:27 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101 Thunderbird/78.10.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 8bit X-Original-Sender: rote@inf.fu-berlin.de X-Originating-IP: 94.222.13.103 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1620657118-000004C8-7D1FF6C3/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.004666, 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 Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Today Monday Colloquium - May 10th 2021 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, 10 May 2021 14:32:03 -0000 Today's colloquium talk was interrupted by technical problems. We are planning to postpone it to next Monday (May 17th) *_Time_: **Monday, **May 10th**- 16:00 h s.t.* (canceled) *_Colloquium_: Aniket Shah (Ohio State University)* *_Title_: A q-analogue of Brion's identity* *_Abstract_:* Rogers-Szegő polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0. From itabrunke@zedat.fu-berlin.de Wed May 12 18:33:57 2021 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 1lgro4-002VAN-RS; Wed, 12 May 2021 18:33:57 +0200 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 1lgro3-003LRt-4j; Wed, 12 May 2021 18:33:55 +0200 Received: from ip5f5af540.dynamic.kabel-deutschland.de ([95.90.245.64] 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 1lgro2-002ZRI-PZ; Wed, 12 May 2021 18:33:55 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 12 May 2021 18:33:54 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------FFD6A71E67E1975990C0F90D" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.245.64 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1620837236-000004C4-EBF7210C/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 X-Spam-Checker-Version: SpamAssassin 3.4.6 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture (possibly) & Colloquium - May 17th 2021 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 May 2021 16:33:57 -0000 This is a multi-part message in MIME format. --------------FFD6A71E67E1975990C0F90D Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture (possibly) & Colloquium on May 17th at 14:15 h & 16:00 h, online via Zoom. Due to technical difficulties we will have the Colloquium's talk from Monday 10th again this week, on Monday 17th. There possibly will also be a /random/ Lecture on Monday 17th. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, May 17th - 14:15 h */(po//tentially takling place)/ *_Lecture_: So far unknown speaker (**Universität Berlin**)* *_Title_: Random. * *_Abstract_:* /Random content./ *Break* *_Time_: **Monday, **May 17th**- 16:00 h s.t.* *_Colloquium_: Aniket Shah (Ohio State University)* *_Title_: A q-analogue of Brion's identity* *_Abstract_:* Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0. --------------FFD6A71E67E1975990C0F90D Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture (possibly) & Colloquium on May 17th at 14:15 h & 16:00 h, online via Zoom.

Due to technical difficulties we will have the Colloquium's talk from Monday 10th again this week, on Monday 17th.
There possibly will also be a random Lecture on Monday 17th.

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

Online via:
Zoom - Invitation

Time: Monday, May 17th - 14:15 h  (potentially takling place)

Lecture: So far unknown speaker (Universität Berlin)

Title: Random.

Abstract:

Random content.

Break

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

Colloquium: Aniket Shah (Ohio State University)

Title: A q-analogue of Brion's identity

Abstract:

Rogers-Szego polynomials are a family of orthogonal polynomials on the circle. We introduce a generalization of these polynomials which depend on the data of a polytope and prove a vertex sum formula for them when the polytope is smooth. This formula recovers Brion's formula when the parameter q is set to 0.

--------------FFD6A71E67E1975990C0F90D-- From itabrunke@zedat.fu-berlin.de Tue Jun 01 21:15:57 2021 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 1lo9rl-000xUJ-Eq; Tue, 01 Jun 2021 21:15:53 +0200 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 1lo9rl-000HSP-Bs; Tue, 01 Jun 2021 21:15:53 +0200 Received: from ip5f5af563.dynamic.kabel-deutschland.de ([95.90.245.99] 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 1lo9rl-001rS1-4V; Tue, 01 Jun 2021 21:15:53 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <86ad57cc-d699-1a0d-b45e-49174ace8319@inf.fu-berlin.de> Date: Tue, 1 Jun 2021 21:15:54 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------400AA6E9CA418AF49BAFBF4A" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.245.99 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1622574953-0002DEBE-E8EE27BB/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000010, 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: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture - June 7th 2021 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, 01 Jun 2021 19:15:57 -0000 This is a multi-part message in MIME format. --------------400AA6E9CA418AF49BAFBF4A Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture on June 7th at 14:15 h online via Zoom. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, June 7th - 14:15 h* *_Lecture_: Michael Joswig (Technische Universität Berlin**)* *_Title_: Tropical bisectors and Voronoi diagrams* *_Abstract_:* We consider norms in real vector spaces where the unit ball is an arbitrary convex polytope, possibly centrally symmetric.  In contrast with the Euclidean norm, the topological shape of bisectors may be complicated.  Our first main result is a formula for the Betti numbers of bisectors of three points in sufficiently general position. Specializing our results to the tropical polyhedral norm then yields structural results and algorithms for tropical Voronoi diagrams.  The tropical distance function plays a key role in current applications of tropical geometry. Joint work with Francisco Criado and Francisco Santos. --------------400AA6E9CA418AF49BAFBF4A Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture on June 7th at 14:15 h online via Zoom.

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

Online via:
Zoom - Invitation

Time: Monday, June 7th - 14:15 h

Lecture: Michael Joswig (Technische Universität Berlin)

Title: Tropical bisectors and Voronoi diagrams

Abstract:

We consider norms in real vector spaces where the unit ball is an arbitrary convex polytope, possibly centrally symmetric.  In contrast with the Euclidean norm, the topological shape of bisectors may be complicated.  Our first main result is a formula for the Betti numbers of bisectors of three points in sufficiently general position.
Specializing our results to the tropical polyhedral norm then yields structural results and algorithms for tropical Voronoi diagrams.  The tropical distance function plays a key role in current applications of tropical geometry.
Joint work with Francisco Criado and Francisco Santos.

--------------400AA6E9CA418AF49BAFBF4A-- From itabrunke@zedat.fu-berlin.de Wed Jun 09 19:32:37 2021 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 1lr249-0024AW-Jv; Wed, 09 Jun 2021 19:32:33 +0200 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 1lr249-001rFf-Gy; Wed, 09 Jun 2021 19:32:33 +0200 Received: from ip5f5af32f.dynamic.kabel-deutschland.de ([95.90.243.47] 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 1lr249-00418N-5z; Wed, 09 Jun 2021 19:32:33 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <31f00635-c69f-575b-5b23-ae04cfc3301a@inf.fu-berlin.de> Date: Wed, 9 Jun 2021 19:32:36 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------4C86F57C96E768FB5C4371B3" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.243.47 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1623259953-000325CA-BE4084A0/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.424239, 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 Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - June 14th 2021 - changed times. 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, 09 Jun 2021 17:32:37 -0000 This is a multi-part message in MIME format. --------------4C86F57C96E768FB5C4371B3 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 14th. *Attention: *Time is changed! /*Colloquium is at 14:45 h*/ & /*Lecture is at 16:30 h*/. Monday's Lecture & Colloquium will be online via Zoom, as used to. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, June 14th - _1__6__:__30_ h !!!* *_Lecture_: Alex Postnikov (MIT**)* *_Title_: Polypositroids* *_Abstract_:* Polypositroids is a class of convex polytopes defined to be those polytopes that are simultaneously generalized permutohedra (or polymatroids) and alcoved polytopes. Whereas positroids are the matroids arising from the totally nonnegative Grassmannian,polypositroids are "positive" polymatroids. We parametrize polypositroids using Coxeter necklaces and balanced graphs, and describe the cone of polypositroids by extremal rays and facet inequalities. We generalize polypositroids to an arbitrary finite Weyl group W, and connect them to cluster algebras and to generalized associahedra. We also discuss membranes, which are certain triangulated surfaces. They extend the notion of plabic graphs from positroids to polypositroids. The talk is based on a joint work with Thomas Lam. *Coffee Break!* *_Time_: **Monday, **June 14th**- _14:45_ h !!!* *_Colloquium_: Davide Lofano (Technische Universität Berlin)* *_Title_: Random Simple-Homotopy Theory* *_Abstract_:* A standard task in topology is to simplify a given finite presentation of a topological space. Bistellar flips allow to search for vertex-minimal triangulations of surfaces or higher-dimensional manifolds, and elementary collapses are often used to reduce a simplicial complex in size and potentially in dimension. Simple-homotopy theory, as introduced by Whitehead in 1939, generalizes both concepts. We take on a random approach to simple-homotopy theory and present a heuristic algorithm to combinatorially deform non-collapsible, but contractible complexes (such as triangulations of the dunce hat, Bing's house or non-collapsible balls that contain short knots) to a point. The procedure also allows to find substructures in complexes, e.g., surfaces in higher-dimensional manifolds or subcomplexes with torsion in lens spaces. (Joint work with Bruno Benedetti, Crystal Lai, and Frank Lutz.) --------------4C86F57C96E768FB5C4371B3 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 14th.

Attention: Time is changed! Colloquium is at 14:45 h & Lecture is at 16:30 h.

Monday's Lecture & Colloquium will be online via Zoom, as used to.

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

Online via:
Zoom - Invitation

Time: Monday, June 14th - 16:30 h !!!

Lecture: Alex Postnikov (MIT)

Title: Polypositroids

Abstract:

Polypositroids is a class of convex polytopes defined to be those polytopes that are simultaneously generalized permutohedra (or polymatroids) and alcoved polytopes. Whereas positroids are the matroids arising from the totally nonnegative Grassmannian,polypositroids are "positive" polymatroids. We parametrize polypositroids using Coxeter necklaces and balanced graphs, and describe the cone of polypositroids by extremal rays and facet inequalities. We generalize polypositroids to an arbitrary finite Weyl group W, and connect them to cluster algebras and to generalized associahedra. We also discuss membranes, which are certain triangulated surfaces. They extend the notion of plabic graphs from positroids to polypositroids. The talk is based on a joint work with Thomas Lam.


Coffee Break!

Time: Monday, June 14th - 14:45 h !!!

Colloquium: Davide Lofano (Technische Universität Berlin)

Title: Random Simple-Homotopy Theory

Abstract:

A standard task in topology is to simplify a given finite presentation of a topological space. Bistellar flips allow to search for vertex-minimal triangulations of surfaces or higher-dimensional manifolds, and elementary collapses are often used to reduce a simplicial complex in size and potentially in dimension. Simple-homotopy theory, as introduced by Whitehead in 1939, generalizes both concepts.
We take on a random approach to simple-homotopy theory and present a heuristic algorithm to combinatorially deform non-collapsible, but contractible complexes (such as triangulations of the dunce hat, Bing's house or non-collapsible balls that contain short knots) to a point.
The procedure also allows to find substructures in complexes, e.g., surfaces in higher-dimensional manifolds or subcomplexes with torsion in lens spaces.
(Joint work with Bruno Benedetti, Crystal Lai, and Frank Lutz.)
--------------4C86F57C96E768FB5C4371B3-- From itabrunke@zedat.fu-berlin.de Tue Jun 15 18:14:19 2021 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 1ltBhf-0027gq-Gn; Tue, 15 Jun 2021 18:14:15 +0200 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 1ltBhf-0020qI-Dw; Tue, 15 Jun 2021 18:14:15 +0200 Received: from [95.90.245.133] (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 1ltBhf-003JnV-3A; Tue, 15 Jun 2021 18:14:15 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <3d7c37e0-fab0-c892-1136-afbdda612dd2@inf.fu-berlin.de> Date: Tue, 15 Jun 2021 18:14:15 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------0B1C3D14AAFFA0184CC58294" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.245.133 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1623773655-000363BA-F1073E01/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 X-Spam-Checker-Version: SpamAssassin 3.4.6 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - June 21 2021 - time is back to normal. 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, 15 Jun 2021 16:14:19 -0000 This is a multi-part message in MIME format. --------------0B1C3D14AAFFA0184CC58294 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 21st. Time is back to normal. Monday's Lecture & Colloquium will be online via Zoom, as used to. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, June 21st - 14:15 h* *_Lecture_: Alexey Pokrovskiy (University College London)* *_Title_: Linear size Ramsey numbers of hypergraphs* *_Abstract_:* The size-Ramsey number of a hypergraph H is the minimum number of edges in a hypergraph G whose every 2-edge-colouring contains a monochromatic copy of H. This talk will be about showing that the size-Ramsey number of r-uniform tight path on n vertices is linear in n. Similar results about hypergraph trees and their powers will also be discussed. This is joint work with Letzter and Yepremyan. *Coffee Break!* *_Time_: **Monday, **June 21st**- 16:00 h s.t.* *_Colloquium_: Patrick Morris (Freie Universität Berlin)* *_Title_: Triangle factors in pseudorandom graphs* *_Abstract_:* An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set.  In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2. --------------0B1C3D14AAFFA0184CC58294 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 21st.

Time is back to normal. 

Monday's Lecture & Colloquium will be online via Zoom, as used to.

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

Online via:
Zoom - Invitation

Time: Monday, June 21st - 14:15 h

Lecture: Alexey Pokrovskiy (University College London)

Title: Linear size Ramsey numbers of hypergraphs

Abstract:

The size-Ramsey number of a hypergraph H is the minimum number of edges in a hypergraph G whose every 2-edge-colouring contains a monochromatic copy of H. This talk will be about showing that the size-Ramsey number of r-uniform tight path on n vertices is linear in n. Similar results about hypergraph trees and their powers will also be discussed. This is joint work with Letzter and Yepremyan.


Coffee Break!

Time: Monday, June 21st - 16:00 h s.t.

Colloquium: Patrick Morris (Freie Universität Berlin)

Title: Triangle factors in pseudorandom graphs

Abstract:

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set.  In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.
--------------0B1C3D14AAFFA0184CC58294-- From itabrunke@zedat.fu-berlin.de Wed Jun 23 16:09:46 2021 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 1lw3ZZ-002a4i-BK; Wed, 23 Jun 2021 16:09:45 +0200 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 1lw3ZZ-0024mx-8L; Wed, 23 Jun 2021 16:09:45 +0200 Received: from ip5f5af311.dynamic.kabel-deutschland.de ([95.90.243.17] 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 1lw3ZY-003Jlu-Tt; Wed, 23 Jun 2021 16:09:45 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <1b48ab60-e9d3-1c4b-63a6-59a53291e938@inf.fu-berlin.de> Date: Wed, 23 Jun 2021 16:09:46 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------339FA4DB2735BDFFB682D62A" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.243.17 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1624457385-000363BA-366B62C9/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.447244, 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 Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - June 28 2021. 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, 23 Jun 2021 14:09:46 -0000 This is a multi-part message in MIME format. --------------339FA4DB2735BDFFB682D62A Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 28 th. Time is back to normal. Monday's Lecture & Colloquium will be online via Zoom, as used to. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, June 28th - 14:15 h* *_Lecture_: Xavier Allamigeon (Inria and Ecole Polytechnique)* *_Title_: Formalizing the theory of polyhedra in a proof assistant* *_Abstract_:* In this talk, I will present the project Coq-Polyhedra that aims at formalizing the theory of polyhedra as well as polyhedral computations in the proof assistant Coq. I will explain how the intuitionistic nature of the logic of a proof assistant like Coq requires to define basic properties of polyhedra in a quite different way than is usually done, by relying on a formal proof of the simplex method. I will also focus on the formalization of the faces of polyhedra, and present a mechanism which automatically introduces an appropriate representation of a polyhedron or a face, depending on the context of the proof. I will demonstrate the usability of this approach by establishing some of the most important combinatorial properties of faces, namely that they constitute a family of graded atomistic and coatomistic lattices closed under interval sublattices, as well as Balinski’s theorem on the d-connectedness of the graph of d-polytopes. Finally, I will discuss recent progress on the formal computation of the graph of a polytope directly within the proof assistant, thanks to a certified algorithm that checks a posteriori the output of Avis’ vertex enumeration library lrslib. Joint work with Quentin Canu, Ricardo D. Katz and Pierre-Yves Strub. *Coffee Break!* *_Time_: **Monday, **June 28th**- 16:00 h s.t.* *_Colloquium_: Gorav Jindal (Technische Universität Berlin)* *_Title_: Arithmetic Circuit Complexity of Division and Truncation* *_Abstract_:* Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute.  We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy. This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found athttps://eccc.weizmann.ac.il/report/2021/072/ . --------------339FA4DB2735BDFFB682D62A Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on June 28 th.

Time is back to normal. 

Monday's Lecture & Colloquium will be online via Zoom, as used to.

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

Online via:
Zoom - Invitation

Time: Monday, June 28th - 14:15 h

Lecture: Xavier Allamigeon (Inria and Ecole Polytechnique)

Title: Formalizing the theory of polyhedra in a proof assistant

Abstract:

In this talk, I will present the project Coq-Polyhedra that aims at formalizing the theory of polyhedra as well as polyhedral computations in the proof assistant Coq.
I will explain how the intuitionistic nature of the logic of a proof assistant like Coq requires to define basic properties of polyhedra in a quite different way than is usually done, by relying on a formal proof of the simplex method. I will also focus on the formalization of the faces of polyhedra, and present a mechanism which automatically introduces an appropriate representation of a polyhedron or a face, depending on the context of the proof. I will demonstrate the usability of this approach by establishing some of the most important combinatorial properties of faces, namely that they constitute a family of graded atomistic and coatomistic lattices closed under interval sublattices, as well as Balinski’s theorem on the d-connectedness of the graph of d-polytopes. Finally, I will discuss recent progress on the formal computation of the graph of a polytope directly within the proof assistant, thanks to a certified algorithm that checks a posteriori the output of Avis’ vertex enumeration library lrslib.
Joint work with Quentin Canu, Ricardo D. Katz and Pierre-Yves Strub.


Coffee Break!

Time: Monday, June 28th - 16:00 h s.t.

Colloquium: Gorav Jindal (Technische Universität Berlin)

Title: Arithmetic Circuit Complexity of Division and Truncation

Abstract:

Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)).
The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute.  We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy.
This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/ . --------------339FA4DB2735BDFFB682D62A-- From itabrunke@zedat.fu-berlin.de Tue Jun 29 17:02:57 2021 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 1lyFGL-001pRU-97; Tue, 29 Jun 2021 17:02:57 +0200 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 1lyFGK-003sju-SH; Tue, 29 Jun 2021 17:02:56 +0200 Received: from ip5f5af32a.dynamic.kabel-deutschland.de ([95.90.243.42] 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 1lyFGK-002Qkh-He; Tue, 29 Jun 2021 17:02:56 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <2e2b38a2-4dbf-1a85-fbd8-1e0fa8e54027@inf.fu-berlin.de> Date: Tue, 29 Jun 2021 17:02:56 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.5 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------7560A4D987F8378D0A650454" X-Original-Sender: i.brunke@inf.fu-berlin.de X-Originating-IP: 95.90.243.42 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1624978977-0002D63E-D21CC218/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.114015, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=-48.8 required=5.0 tests=ALL_TRUSTED,HTML_MESSAGE, HTML_OBFUSCATE_10_20 X-Spam-Checker-Version: SpamAssassin 3.4.6 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - July 5th 2021 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, 29 Jun 2021 15:02:57 -0000 This is a multi-part message in MIME format. --------------7560A4D987F8378D0A650454 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on July 5th at 14:15 h & 16:00 h, online via Zoom. Invitation link: https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09 No password is required. *_Online via_: Zoom - Invitation* *_Time_: **Monday, July 5th - 14:15 h* *_Lecture_: Papa Sissokho (Illinois State University)* *_Title_: Geometry of the minimal solutions of a linear Diophantine Equation* *_Abstract_:* Let a_1 ,...,a_n and b_1 ,...,b_m be fixed positive integers, and let S denote the set of all nonnegative integer solutions of the equation x_1 a_1 +...+x_n a_n =y_1 b_1 +...+y_m b_m . A solution (x_1 ,...,x_n ,y_1 ,...,y_m ) in S is called /minimal/ if it cannot be expressed as the sum of two nonzero solutions in S.  For each pair (i,j), with 1 ≤ i ≤ n and 1 ≤ j ≤ m, the solution whose only nonzero coordinates are x_i = b_j and y_j = a_i is called a /generator/.  We show that every minimal solution is a convex combination of the generators and the zero-solution. This proves a conjecture of Henk-Weismantel and, independently, Hosten-Sturmfels. * Break!* *_Time_: **Monday, **July 5th**- 16:00 h s.t.* *_Colloquium_: Ansgar Freyer (Technische Universität Berlin)* *_Title_: Shaking a convex body in order to count its lattice points* *_Abstract_:* We prove inequalities on the number of lattice points inside a convex body K in terms of its volume and its successive minima. The successive minima of a convex body have been introduced by Minkowski and since then, they play a major role in the geometry of numbers. A key step in the proof is a technique from convex geometry known as Blascke's shaking procedure by which the problem can be reduced to anti-blocking bodies, i.e., convex bodies that are "located in the corner of the positive orthant". As a corollary of our result, we will obtain an upper bound on the number of lattice points in K in terms of the successive minima, which is equivalent to Minkowski's Second Theorem, giving a partial answer to a conjecture by Betke et al. from 1993. This is a joint work with Eduardo Lucas Marín. --------------7560A4D987F8378D0A650454 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on July 5th at 14:15 h & 16:00 h, online via Zoom.

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

Online via:
Zoom - Invitation

Time: Monday, July 5th - 14:15 h

Lecture: Papa Sissokho (Illinois State University)

Title: Geometry of the minimal solutions of a linear Diophantine Equation

Abstract:

Let a1,...,an and b1,...,bm be fixed positive integers, and let S denote the set of all nonnegative integer solutions of the equation x1a1+...+xnan=y1b1+...+ymbm. A solution (x1,...,xn,y1,...,ym) in S is called minimal if it cannot be expressed as the sum of two nonzero solutions in S.  For each pair (i,j), with 1 ≤ i ≤ n and 1 ≤ j ≤ m, the solution whose only nonzero coordinates are xi = bj and yj = ai is called a generator.  We show that every minimal solution is a convex combination of the generators and the zero-solution. This proves a conjecture of Henk-Weismantel and, independently, Hosten-Sturmfels.


Break!

Time: Monday, July 5th - 16:00 h s.t.

Colloquium: Ansgar Freyer (Technische Universität Berlin)

Title: Shaking a convex body in order to count its lattice points

Abstract:

We prove inequalities on the number of lattice points inside a convex body K in terms of its volume and its successive minima. The successive minima of a convex body have been introduced by Minkowski and since then, they play a major role in the geometry of numbers.
A key step in the proof is a technique from convex geometry known as Blascke's shaking procedure by which the problem can be reduced to anti-blocking bodies, i.e., convex bodies that are "located in the corner of the positive orthant".
As a corollary of our result, we will obtain an upper bound on the number of lattice points in K in terms of the successive minima, which is equivalent to Minkowski's Second Theorem, giving a partial answer to a conjecture by Betke et al. from 1993.
This is a joint work with Eduardo Lucas Marín.
--------------7560A4D987F8378D0A650454--