From rote@inf.fu-berlin.de Fri Apr 12 14:28:42 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hEvIQ-001XPG-0O>; Fri, 12 Apr 2019 14:28:42 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hEvIP-002rSx-Ta>; Fri, 12 Apr 2019 14:28:41 +0200 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hEvIP-002AtN-Jq>; Fri, 12 Apr 2019 14:28:41 +0200 From: =?UTF-8?Q?G=c3=bcnter_Rote?= References: <7f002bd3-b362-9102-de49-adeb94711989@inf.fu-berlin.de> To: facets-of-complexity@lists.fu-berlin.de Message-ID: <4b6987b1-9099-380d-b3c0-9a1cd494d4e3@inf.fu-berlin.de> Date: Fri, 12 Apr 2019 14:28:41 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 In-Reply-To: <7f002bd3-b362-9102-de49-adeb94711989@inf.fu-berlin.de> Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit X-Originating-IP: 160.45.40.209 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1555072122-00015767-4F436A9F/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000049, 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.2 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquium - April 15, 2019 at FU Berlin 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, 12 Apr 2019 12:28:42 -0000 You are invited to our Monday Lecture & Colloquium on April 15th, 2019 at 14:15 h & 16:00 h at FU Berlin. Lecture: Monday, April 15th - 14:15 h =============================================== Kaie Kubjas (Sorbonne Université Paris): Nonnegative rank four boundaries =============================================== Abstract: Matrices of nonnegative rank at most r form a semialgebraic set. This semialgebraic set is understood for r=1,2,3. In this talk, I will recall what was previously known about this semialgebraic set and present recent results on the boundaries of the set of matrices of nonnegative rank at most four using notions from the rigidity theory of frameworks. These results are joint work with Robert Krone. In the nonnegative rank-3 case, all boundaries are trivial or consist of matrices that have only infinitesimally rigid factorizations. For arbitrary nonnegative rank, we give a necessary condition on zero entries of a nonnegative factorization for the factorization to be infinitesimally rigid, and we show that in the case of 5×5 matrices of nonnegative rank four, there exists an infinitesimally rigid realization for every zero pattern that satisfies this necessary condition. However, the nonnegative rank-4 case is much more complicated than the nonnegative rank-3 case, and there exist matrices on the boundary that have factorizations that are not infinitesimally rigid. We discuss two such examples. Coffee & Tea Break: Room 134 Colloquium: 16:00 h ====================================================================== Josué Tonelli-Cueto (Technische Universität Berlin): Condition meets Computational Geometry: The Plantinga-Vegter algorithm ====================================================================== Abstract: The Plantinga-Vegter algorithm is a subdivision algorithm that produces an isotopic approximation of implicit smooth curves in the plane (and also of surfaces in three-dimensional space). Despite remarkable practical success of the algorithm, little was known about its complexity. The only existing complexity analysis due to Burr, Gao and Tsigaridas provides worst-case bounds that are exponential both in the degree and the bit size of the input polynomial. Despite being tight, this worst-case bound doesn't explain why the algorithm is efficient in practice. In this talk, we show how condition numbers, combined with techniques from geometric functional analysis, help to solve this issue. This is joint work with Alperen A. Ergür and Felipe Cucker. =============================================================== Location: Room 005 - Ground Floor Freie Universität Berlin, Department of Computer Science Takustr. 9 14195 Berlin From i.brunke@inf.fu-berlin.de Wed Apr 24 18:39:34 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hJKvl-001tba-Qt>; Wed, 24 Apr 2019 18:39:33 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hJKvl-000meq-O6>; Wed, 24 Apr 2019 18:39:33 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hJKvl-001yfT-IH>; Wed, 24 Apr 2019 18:39:33 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <8230e068-70b9-3b72-851a-69804eec0b49@inf.fu-berlin.de> Date: Wed, 24 Apr 2019 18:39:33 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------F45305BC7659D95BC2B101B9" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1556123973-000121DE-70ACBC6B/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.134641, 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.2 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - April 29th 2019 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, 24 Apr 2019 16:39:34 -0000 This is a multi-part message in MIME format. --------------F45305BC7659D95BC2B101B9 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on April 29th at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, April 29th - 14:15 h* *_Lecture_: Kolja Knauer (Aix-Marseille Université) * *_Title_: Tope graphs of (Complexes of) Oriented Matroids * *_Abstract_:* Tope graphs of Complexes of Oriented Matroids fall into the important class of metric graphs called partial cubes. They capture a variety of interesting graphs such as flip graphs of acyclic orientations of a graph, linear extension graphs of a poset, region graphs of hyperplane arrangements to name a few. After a soft introduction into oriented matroids and tope graphs, we give two purely graph theoretical characterizations of tope graphs of Complexes of Oriented Matroids. The first is in terms of a new notion of excluded minors for partial cube, the second is in terms of classical metric properties of certain so-called antipodal subgraphs. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we give a polynomial time recognition algorithms for tope graphs, which solves a relatively long standing open question. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory. Based on joint work with H.-J; Bandelt, V. Chepoi, and T. Marc. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor***[British Reading]* * *_Time_: **Monday, ***April 29th* - 16:00 h s.t.* *_Colloquium_: Torsten Mütze (Technische Universität Berlin**)* *_Title_: Combinatorial generation via permutation languages * *_Abstract_:* In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an n-element set by adjacent transpositions; the binary reflected Gray code to generate all n-bit strings by flipping a single bit in each step; the Gray code for generating all n-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an n-element ground set by element exchanges due to Kaye. The first main application of our framework are permutation patterns, yielding new Gray codes for different pattern-avoiding permutations, such as vexillary, skew-merged, X-shaped, separable, Baxter and twisted Baxter permutations etc. We also obtain new Gray codes for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to different restrictions. The second main application of our framework are lattice congruences of the weak order on the symmetric group S_n. Recently, Pilaud and Santos realized all those lattice congruences as (n-1)-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian. This is joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams.// --------------F45305BC7659D95BC2B101B9 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on April 29th at 14:15 h & 16:00 h at TU Berlin.

Location:

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

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

Lecture: Kolja Knauer (Aix-Marseille Université)

Title: Tope graphs of (Complexes of) Oriented Matroids

Abstract:

Tope graphs of Complexes of Oriented Matroids fall into the important class of metric graphs called partial cubes. They capture a variety of interesting graphs such as flip graphs of acyclic orientations of a graph, linear extension graphs of a poset, region graphs of hyperplane arrangements to name a few. After a soft introduction into oriented matroids and tope graphs, we give two purely graph theoretical characterizations of tope graphs of Complexes of Oriented Matroids. The first is in terms of a new notion of excluded minors for partial cube, the second is in terms of classical metric properties of certain so-called antipodal subgraphs. Corollaries include a characterization of topes of oriented matroids due to da Silva, another one of Handa, a characterization of lopsided systems due to Lawrence, and an intrinsic characterization of tope graphs of affine oriented matroids. Moreover, we give a polynomial time recognition algorithms for tope graphs, which solves a relatively long standing open question. I will try to furthermore give some perspectives on classical problems as Las Vergnas simplex conjecture in terms of Metric Graph Theory.
Based on joint work with H.-J; Bandelt, V. Chepoi, and T. Marc.

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]


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

Colloquium: Torsten Mütze (Technische Universität Berlin)

Title: Combinatorial generation via permutation languages

Abstract:
In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. In particular, we obtain the following four classical Gray codes as special cases: the Steinhaus-Johnson-Trotter algorithm to generate all permutations of an n-element set by adjacent transpositions; the binary reflected Gray code to generate all n-bit strings by flipping a single bit in each step; the Gray code for generating all n-vertex binary trees by rotations due to Lucas, van Baronaigien, and Ruskey; the Gray code for generating all partitions of an n-element ground set by element exchanges due to Kaye. The first main application of our framework are permutation patterns, yielding new Gray codes for different pattern-avoiding permutations, such as vexillary, skew-merged, X-shaped, separable, Baxter and twisted Baxter permutations etc. We also obtain new Gray codes for five different types of geometric rectangulations, also known as floorplans, which are divisions of a square into n rectangles subject to different restrictions. The second main application of our framework are lattice congruences of the weak order on the symmetric group S_n. Recently, Pilaud and Santos realized all those lattice congruences as (n-1)-dimensional polytopes, called quotientopes, which generalize hypercubes, associahedra, permutahedra etc. Our algorithm generates each of those lattice congruences, by producing a Hamilton path on the skeleton of the corresponding quotientope, yielding a constructive proof that each of these highly symmetric graphs is Hamiltonian.
This is joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams.
--------------F45305BC7659D95BC2B101B9-- From i.brunke@inf.fu-berlin.de Tue Apr 30 13:11:11 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hLQfG-001xSe-Ve>; Tue, 30 Apr 2019 13:11:11 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hLQfG-000Gbz-T2>; Tue, 30 Apr 2019 13:11:10 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hLQfF-000eoL-TO>; Tue, 30 Apr 2019 13:11:10 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <9cd52467-caf3-d94e-3cdb-cc6848dc027c@inf.fu-berlin.de> Date: Tue, 30 Apr 2019 13:11:09 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------A620DCED0A2FE03E72D88A04" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1556622670-0003289B-6E13ABF9/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.433548, 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.2 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - May 6th 2019 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, 30 Apr 2019 11:11:11 -0000 This is a multi-part message in MIME format. --------------A620DCED0A2FE03E72D88A04 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 6th at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, May 6th - 14:15 h* *_Lecture_: Matthias Köppe (University of California) * *_Title_: Facets of cut-generating functionology * *_Abstract_:* In the theory of valid inequalities for integer point sets in polyhedra, the traditional, finite-dimensional techniques of polyhedral combinatorics are complemented by infinite-dimensional methods, the study of cut-generating functions. I will give an introduction to these methods and will explain their connection tolattice-free convex bodies. I will present recent results involving inverse semigroups of partial maps, obtained jointly with Robert Hildebrand and Yuan Zhou, and highlight some open questions regarding computability and complexity. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor***[British Reading]* * *_Time_: **Monday, ***May 6th* - 16:00 h s.t.* *_Colloquium_: Tillmann Miltzow (Universität Utrecht**)* *_Title_: Smoothed Analysis of the Art Gallery Problem * *_Abstract_:* In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation.Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude \delta of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ER-complete problem was analyzed by Smoothed Analysis. This is joint work with Michael Dobbins and Andreas Holmsen. --------------A620DCED0A2FE03E72D88A04 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on May 6th at 14:15 h & 16:00 h at TU Berlin.

Location:

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

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

Lecture: Matthias Köppe (University of California)

Title: Facets of cut-generating functionology

Abstract:

In the theory of valid inequalities for integer point sets in polyhedra, the traditional, finite-dimensional techniques of polyhedral combinatorics are complemented by infinite-dimensional methods, the study of cut-generating functions. I will give an introduction to these methods and will explain their connection tolattice-free convex bodies. I will present recent results involving inverse semigroups of partial maps, obtained jointly with Robert Hildebrand and Yuan Zhou, and highlight some open questions regarding computability and complexity.

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]


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

Colloquium: Tillmann Miltzow (Universität Utrecht)

Title: Smoothed Analysis of the Art Gallery Problem

Abstract:
In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n vertices and a number k. We want to find a guard set G of size k, such that each point in P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg is fully contained inside the polygon P. The history and practical findings indicate that irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation.Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical performance of algorithms, even if they perform badly in the worst case. The idea is to study the expected performance on small perturbations of the worst input. The performance is measured in terms of the magnitude \delta of the perturbation and the input size. We consider four different models of perturbation. We show that the expected number of bits to describe optimal guard positions per guard is logarithmic in the input and the magnitude of the perturbation. This shows from a theoretical perspective that rational guards with small bit-complexity are typical. Note that describing the guard position is the bottleneck to show NP-membership. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an ER-complete problem was analyzed by Smoothed Analysis.
This is joint work with Michael Dobbins and Andreas Holmsen.
--------------A620DCED0A2FE03E72D88A04-- From i.brunke@inf.fu-berlin.de Fri May 10 13:45:23 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hP3xr-001AVb-0s>; Fri, 10 May 2019 13:45:23 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hP3xq-001x7o-Us>; Fri, 10 May 2019 13:45:22 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hP3xq-003dvK-HU>; Fri, 10 May 2019 13:45:22 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Fri, 10 May 2019 13:45:22 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------0343BFB8379D929C261676F0" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1557488723-000EC860-B966C324/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.2 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - May 13th 2019 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, 10 May 2019 11:45:23 -0000 This is a multi-part message in MIME format. --------------0343BFB8379D929C261676F0 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 13th at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, May 13th - 14:15 h* *_Lecture_: Boaz Slomka (Weizmann Institute of Science, Rehovot Israel) * *_Title_: On Hadwiger's covering conjecture * *_Abstract_:* A long-standing open problem, known as Hadwiger’s covering problem, asks what is the smallest natural number N(n) such that every convex body in {\mathbb R}^n can be covered by a union of the interiors of at most N(n) of its translates. In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a new general upper bound for N(n). _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor***[British Reading]* * *_Time_: **Monday, ***May 13th* - 16:00 h s.t.* *_Colloquium_: Fei Xue (Technische Universität Berlin**)* *_Title_: On the lattice point covering problem in dimension 2 * *_Abstract_:* We say that a convex body K has the lattice point covering property, if K contains a lattice point of Z^n in any position, i.e., in any translation and rotation of K. In this talk we discuss the lattice point covering property of some regular polygons in dimension 2. --------------0343BFB8379D929C261676F0 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on May 13th at 14:15 h & 16:00 h at TU Berlin.

Location:

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

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

Lecture: Boaz Slomka (Weizmann Institute of Science, Rehovot Israel)

Title: On Hadwiger's covering conjecture

Abstract:
A long-standing open problem, known as Hadwiger’s covering problem, asks what is the smallest natural number N(n) such that every convex body in {\mathbb R}^n can be covered by a union of the interiors of at most N(n) of its translates.
In this talk, I will discuss some history of this problem and its close relatives, and present more recent results, including a new general upper bound for N(n).

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]


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

Colloquium: Fei Xue (Technische Universität Berlin)

Title: On the lattice point covering problem in dimension 2

Abstract:
We say that a convex body K has the lattice point covering property, if K contains a lattice point of Z^n in any position, i.e., in any translation and rotation of K. In this talk we discuss the lattice point covering property of some regular polygons in dimension 2.
--------------0343BFB8379D929C261676F0-- From itabrunke@zedat.fu-berlin.de Fri May 17 16:42:36 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hRe4B-0049e9-OG>; Fri, 17 May 2019 16:42:35 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hRe4B-003GUZ-Lz>; Fri, 17 May 2019 16:42:35 +0200 Received: from webmail1.zedat.fu-berlin.de ([130.133.4.91] helo=webmail.zedat.fu-berlin.de) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hRe4B-002ECC-Gp>; Fri, 17 May 2019 16:42:35 +0200 Received: from 95.91.210.55 (ZEDAT-Webmail authenticated user itabrunke) by webmail.zedat.fu-berlin.de with HTTP; Fri, 17 May 2019 16:42:35 +0200 Message-ID: <2353.95.91.210.55.1558104155.webmail@webmail.zedat.fu-berlin.de> Date: Fri, 17 May 2019 16:42:35 +0200 From: "Ita Brunke" To: facets-of-complexity@lists.fu-berlin.de User-Agent: ZEDAT-Webmail MIME-Version: 1.0 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: 8bit X-Originating-IP: 130.133.4.91 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1558104155-000A200A-AA4C9F0B/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.264967, 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.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - May 20th 2019 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, 17 May 2019 14:42:36 -0000 You are cordially invited to our next Monday Lecture & Colloquium on May 20th at 14:15 h & 16:00 h at TU Berlin. Location: Room MA 041 - Ground Floor Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, May 20th - 14:15 h Lecture: Matthew Kahle (Ohio State University) Title: Configuration spaces of hard disks in an infinite strip Abstract: This is joint work with Bob MacPherson. We study the configuration space config(n,w) of n non-overlapping disks of unit diameter in an infinite strip of width w. Our main result establishes the rate of growth of the Betti numbers for fixed j and w as n → ∞. We identify three regions in the (j,w) plane exhibiting qualitatively different topological behavior. We describe these regions as (1) a “gas” regime where homology is stable, (2) a “liquid” regime where homology is unstable, and (3) a “solid” regime where homology is trivial. We describe the boundaries between stable, unstable, and trivial homology for every n ≥ 3. Coffee & Tea Break : Room MA 316 - Third Floor [British Reading] Time: Monday, May 20th - 16:00 h s.t. Colloquium: Davide Lofano (Technische Universität Berlin) Title: Collapsible vs Contractible Abstract: Probably the most studied invariant in Topological Data Analysis is the homology of a space. The usual approach is to triangulate the space and try to reduce it in order to make the computations more feasible. A common reduction technique is that of collapsing. In a collapsing process we perform a sequence of elementary collapses, where at each step we delete a free face and the unique facet containing it. If we are able to reduce a complex to one of its vertices then we say it is collapsible and its homology is trivial. Collapsibility implies that the space is contractible but the converse is not always true, probably the best known example is the Dunce Hat. We are going to explore the difference between these two concepts and look for minimal examples of contractible non collapsible complexes in each dimension and how often they arise. From i.brunke@inf.fu-berlin.de Fri May 24 12:57:24 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hU7t5-003DWC-Hh>; Fri, 24 May 2019 12:57:23 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hU7t5-000j5L-F8>; Fri, 24 May 2019 12:57:23 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hU7t5-002sGD-9g>; Fri, 24 May 2019 12:57:23 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Fri, 24 May 2019 12:57:23 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.6.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------F67A313D5F06BB1B277B7077" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1558695443-00079AB3-8148A90E/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.059361, 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.2 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - May 27th 2019 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 May 2019 10:57:24 -0000 This is a multi-part message in MIME format. --------------F67A313D5F06BB1B277B7077 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 27th at 14:15 h & 16:00 h at TU Berlin. *_Location_**: ** * *Room MA 041 - Ground Floor* Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin *_Time_: **Monday, May 27th - 14:15 h* *_Lecture_: William T. Trotter (Georgia Institute of Technology) * *_Title_: Stability Analysis for Posets * *_Abstract_:* Trivially, the maximum chromatic number of a graph on n vertices is n, and the only graph which achieves this value is the complete graph  K_n. It is natural to ask whether this result is "stable", i.e.,  if n is large, G  has n vertices and the chromatic number of G is close to n, must G  be close to being a complete graph? It is easy to see that for each  c>0, if  G  has n  vertices and chromatic number at least  n−c, then it contains a clique whose size is at least  n−2c. We will consider the analogous questions for posets and dimension.  Now the discussion will really become interesting. _*Coffee & Tea Break*_*:* *R**oom MA 316 - Third Floor***[British Reading]* * *_Time_: **Monday, ***May 27th* - 16:00 h s.t.* *_Colloquium_: Felix Schröder (Technische Universität Berlin**)* *_Title_: Lower Bounds on the p-centered coloring number * *_Abstract_:* A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity.  We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number  is in Theta(p log p). We have examples of graphs of treewidth k needing  (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz. We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz. --------------F67A313D5F06BB1B277B7077 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on May 27th at 14:15 h & 16:00 h at TU Berlin.

Location:

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

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

Lecture: William T. Trotter (Georgia Institute of Technology)

Title: Stability Analysis for Posets

Abstract:
Trivially, the maximum chromatic number of a graph on n vertices is n, and the only graph which achieves this value is the complete graph  K_n.  It is natural to ask whether this result is "stable", i.e.,  if n  is large, G  has n vertices and the chromatic number of G is close to n, must G  be close to being a complete graph? It is easy to see that for each  c>0, if  G  has n  vertices and chromatic number at least  n−c, then it contains a clique whose size is at least  n−2c. We will consider the analogous questions for posets and dimension.  Now the discussion will really become interesting.

Coffee & Tea Break :

Room MA 316 - Third Floor [British Reading]


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

Colloquium: Felix Schröder (Technische Universität Berlin)

Title: Lower Bounds on the p-centered coloring number

Abstract:

A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity.  We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number  is in Theta(p log p). We have examples of graphs of treewidth k needing  (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz. We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz.

--------------F67A313D5F06BB1B277B7077-- From newman.534@buckeyemail.osu.edu Fri May 31 15:18:28 2019 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hWhQS-001waY-4X>; Fri, 31 May 2019 15:18:28 +0200 Received: from mail-eopbgr820129.outbound.protection.outlook.com ([40.107.82.129] helo=NAM01-SN1-obe.outbound.protection.outlook.com) by relay1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-SHA384:256) (envelope-from ) id <1hWhQR-000qzh-PR>; Fri, 31 May 2019 15:18:28 +0200 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=buckeyemail.osu.edu; s=selector2; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=8GeaJnTFZzaw9lYd977lHBB1pd99W4ofTw7/yFPNB8U=; b=DrKrJLcocANLDD5TjeCPu1LEUovhXHKhz60o22isbRbYajRMLyQXWIpYw1pU6QLyi8EHok42ZQgjposxdVxnqdGvVguF2Ves8L53qw/B998QSO2hs0lSeN5nPtGfhuwVBpIX7uC8JezosbznZm0UArn03n+Iy8sW1Wex55gsF9s= Received: from BYAPR01MB4069.prod.exchangelabs.com (52.135.237.18) by BYAPR01MB4517.prod.exchangelabs.com (20.177.229.159) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1922.17; Fri, 31 May 2019 13:18:22 +0000 Received: from BYAPR01MB4069.prod.exchangelabs.com ([fe80::5195:4c8b:f1f1:52b0]) by BYAPR01MB4069.prod.exchangelabs.com ([fe80::5195:4c8b:f1f1:52b0%7]) with mapi id 15.20.1922.021; Fri, 31 May 2019 13:18:22 +0000 From: "Newman, Andrew" To: "facets-of-complexity@lists.fu-berlin.de" Thread-Topic: Reminder about Math+ conference Thread-Index: AQHVF7Ls/ilS31Lplkytcf50+xiJxA== Date: Fri, 31 May 2019 13:18:22 +0000 Message-ID: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: spf=none (sender IP is ) smtp.mailfrom=newman.534@buckeyemail.osu.edu; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: d60e6f3b-dc51-4f6f-2cfa-08d6e5ca74c7 x-microsoft-antispam: BCL:0; PCL:0; RULEID:(2390118)(7020095)(4652040)(8989299)(4534185)(4627221)(201703031133081)(201702281549075)(8990200)(5600148)(711020)(4605104)(1401327)(2017052603328)(7193020); SRVR:BYAPR01MB4517; x-ms-traffictypediagnostic: BYAPR01MB4517: x-ms-exchange-purlcount: 1 x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:8882; x-forefront-prvs: 00540983E2 x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(366004)(396003)(39860400002)(376002)(136003)(346002)(189003)(199004)(53336002)(236005)(76116006)(14454004)(606006)(186003)(52536014)(5640700003)(2906002)(6436002)(7736002)(3846002)(486006)(476003)(86362001)(5660300002)(68736007)(6606003)(25786009)(21615005)(54896002)(316002)(53936002)(66066001)(6116002)(33656002)(256004)(6916009)(19627405001)(75432002)(71190400001)(8676002)(71200400001)(2501003)(73956011)(966005)(2351001)(64756008)(786003)(55016002)(74316002)(6506007)(478600001)(6306002)(9686003)(7696005)(4744005)(102836004)(88552002)(66446008)(66946007)(66476007)(81156014)(81166006)(26005)(8936002)(91956017)(99286004)(66556008); DIR:OUT; SFP:1102; SCL:1; SRVR:BYAPR01MB4517; H:BYAPR01MB4069.prod.exchangelabs.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1; received-spf: None (protection.outlook.com: buckeyemail.osu.edu does not designate permitted sender hosts) x-ms-exchange-senderadcheck: 1 x-microsoft-antispam-message-info: KBLYlAjmLZ4ajj3JopTLmgWr2v+HkNfUkZKPn1AcEBpwkNVgJVFM15eDBMMucefuIv9ZfOGjyKljjWhgqTz3cttDEGXlUat6s+HR9ZzHFZP8UwrkwQjptQgLD1IqQ6x6WCey8JbPbAf+mgF8khFF9T54GPJ8VH4v+I7SmGcMHOPZ/cD65C5yy9f27jarIoELPBG3HfXG6eR58QtfHHvZqEseS+FgccmMW3zBrfFHqF/4yseJFrk8FXQVQPCDd8vjGUBGmt6Pw6Pgp/VVxjZV020Nm/id6MxvrVzeJ6zh+9A2rMvJ2lXLZNAiX+Z3MXbjlkLpzbgqMRVxwPz/CSBwuM21UWdHUmUkSnTjnA+def989aFiRIgS63Q/Vm+inQnv12p9OKMQp5MxHMZjez4kIKQortJR0D6/VesfgW3Bsrw= Content-Type: multipart/alternative; boundary="_000_BYAPR01MB4069FAAC30BB24CA74FC296F8A190BYAPR01MB4069prod_" MIME-Version: 1.0 X-OriginatorOrg: buckeyemail.osu.edu X-MS-Exchange-CrossTenant-Network-Message-Id: d60e6f3b-dc51-4f6f-2cfa-08d6e5ca74c7 X-MS-Exchange-CrossTenant-originalarrivaltime: 31 May 2019 13:18:22.3869 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: eb095636-1052-4895-952b-1ff9df1d1121 X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: newman.534@buckeyemail.osu.edu X-MS-Exchange-Transport-CrossTenantHeadersStamped: BYAPR01MB4517 X-Originating-IP: 40.107.82.129 X-Original-X-Originating-IP: [130.149.12.144] X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1559308708-0002758D-E0D6D34F/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.352689, version=1.2.4 X-Spam-Flag: NO X-Spam-Status: No, score=0.2 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HTML_MESSAGE,RCVD_IN_DNSWL_BLOCKED,SPF_HELO_PASS,SPF_PASS,URIBL_BLOCKED X-Spam-Checker-Version: SpamAssassin 3.4.2 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: X-Mailman-Approved-At: Fri, 31 May 2019 15:26:24 +0200 Subject: [Facets-of-complexity] Reminder about Math+ conference 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, 31 May 2019 13:18:29 -0000 --_000_BYAPR01MB4069FAAC30BB24CA74FC296F8A190BYAPR01MB4069prod_ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Dear Facets of Complexity members, Next week, the International Conference on Network Games, Tropical Geometry= and Quantum Communication will be taking place from Monday to Friday at th= e Zuse Institute Berlin. More information can be found at https://www3.math= .tu-berlin.de/combi/dmg/TES-Summer2019/conference.html. All are invited to = participate. Due to the conference, the regular Facets of Complexity Monda= y Lectures will not take place. Best regards, Andrew --_000_BYAPR01MB4069FAAC30BB24CA74FC296F8A190BYAPR01MB4069prod_ Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

Dear Facets of Complexity member= s,


Next week, the International Con= ference on Network Games, Tropical Geometry and Quantum Communication will = be taking place from Monday to Friday at the Zuse Institute Berlin. More in= formation can be found at https://www3.math.tu-berlin.de/combi/dmg/TES-Summer2019/conference.html= . All are invited to participate.  Due to the conference, the regular = Facets of Complexity Monday Lectures will not take place.


Best regards,

Andrew

--_000_BYAPR01MB4069FAAC30BB24CA74FC296F8A190BYAPR01MB4069prod_-- From i.brunke@inf.fu-berlin.de Fri Jun 14 15:41:14 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hbmSA-0013Zc-54>; Fri, 14 Jun 2019 15:41:14 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hbmSA-002RLe-2W>; Fri, 14 Jun 2019 15:41:14 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hbmS9-001ODx-Ts>; Fri, 14 Jun 2019 15:41:14 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <57676037-5899-e94d-2cad-3213473d42ed@inf.fu-berlin.de> Date: Fri, 14 Jun 2019 15:41:13 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.7.0 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------73E0E384B595583E0FC6ECB6" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1560519674-000E3B09-1608F3E8/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.050096, 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.2 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture on June 17th 2019 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, 14 Jun 2019 13:41:14 -0000 This is a multi-part message in MIME format. --------------73E0E384B595583E0FC6ECB6 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture on June 17th at 14:15 h at FU Berlin. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, June 17th - 14:15 h* *_Lecture_: Matthias Beck (San Francisco State University**)* *_Title_: Lonely Runner Polyhedra * *_Abstract_:* We study the Lonely Runner Conjecture, conceived by Wills in the 1960's: Given positive integers n_1, n_2, ..., n_k, there exists a positive real number t such that for all 1 ≤ j ≤ k the distance of tn_j to the nearest integer is at least 1/(k+1). Continuing a view-obstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral ansatz to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture. _*Coffee & Tea*_*:**Room 134* /Exceptionally, there will be no Colloquium and only this Lecture./ --------------73E0E384B595583E0FC6ECB6 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture on June 17th at 14:15 h at FU Berlin.

Location:

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

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

Lecture: Matthias Beck (San Francisco State University)

Title: Lonely Runner Polyhedra

Abstract:

We study the Lonely Runner Conjecture, conceived by Wills in the 1960's: Given positive integers n_1, n_2, ..., n_k, there exists a positive real number t such that for all 1 ≤ j ≤ k the distance of tn_j to the nearest integer is at least 1/(k+1). Continuing a view-obstruction approach by Cusick and recent work by Henze and Malikiosis, our goal is to promote a polyhedral ansatz to the Lonely Runner Conjecture. Our results include geometric proofs of some folklore results that are only implicit in the existing literature, a new family of affirmative instances defined by the parities of the speeds, and geometrically motivated conjectures whose resolution would shed further light on the Lonely Runner Conjecture.


Coffee & Tea: Room 134

Exceptionally, there will be no Colloquium and only this Lecture.
--------------73E0E384B595583E0FC6ECB6-- From i.brunke@inf.fu-berlin.de Wed Jun 19 15:54:36 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hdb2p-001ygq-J5>; Wed, 19 Jun 2019 15:54:35 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hdb2p-003Nfe-GH>; Wed, 19 Jun 2019 15:54:35 +0200 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hdb2p-001vUe-AL>; Wed, 19 Jun 2019 15:54:35 +0200 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 19 Jun 2019 15:54:35 +0200 User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.7.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------85D45C57FA2D6B054666C25B" Content-Language: en-US X-Originating-IP: 160.45.40.245 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1560952475-0001A528-C0226491/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.235765, 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.2 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - June 24th 2019 X-BeenThere: facets-of-complexity@lists.fu-berlin.de X-Mailman-Version: 2.1.29 Precedence: list List-Id: announcements of Monday lectures and other events List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 19 Jun 2019 13:54:36 -0000 This is a multi-part message in MIME format. --------------85D45C57FA2D6B054666C25B 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 24th at 14:15 h & 16:00 h at FU Berlin. *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, June 24th - 14:15 h* *_Lecture_: Emo Welzl (ETH Zürich**)* *_Title_: Connectivity of Triangulation Flip Graphs in the Plane * *_Abstract_:* In a straight line embedded triangulation of a point set P in the plane, removing an inner edge and - provided the resulting quadrilateral Q is convex - adding the other diagonal is called an edge flip. The flip graph has all triangulations as vertices and a pair of triangulations is adjacent, if they can be obtained from each other by an edge flip. This presentation is towards a better understanding of this graph, with emphasis on its connectivity. It is known that every triangulation allows at least n/2-2 edge flips and we show (n/2-2)-vertex connectivity for flip graphs of all P in general position, n:=|P|. Somewhat stronger, but restricted to P large enough, we show that the vertex connectivity is determined by the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P.  A corresponding result is shown for so-called partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. Here the flip operation is extended to bistellar flips (edge flip, and insertion and removal of an inner vertex of degree three). We prove (n-3)-edge connectedness for all P in general position and (n-3)-vertex connectedness for n large enough ((n-3) is tight, since there is always a partial triangulation which allows exactly n-3 bistellar flips). This matches the situation known (through the secondary polytope) for regular triangulations (i.e. partial triangulations obtained by lifting the points and projecting the lower convex hull). This is joint work with Uli Wagner, IST Austria. _*Coffee & Tea Break*_*:* *Room 134* *_Time_: **Monday, **June 24th**- 16:00 h s.t.* *_Colloquium_: Simona Boyadzhiyska (Freie Universität Berlin**)* *_Title_: On counting problems related to (mutually) orthogonal Latin squares * *_Abstract_:* An n×n array with entries in [n] such that each integer appears exactly once in every row and every column is called a Latin square of order n. Two Latin squares L and L' are said to be orthogonal if, for all x,y∈[n], there is a unique pair (i,j) such that L(i,j) = x and L'(i,j) = y; k Latin squares are mutually orthogonal if any two of them are orthogonal.After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will present an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.This talk is based on joint work with Shagnik Das and Tibor Szabó. --------------85D45C57FA2D6B054666C25B Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on June 24th at 14:15 h & 16:00 h at FU Berlin.

Location:

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

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

Lecture: Emo Welzl (ETH Zürich)

Title: Connectivity of Triangulation Flip Graphs in the Plane

Abstract:

In a straight line embedded triangulation of a point set P in the plane, removing an inner edge and - provided the resulting quadrilateral Q is convex - adding the other diagonal is called an edge flip. The flip graph has all triangulations as vertices and a pair of triangulations is adjacent, if they can be obtained from each other by an edge flip. This presentation is towards a better understanding of this graph, with emphasis on its connectivity. It is known that every triangulation allows at least n/2-2 edge flips and we show (n/2-2)-vertex connectivity for flip graphs of all P in general position, n:=|P|. Somewhat stronger, but restricted to P large enough, we show that the vertex connectivity is determined by the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P.  A corresponding result is shown for so-called partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. Here the flip operation is extended to bistellar flips (edge flip, and insertion and removal of an inner vertex of degree three). We prove (n-3)-edge connectedness for all P in general position and (n-3)-vertex connectedness for n large enough ((n-3) is tight, since there is always a partial triangulation which allows exactly n-3 bistellar flips). This matches the situation known (through the secondary polytope) for regular triangulations (i.e. partial triangulations obtained by lifting the points and projecting the lower convex hull). This is joint work with Uli Wagner, IST Austria.


Coffee & Tea Break:
Room 134

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

Colloquium: Simona Boyadzhiyska (Freie Universität Berlin)

Title: On counting problems related to (mutually) orthogonal Latin squares

Abstract:

An n×n array with entries in [n] such that each integer appears exactly once in every row and every column is called a Latin square of order n. Two Latin squares L and L' are said to be orthogonal if, for all x,y∈[n], there is a unique pair (i,j) such that L(i,j) = x and L'(i,j) = y; k Latin squares are mutually orthogonal if any two of them are orthogonal.After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will present an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.This talk is based on joint work with Shagnik Das and Tibor Szabó.

--------------85D45C57FA2D6B054666C25B-- From itabrunke@zedat.fu-berlin.de Fri Jun 28 19:04:21 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hguIP-003Vq8-Cu>; Fri, 28 Jun 2019 19:04:21 +0200 Received: from inpost2.zedat.fu-berlin.de ([130.133.4.69]) by outpost.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from ) id <1hguIP-003Wrc-A9>; Fri, 28 Jun 2019 19:04:21 +0200 Received: from webmail1.zedat.fu-berlin.de ([130.133.4.91] helo=webmail.zedat.fu-berlin.de) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtps (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1hguIP-001Zl4-4o>; Fri, 28 Jun 2019 19:04:21 +0200 Received: from 95.91.210.63 (ZEDAT-Webmail authenticated user itabrunke) by webmail.zedat.fu-berlin.de with HTTP; Fri, 28 Jun 2019 19:04:21 +0200 Message-ID: <30182.95.91.210.63.1561741461.webmail@webmail.zedat.fu-berlin.de> Date: Fri, 28 Jun 2019 19:04:21 +0200 From: "Ita Brunke" To: facets-of-complexity@lists.fu-berlin.de User-Agent: ZEDAT-Webmail MIME-Version: 1.0 Content-Type: text/plain;charset=utf-8 Content-Transfer-Encoding: 8bit X-Originating-IP: 130.133.4.91 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1561741461-00036E15-B04272C3/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.056222, 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.2 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - July 1st 2019 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, 28 Jun 2019 17:04:21 -0000 You are cordially invited to our next Monday Lecture & Colloquium on July 1st at 14:15 h & 16:00 h at FU Berlin. Location: Room 005 - Ground Floor Freie Universität Berlin Takustr. 9 14195 Berlin Time: Monday, July 1st - 14:15 h Lecture: Rekha R. Thomas (University of Washington) Title: Graph Density Inequalities and Sums of Squares Abstract: Many results in extremal graph theory can be formulated as inequalities on graph densities. While many inequalites are known, many more are conjectured. A standard tool to establish an inequality is to write the expression whose nonnegativity needs to be certified as a sum of squares. This technique has had many successes but also limitations. In this talk I will describe new restrictions that show that several simple inequalities cannot be certified by sums of squares. These results extend to the powerful frameworks of flag algebras by Razborov and graph algebras by Lovasz and Szegedy. This is joint work with Greg Blekherman, Annie Raymond, and Mohit Singh. Coffee & Tea Break: Room 134 Time: Monday, July 1st - 16:00 h s.t. Colloquium: Manfred Scheucher (Technische Universität Berlin) Title: On Arrangements of Pseudocircles Abstract: Towards a better understanding of arrangements of circles and also to get rid of geometric difficulties, we look at the more general setting of ''arrangements of pseudocircles'' which was first introduced by Grünbaum in the 1970's. An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two points, where the two curves cross. In his book, Grünbaum conjectured that every digon-free arrangement of n pairwise intersecting pseudocircles contains at least $2n-4$ triangular cells. We present arrangements to disprove this conjecture and give new bounds on the number of triangular cells for various classes of arrangements. Furthermore, we study the ''circularizability'' of arrangements: it is clear that every arrangement of circles is an arrangement of pseudocircles, however, deciding whether an arrangement of pseudocircles is isomorphic to an arrangement of circles is computationally hard. Using a computer program, we have enumerated all combinatorially different arrangements of up to $7$ pseudocircles. For the class of arrangements of $5$ pseudocircles and for the class of digon-free intersecting arrangements of $6$ pseudocircles, we give a complete classification: we either provide a circle representation or a non-circularizability proof. For these proofs we use incidence theorems like Miquel's and arguments based on continuous deformation, where circles of an assumed circle representation grow or shrink in a controlled way. This talk summarizes results from two articles, which are both joint work with Stefan Felsner: * Arrangements of Pseudocircles: Triangles and Drawings; short version in Proc. GD'17; full version available at arXiv (1708.06449) * Arrangements of Pseudocircles: On Circularizability; short version in Proc. GD'18; full version in DCG: Ricky Pollack Memorial Issue (doi:10.1007/s00454-019-00077-y)