From rote@inf.fu-berlin.de Mon Jan 06 12:39:31 2020 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 <1ioQjK-0049td-QH>; Mon, 06 Jan 2020 12:39:30 +0100 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 <1ioQjK-003Ie8-Nq>; Mon, 06 Jan 2020 12:39:30 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1ioQjK-003W8k-IU>; Mon, 06 Jan 2020 12:39:30 +0100 To: Ita Brunke , facets-of-complexity@lists.fu-berlin.de References: <8d2e94c3-d657-27d1-8292-a9edefd2c5d9@inf.fu-berlin.de> From: =?UTF-8?Q?G=c3=bcnter_Rote?= Message-ID: <91e60edf-00ca-cf4f-8d46-4419dc31625b@inf.fu-berlin.de> Date: Mon, 6 Jan 2020 12:39:30 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 In-Reply-To: <8d2e94c3-d657-27d1-8292-a9edefd2c5d9@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::1578310770-000BAB21-2474BAF3/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000153, 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.3 on Tuvalu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - TODAY January 6 2020 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, 06 Jan 2020 11:39:31 -0000 Location: Room 005 - Ground Floor Freie Universität Berlin Institut für Informatik, Takustr. 9 14195 Berlin Time: Monday, Jan 6 - 14:15 h Lecturer: Frank Sottile (Texas University) Title: *Irrational toric varieties and the secondary polytope* Abstract: The secondary fan of a point configuration A in R^n encodes all regular subdivisions of A. These subdivisions also record all limiting objects obtained by weight degenerations of the irrational toric variety X_A parameterized by A. The secondary fan is the normal fan of the secondary polytope. We explain a functorial construction of R^n-equivariant cell complexes from fans that, when applied to the secondary fan, realizes the secondary polytope as the moduli space of translations and degenerations of X_A. This extends the work of Kapranov, Sturmfels and Zelevinsky (who established this for complex toric varieties when A is integral) to all real configurations A. Coffee & Tea Break: Room 134 Time: Monday, Jan 6 - 16:00 h s.t.* Colloquium: Lukas Kühne (Hebrew University of Jerusalem) Title: *Matroid representations by c-arrangements are undecidable* Abstract: A matroid is a combinatorial object based on an abstraction of linear independence in vector spaces and forests in graphs. It is a classical question to determine whether a given matroid is representable as a vector configuration over a field. Such a matroid is called linear. This talk is about a generalization of that question from vector configurations to c-arrangements. A c-arrangement for a fixed c is an arrangement of dimension c subspaces such that the dimensions of their sums are multiples of c. Matroids representable as c-arrangements are called multilinear matroids. We prove that it is algorithmically undecidable whether there exists a c such that a given matroid has a c-arrangement representation. In the proof, we introduce a non-commutative von Staudt construction to encode an instance of the uniform word problem for finite groups in matroids of rank three. The talk is based on joint work with Geva Yashfe. -- G"unter Rote (Germany=49)30-838-75150 (office) Freie Universit"at Berlin -75103 (secretary) Institut f"ur Informatik FAX (49)30-838-4-75150 Takustrase 9, D-14195 Berlin, GERMANY From rote@inf.fu-berlin.de Wed Jan 08 18:24:37 2020 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 <1ipF4P-001VSi-1y>; Wed, 08 Jan 2020 18:24:37 +0100 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 <1ipF4O-0020f3-VX>; Wed, 08 Jan 2020 18:24:36 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1ipF4O-000Ht7-Os>; Wed, 08 Jan 2020 18:24:36 +0100 From: =?UTF-8?Q?G=c3=bcnter_Rote?= References: <4b6987b1-9099-380d-b3c0-9a1cd494d4e3@inf.fu-berlin.de> To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 8 Jan 2020 18:24:36 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 In-Reply-To: <4b6987b1-9099-380d-b3c0-9a1cd494d4e3@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::1578504277-000A6214-5A306B8E/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.270077, 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.3 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquia - Jan 13, 2020 at TU 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: Wed, 08 Jan 2020 17:24:37 -0000 You are invited to our Monday Lecture & Colloquium on January 13, 2020 at 14:15 h & 16:00 h & 17:00 h at FU Berlin. Exceptionally, there will be *ANOTHER COLLOQUIUM* at 17:00. Lecture: Monday, April 15th - 14:15 h =============================================================== Eric Fusy (École Polytechnique Paris): Bijections between families of walks using oriented planar maps =============================================================== Abstract: When counting walks (with a given step-set), an equi-enumeration phenomenom is often observed between a stronger constraint on the domain and a stronger constraint on the position of the endpoint (a classical 1d example is the fact that positive walks of length 2n are in bijection with walks of length 2n ending at 0, both being counted by the central binomial coefficient). I will show examples of such relations for 2d walks where the equi-enumeration can be bijectively explained using planar maps endowed with certain orientations (Schnyder woods, bipolar orientations). Coffee & Tea Break: Room MA 316 - Third Floor First Colloquium: 16:00 h ========================================================= Andrei Asinowski (Universität Klagenfurt): The vectorial kernel method and patterns in lattice paths ========================================================= Abstract: A directed lattice path is a polygonal line which starts at the origin and consists of several vectors of the form (1, y) (where y belongs to a fixed set of integers) appended to each other. Enumeration of different kinds of lattice paths (walks/bridges/meanders /excursions) was accomplished by Banderier and Flajolet in 2002. We refine and generalize their results by studying lattice paths that avoid a fixed pattern (or several patterns). To this end, we develop a "vectorial kernel method" – a unified framework for enumeration of words generated by a counter automaton. Another improtant tool is the "autocorrelation polynomial" that encodes self-overlappings of a pattern, and its generalization: the "mutual correlation matrix" for several patterns. This talk is based on joint work with Cyril Banderier, Axel Bacher, Bernhard Gittenberger and Valerie Rointer. Second Colloquium: 17:00 h ============================================== Shahrzad Haddadan (MPI Informatik Saarbrücken): Algorithms for top-k lists and social networks ============================================== Abstract: Today’s massive and dynamic data sets have motivated many computer scientists and mathematicians to study classical problems in combinatorics and graph theory in various settings. In certain settings the algorithms’ access to the data is restricted while in others the resources are limited. In this talk we explore such settings in three directions: ranking of objects, property testing in social networks and finding communities in dynamic graphs. In the first part, we discuss algorithms on permutations as well as prefixes of permutations also known as top-k lists. The study of later particularly arises in big data scenarios when analysis of the entire permutation is costly or not interesting. We start by discussing random walks on the set of full rankings or permutations of n objects, a set whose size is n!. Since the 1990s to today, various versions of this problem have been studied, each for a different motivation. The second part of the talk is devoted to property testing in social networks: Given a graph, an algorithm seeks to approximate several parameters of a graph just by accessing the graph by means of oracles and while querying these oracles as few times as possible. We introduce a new oracle access model which is applicable to social networks, and assess the complexity of estimating parameters such as the number of users (vertices) in this model. In the third part of the talk, we introduce a new dynamic graph model which is based on triadic closure: a friendship is more likely to be formed between a pair of users with a larger number of mutual friends. We find upper bounds for the rate of graph evolution in this model and using such bounds we devise algorithms discovering communities. I will finish this talk by proposing new directions and presenting related open problems. ========================================================================================= Location: Room MA 041 (Ground Floor) Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin From rote@inf.fu-berlin.de Fri Jan 17 20:13:35 2020 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 <1isX3n-0030O8-7X>; Fri, 17 Jan 2020 20:13:35 +0100 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 <1isX3m-000Y0y-Cu>; Fri, 17 Jan 2020 20:13:34 +0100 Received: from strecke.imp.fu-berlin.de ([160.45.40.209]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1isX3m-001p0G-7X>; Fri, 17 Jan 2020 20:13:34 +0100 References: From: =?UTF-8?Q?G=c3=bcnter_Rote?= To: facets-of-complexity@lists.fu-berlin.de X-Forwarded-Message-Id: Message-ID: <7a930d6e-5671-053c-6708-e0a08d84f10f@inf.fu-berlin.de> Date: Fri, 17 Jan 2020 20:13:34 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 MIME-Version: 1.0 In-Reply-To: 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::1579288415-000525D6-FE1B5E7D/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000416, 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.3 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Monday Lecture & Colloquia - Jan 20, 2020 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, 17 Jan 2020 19:13:35 -0000 You are invited to our Monday Lecture & Colloquiums on January 20, 2020 at 14:15 h & 16:00 h & 17:00 h at FU Berlin. Exceptionally, there will be *ANOTHER COLLOQUIUM TALK* at 17:00. Lecture: Monday, January 20, 14:15 h ========================================== Holger Dell (IT University of Copenhagen): Counting and sampling small subgraphs ========================================== Abstract: We discuss various algorithmic techniques used for counting and sampling subgraphs in a large input graph. The focus of the talk is on the mathematical foundations. We start with the beautiful technique of color-coding (Alon, Yuster, Zwick 1995), and we discuss various generalizations based on group algebras (Koutis 2008) and on the exterior algebra (Brand, Dell, Husfeldt 2018). These techniques are most useful for sampling, which is equivalent to approximate counting. On the other hand, the fastest known algorithm to exactly count subgraphs that are isomorphic to a graph H (Curticapean, Dell, Marx 2017) is based on the foundations of Lovász' theory of graph limits. Coffee & Tea Break: Room 134 - First Floor First Colloquium: 16:00 h ========================================================== Alan Arroyo (Institute of Science and Technology Austria): Obstructions in graph drawings =========================================================? Abstract: Many nice results in graph theory involve the characterization of a graph class in terms of a set of forbidden obstructions. In this talk I will consider the problem of understanding whether a class of graph drawings can be characterized by a set of forbidden obstructions. I will do an overview on interesting recent results that fall under this theme, but I will emphasize more on those related to geometric arrangements. Second Colloquium: 17:00 h ========================================== Gorav Jindal (Aalto University, Helsinki): On the Complexity of Symmetric Polynomials ========================================== Abstract: The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_Sym in C[x1,x2,...,x_n], there exists a unique "witness" f in C[y1,y2,...,y_n] such that f_Sym=f(e1,e2,...,e_n), where the e_i's are the elementary symmetric polynomials. In this work, we study the arithmetic complexity L(f) of the witness f as a function of the arithmetic complexity L(f_Sym) of f_Sym. We show that the arithmetic complexity L(f) of f is bounded by poly(L(f_Sym),deg(f),n). Prior to this work, only exponential upper bounds were known for L(f). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series. As a corollary of this result, we show that if VP is not equal to VNP then there are symmetric polynomial families which have super-polynomial arithmetic complexity. This is joint work with Markus Bläser. ========================================================================================= Location: Seminar room 005 (Ground Floor) Freie Universität Berlin Institut für Informatik Takustr. 9, 14195 Berlin From i.brunke@inf.fu-berlin.de Wed Jan 22 15:46:43 2020 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 <1iuHHG-004ArB-Vu>; Wed, 22 Jan 2020 15:46:43 +0100 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 <1iuHHG-00205W-TB>; Wed, 22 Jan 2020 15:46:42 +0100 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 <1iuHHG-001R4F-KG>; Wed, 22 Jan 2020 15:46:42 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Wed, 22 Jan 2020 15:46:42 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------14F45A133C9C2900F1D8E40D" 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::1579704402-00099802-810CBC7A/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000042, 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.3 on Vanuatu.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 27th 2020 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, 22 Jan 2020 14:46:43 -0000 This is a multi-part message in MIME format. --------------14F45A133C9C2900F1D8E40D Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on January 27th at *14:15 h*, *16:00 h* & *17:00 h* at FU Berlin. *Exceptionally*, there will be a*second Colloquium* at *17:00.* *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, January 27th - 14:15 h* *_Lecture_: Haim Kaplan (Tel Aviv University**)* *_Title_: Privately Learning Thresholds * *_Abstract_:* We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy . Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity. Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well. No previous background on differential privacy will be assumed. _*Coffee & Tea Break*_*:* *Room 134* ** *_Time_: **Monday, ***January* 27th**- 16:00 h s.t.* *_Colloquium_: Gweneth Anne McKinley (MIT, Cambridge, USA**)* *_Title_: Super-logarithmic cliques in dense inhomogeneous random graphs * *_Abstract_:* In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1] ^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G ( n , W ), that can be viewed as a generalization of the Erdös-Rényi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order  log n   for the size of the largest clique in G ( n , W ) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G ( n , W ) will be of order √ n almost surely. We also give a family of examples with clique number of order n ^ c for any c in (0,1), and some conditions under which the clique number of  G ( n , W ) will be o (√ n ) or ω(√ n ). This talk assumes no previous knowledge of graphons. *_Time_: **Monday, ***January* 27th**- 17:00 h s.t.* *_Colloquium_: Michał Włodar**czyk (Universität Eindhoven**)* *_Title_: Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems * *_Abstract_:* Consider the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G \ S belongs to some class H . I will cover the case where graphs in H have treewidth bounded by t , and give a general framework to obtain approximation algorithms basing on two ingredients: 1) approximation algorithms for the k -Subset Separator problem, 2) FPT algorithms parameterized by the solution size. For the vertex deletion setting, this new framework combined with the current best result for k -Subset Vertex Separator, improves approximation ratios for basic problems such as k -Treewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the H Vertex Deletion algorithm and explain the differences between deleting vertices or edges. --------------14F45A133C9C2900F1D8E40D Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on January 27th at 14:15 h, 16:00 h & 17:00 h at FU Berlin.

Exceptionally, there will be a second Colloquium at 17:00.


Location:

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

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

Lecture: Haim Kaplan (Tel Aviv University)

Title: Privately Learning Thresholds

Abstract:

We study the problem of computing a point in the convex hull, and the related problem of computing a separating hyperplane, under the constraint of differential privacy . Intuitively, differential privacy means that our output should be robust to small changes in the input (for example to adding or deleting a point). We study the minimum size of the input needed to achieve such a private computation (sample complexity) and its time complexity. Even in one dimension the problem is non-trivial and we will first focus on this case. Several interesting open problems will be presented as well. No previous background on differential privacy will be assumed.


Coffee & Tea Break:
Room 134

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

Colloquium: Gweneth Anne McKinley (MIT, Cambridge, USA)

Title: Super-logarithmic cliques in dense inhomogeneous random graphs

Abstract:

In the theory of dense graph limits, a graphon is a symmetric measurable function W from [0,1] ^2 to [0,1]. Each graphon gives rise naturally to a random graph distribution, denoted G ( n , W ), that can be viewed as a generalization of the Erdös-Rényi random graph. Recently, Dolezal, Hladky, and Mathe gave an asymptotic formula of order  log n   for the size of the largest clique in G ( n , W ) when W is bounded away from 0 and 1. We show that if W is allowed to approach 1 at a finite number of points, and displays a moderate rate of growth near these points, then the clique number of G ( n , W ) will be of order √ n almost surely. We also give a family of examples with clique number of order n ^ c for any c in (0,1), and some conditions under which the clique number of  G ( n , W ) will be o (√ n ) or ω(√ n ). This talk assumes no previous knowledge of graphons.


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

Colloquium: Michał Włodarczyk (Universität Eindhoven)

Title: Losing treewidth by separating subsets: on approximation of vertex/edge deletion problems

Abstract:

Consider the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G \ S belongs to some class H . I will cover the case where graphs in H have treewidth bounded by t , and give a general framework to obtain approximation algorithms basing on two ingredients: 1) approximation algorithms for the k -Subset Separator problem, 2) FPT algorithms parameterized by the solution size. For the vertex deletion setting, this new framework combined with the current best result for k -Subset Vertex Separator, improves approximation ratios for basic problems such as k -Treewidth Vertex Deletion and Planar F Vertex Deletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. I will talk about what it means for several important graph classes and how the bounded treewidth property is exploited. I will present a sketch of the proof for the H Vertex Deletion algorithm and explain the differences between deleting vertices or edges.

--------------14F45A133C9C2900F1D8E40D-- From i.brunke@inf.fu-berlin.de Tue Jan 28 17:18:34 2020 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 <1iwTZR-003tMZ-Oa>; Tue, 28 Jan 2020 17:18:33 +0100 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 <1iwTZR-0009UJ-Lp>; Tue, 28 Jan 2020 17:18:33 +0100 Received: from ip5f5af303.dynamic.kabel-deutschland.de ([95.90.243.3] helo=[192.168.0.2]) 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 <1iwTZR-003Bkv-CK>; Tue, 28 Jan 2020 17:18:33 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: <85823375-9dcf-a37f-6685-c73d636cb650@inf.fu-berlin.de> Date: Tue, 28 Jan 2020 17:18:33 +0100 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="------------72A0FC8B908A22A5498EF19E" X-Originating-IP: 95.90.243.3 X-ZEDAT-Hint: A X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1580228313-0008DDA6-BBBEFFA4/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000103, 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.3 on Kiribati.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 3rd 2020 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, 28 Jan 2020 16:18:34 -0000 This is a multi-part message in MIME format. --------------72A0FC8B908A22A5498EF19E Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our next Monday Lecture & Colloquium on February 3rd - again at regular times - 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, February 3rd - 14:15 h* *_Lecture_: Sándor Kisfaludi-Bak (MPI Saarbrücken**)* *_Title_: Separators and exact algorithms for geometric intersection graphs * *_Abstract_:* Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH). _*Coffee & Tea Break*_*:* *Room 134* *_Time_: **Monday, ***February* 3rd**- 16:00 h s.t.* *_Colloquium_: Yanitsa Pehova (University of Warwick**)* *_Title_: Characterisation of quasirandom permutations by a pattern sum * *_Abstract_:* We say that a sequence {π__/i/ } of permutations is quasirandom if, for each k>1 and each σ∈/S/__/k/ , the probability that a uniformly chosen /k-set of entries of π/__/i/ induces σ tends to 1//k/! as /i/ tends to infinity. It is known that a much weaker condition already forces π__/i/ to be quasirandom; namely, if the above property holds for all σ∈/S/_4 . We further weaken this condition by exhibiting sets S⊆/S/_4 , such that if randomly chosen four entries of π__/i/ induce an element of /S/ with probability tending to |/S/|/24, then {π__/i/ } is quasirandom. Moreover, we are able to completely characterise the sets /S/ with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec. --------------72A0FC8B908A22A5498EF19E Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our next Monday Lecture & Colloquium on February 3rd - again at regular times - 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, February 3rd - 14:15 h

Lecture: Sándor Kisfaludi-Bak (MPI Saarbrücken)

Title: Separators and exact algorithms for geometric intersection graphs

Abstract:

Given n ball-like objects in some metric space, one can define a geometric intersection graph where the vertices correspond to objects, and edges are added for pairs of objects with a non-empty intersection. A separator of a graph is a small or otherwise "nice" vertex set whose removal disconnects the graph into two roughly equal parts. In this talk, we will see some separator theorems for intersection graphs in Euclidean and hyperbolic space. One can use these separators to design simple divide and conquer algorithms for several classical NP-hard problems. It turns out that well-designed separators often lead to subexponential algorithms with optimal running times (up to constant factors in the exponent) under the Exponential Time Hypothesis (ETH).


Coffee & Tea Break:
Room 134

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

Colloquium: Yanitsa Pehova (University of Warwick)

Title: Characterisation of quasirandom permutations by a pattern sum

Abstract:

We say that a sequence {π_i} of permutations is quasirandom if, for each k>1 and each σ∈S_k, the probability that a uniformly chosen k-set of entries of π_i induces σ tends to 1/k! as i tends to infinity. It is known that a much weaker condition already forces π_i to be quasirandom; namely, if the above property holds for all σ∈S4. We further weaken this condition by exhibiting sets S⊆S4, such that if randomly chosen four entries of π_i induce an element of S with probability tending to |S|/24, then {π_i} is quasirandom. Moreover, we are able to completely characterise the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight. This is joint work with Timothy Chan, Daniel Král', Jon Noel, Maryam Sharifzadeh and Jan Volec.

--------------72A0FC8B908A22A5498EF19E-- From i.brunke@inf.fu-berlin.de Mon Feb 03 17:58:59 2020 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 <1iyf3r-003ZRL-3l>; Mon, 03 Feb 2020 17:58:59 +0100 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 <1iyf3q-002zYi-54>; Mon, 03 Feb 2020 17:58:58 +0100 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1iyf3p-0011wW-VR>; Mon, 03 Feb 2020 17:58:58 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de Message-ID: Date: Mon, 3 Feb 2020 17:58:57 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="------------D1E5514C014F33239D926721" 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::1580749139-0006DFFB-6757D2F9/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.4 on Palau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 10th 2020 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, 03 Feb 2020 16:58:59 -0000 This is a multi-part message in MIME format. --------------D1E5514C014F33239D926721 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit You are cordially invited to our last Monday Lecture & Colloquium for this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin. *Exceptionally*, there will be once again a*second Colloquium* at *17:00. * *The Faculty will meet *after the second Colloquium.* * * * *_Location_**: ** * *Room 005 - Ground Floor* Freie Universität Berlin Takustr. 9 14195 Berlin *_Time_: **Monday, February 10th - 14:15 h* *_Lecture_: Lionel Pournin (Université Paris 13**)* *_Title_: Recent results on the diameter of lattice polytopes * *_Abstract_:* Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa. _*Coffee & Tea Break*_*:* *Room 134* *_Time_: **Monday, **February 10th**- 16:00 h s.t.* *_Colloquium_: José Samper (Max Planck Institute Leipzig**)* *_Title_: Dual matroid polytopes and the independence complex of a matroid * *_Abstract_:* A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton. *_Time_: **Monday, **February 10th**- 17:00 h s.t.* *_Colloquium_: Zslot Ádám Wagner (ETH Zürich**)* *_Title_: Recent developments in the container method * *_Abstract_:* The container algorithm is a recently-developed technique for establishing subtle clustering phenomena of independent sets in graphs and hypergraphs. This method has found numerous applications in extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry. In this talk, I will give a brief overview of this method and survey some recent developments. --------------D1E5514C014F33239D926721 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

You are cordially invited to our last Monday Lecture & Colloquium for this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin.

Exceptionally, there will be once again a second Colloquium at 17:00.

The Faculty will meet after the second Colloquium.


Location:

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

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

Lecture: Lionel Pournin (Université Paris 13)

Title: Recent results on the diameter of lattice polytopes

Abstract:

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.


Coffee & Tea Break:
Room 134

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

Colloquium: José Samper (Max Planck Institute Leipzig)

Title: Dual matroid polytopes and the independence complex of a matroid

Abstract:

A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton.


Time: Monday, February 10th - 17:00 h s.t.

Colloquium: Zslot Ádám Wagner (ETH Zürich)

Title: Recent developments in the container method

Abstract:

The container algorithm is a recently-developed technique for establishing subtle clustering phenomena of independent sets in graphs and hypergraphs. This method has found numerous applications in extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry. In this talk, I will give a brief overview of this method and survey some recent developments.

--------------D1E5514C014F33239D926721-- From rote@inf.fu-berlin.de Thu Feb 06 18:51:53 2020 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 <1izlJh-003Ix3-E2>; Thu, 06 Feb 2020 18:51:53 +0100 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 <1izlJh-0022g8-BV>; Thu, 06 Feb 2020 18:51:53 +0100 Received: from [64.210.41.235] (helo=[192.168.1.214]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1izlJf-0035kA-0B>; Thu, 06 Feb 2020 18:51:53 +0100 References: To: facets-of-complexity@lists.fu-berlin.de Cc: Ita Brunke From: =?UTF-8?Q?G=c3=bcnter_Rote?= X-Forwarded-Message-Id: Message-ID: <0b168244-15b5-3f74-8742-4c40e1833885@inf.fu-berlin.de> Date: Thu, 6 Feb 2020 18:56:50 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.7.2 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-Originating-IP: 64.210.41.235 X-purgate: clean X-purgate-type: clean X-purgate-ID: 151147::1581011513-0005ECF0-6184E939/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.018729, 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.4 on Tokelau.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] Invitation to Monday Lecture & Colloquium - February 10th 2020 / Third 17:00 talk canceled 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 Feb 2020 17:51:53 -0000 You are invited to our last Monday Lecture & Colloquium for this term next Monday at 14:15 h and 16:00 h at FU Berlin. The *second Colloquium* that was planned for *17:00* is CANCELED. Location: Room 005 - Ground Floor Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Time: Monday, February 10th - 14:15 h Lecture: Lionel Pournin (Université Paris 13) Title: Recent results on the diameter of lattice polytopes Abstract: Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa. Coffee & Tea Break: Room 134 Time: 16:00 h s.t. Colloquium: José Samper (Max-Planck-Institut Leipzig) Title: Dual matroid polytopes and the independence complex of a matroid Abstract: A shelling order of a simplicial/polytopal complex is an ordering of the top dimensional faces that allows us to understand various properties of the underlying complex (when it exists). Empirically, some shelling orders are better than others in the sense that they are easier to analyze or come equipped with . This is especially notable for complexes that admit many shelling orders, like polytopes and and matroid independence complexes. We propose a strange connection, linking shelling orders of dual matroid polytopes to shelling orders of independence complexes. In particular, we show that several classical theorems about shellability of matroids have geometric interpretations. We use this to address to propose a new strategy for a 1977 conjecture of R. Stanley about face numbers of independence complexes: that the h-vector is a pure O-sequence. The talk is based on joint work with Alex Heaton. The second colloquium that was planned at 17:00 h (by Zsolt Ádám Wagner from ETH Zürich, about recent developments in the container method) is CANCELED. From i.brunke@inf.fu-berlin.de Mon Feb 10 14:23:28 2020 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 <1j1928-002Nn3-5A>; Mon, 10 Feb 2020 14:23:28 +0100 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 <1j1927-001EWi-5S>; Mon, 10 Feb 2020 14:23:27 +0100 Received: from punkt.imp.fu-berlin.de ([160.45.40.245]) by inpost2.zedat.fu-berlin.de (Exim 4.85) with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (envelope-from ) id <1j1926-002ju2-T8>; Mon, 10 Feb 2020 14:23:27 +0100 From: Ita Brunke To: facets-of-complexity@lists.fu-berlin.de References: Message-ID: Date: Mon, 10 Feb 2020 14:23:26 +0100 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Thunderbird/68.4.1 MIME-Version: 1.0 In-Reply-To: Content-Type: multipart/alternative; boundary="------------452046647D1A24B345B1F3BB" 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::1581341008-00046016-79E042EF/0/0 X-Bogosity: Ham, tests=bogofilter, spamicity=0.003378, 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.4 on Niue.ZEDAT.FU-Berlin.DE X-Spam-Level: Subject: [Facets-of-complexity] CHANGE of program - Monday Lecture & Colloquium - February 10th 2020 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 Feb 2020 13:23:28 -0000 This is a multi-part message in MIME format. --------------452046647D1A24B345B1F3BB Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Due to the storm 'Sabine' the second talk of today can not be given. Today there will only be the Lecture and the coffee after. On 03.02.2020 17:58, Ita Brunke wrote: > > You are cordially invited to our last Monday Lecture & Colloquium for > this term on February 10th at 14:15 h, 16:00 h & 17:00 h at FU Berlin. > > *Exceptionally*, there will be once again a*second Colloquium* at *17:00. > * > > *The Faculty will meet *after the second Colloquium.* > * > > * > * > > *_Location_**: ** > * > > *Room 005 - Ground Floor* > Freie Universität Berlin > Takustr. 9 > 14195 Berlin > > *_Time_: **Monday, February 10th - 14:15 h* > > *_Lecture_: Lionel Pournin (Université Paris 13**)* > > *_Title_: Recent results on the diameter of lattice polytopes > * > > *_Abstract_:* > > Several new results about the largest possible diameter of a lattice > polytope contained in the hypercube [0,k]^d, a quantity related to the > complexity of the simplex algorithm, will be presented. Upper bounds > on this quantity have been known for a couple of decades and have been > improved recently. In this lecture, conjecturally sharp lower bounds > on this quantity will be presented for all d and k, as well as exact > asymptotic estimates when d is fixed and k grows large. These lower > bounds are obtained by computing the largest diameter a lattice > zonotope contained in the hypercube [0,k]^d can have, answering a > question by Günter Rote. This talk is based on joint work with Antoine > Deza and Noriyoshi Sukegawa. > > > _*Coffee & Tea Break*_*:* > *Room 134* > > *_Time_: **Monday, **February 10th**- 16:00 h s.t.* > > *_Colloquium_: José Samper (Max Planck Institute Leipzig**)* > > *_Title_: Dual matroid polytopes and the independence complex of a > matroid > * > > *_Abstract_:* > > A shelling order of a simplicial/polytopal complex is an ordering of > the top dimensional faces that allows us to understand various > properties of the underlying complex (when it exists). Empirically, > some shelling orders are better than others in the sense that they are > easier to analyze or come equipped with . This is especially notable > for complexes that admit many shelling orders, like polytopes and and > matroid independence complexes. We propose a strange connection, > linking shelling orders of dual matroid polytopes to shelling orders > of independence complexes. In particular, we show that several > classical theorems about shellability of matroids have geometric > interpretations. We use this to address to propose a new strategy for > a 1977 conjecture of R. Stanley about face numbers of independence > complexes: that the h-vector is a pure O-sequence. The talk is based > on joint work with Alex Heaton: > --------------452046647D1A24B345B1F3BB Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: 8bit

Due to the storm 'Sabine' the second talk of today can not be given.

Today there will only be the Lecture and the coffee after.


    
On 03.02.2020 17:58, Ita Brunke wrote:

    

    

      
      
You are cordially invited to our last Monday Lecture &
        Colloquium for this term on February 10th at 14:15 h, 16:00 h
        & 17:00 h at FU Berlin. 

      

      
Exceptionally, there will be once again a second
          Colloquium at 17:00. 

        

      
The Faculty will meet after the second Colloquium.

        

      


        

      
 

      
Location: 

        

      Room 005 - Ground Floor

      Freie Universität Berlin

      Takustr. 9

      14195 Berlin 

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

      
Lecture: Lionel Pournin (Université Paris 13)

      
Title: Recent results on the diameter of lattice
          polytopes

        

      Abstract:

      

        
Several new results about the largest possible diameter of a
          lattice polytope contained in the hypercube [0,k]^d, a
          quantity related to the complexity of the simplex algorithm,
          will be presented. Upper bounds on this quantity have been
          known for a couple of decades and have been improved recently.
          In this lecture, conjecturally sharp lower bounds on this
          quantity will be presented for all d and k, as well as exact
          asymptotic estimates when d is fixed and k grows large. These
          lower bounds are obtained by computing the largest diameter a
          lattice zonotope contained in the hypercube [0,k]^d can have,
          answering a question by Günter Rote. This talk is based on
          joint work with Antoine Deza and Noriyoshi Sukegawa.

        

      

      

      Coffee & Tea Break:

      Room 134

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

      
Colloquium: José Samper (Max Planck Institute Leipzig)

      
Title: Dual matroid polytopes and the independence
          complex of a matroid 

        

      Abstract:

      
A shelling order of a simplicial/polytopal complex is an
        ordering of the top dimensional faces that allows us to
        understand various properties of the underlying complex (when it
        exists). Empirically, some shelling orders are better than
        others in the sense that they are easier to analyze or come
        equipped with . This is especially notable for complexes that
        admit many shelling orders, like polytopes and and matroid
        independence complexes. We propose a strange connection, linking
        shelling orders of dual matroid polytopes to shelling orders of
        independence complexes. In particular, we show that several
        classical theorems about shellability of matroids have geometric
        interpretations. We use this to address to propose a new
        strategy for a 1977 conjecture of R. Stanley about face numbers
        of independence complexes: that the h-vector is a pure
        O-sequence. The talk is based on joint work with Alex Heaton: 

    

  


--------------452046647D1A24B345B1F3BB--