Dear all,

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

**You all are cordially invited. **

__Location__**: **

Humboldt-Universität zu Berlin

Rudower Chaussee 25

12489 Berlin

__Time__: **Monday, May 2 - 14:15**

__Lecture__: Tomáš Masarik (Charles University Prague)

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

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

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

an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G−N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices.

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

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

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

__Colloquium__: Jana Novotna (University of Warsaw)

__Title__: Taming Creatures

A graph class is tame if it admits a polynomial bound on the number of minimal separators, and feral if it contains infinitely many graphs with exponential number of minimal separators. The former entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set, and many other problems, when restricted to an input graph from a tame class, by a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015].

In the talk, we show a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame and feral. To obtain the full dichotomy, we confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class C there exists a constant k such that no member of C contains a k-creature or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every graph G from C contains at most p(|V(G)|) minimal separators.

Joint work with Jakub Gajarský, Lars Jafke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza.

Dear all,

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

Invitation link for Zoom meeting:

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

No password is required.

**You all are cordially invited. **

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, May 9 - 14:15**

__Lecture__: Andrew Newman (Carnegie Mellon University,
Pittsburgh)

__Title__: Complexes of nearly maximum diameter

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

**Room 134 - 1st Floor **

** **

__Colloquium__: Marcel Celaya (ETH, Zürich)

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

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

Dear all,

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

Invitation link for Zoom meeting:

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

No password is required.

**You all are cordially invited. **

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, May 16 - 14:15**

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

__Title__: Stack and Queue Layouts of Planar Graphs

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

__Colloquium__: Sandro Roch (Technische Universität
Berlin)

__Title__: Arrangements of Pseudocircles: On Digons and
Triangles

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

(Joint with S.Felsner and M.Scheucher)

Dear all,

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

**You all are cordially invited. **

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, June 13 - 14:15**

__Lecture__: Matthias Beck (San Francisco State
University)

__Title__: Boundary h*-polynomials of rational polytopes

If P is a

`|mP \cap Z^d|`

is a polynomial in the integer
variable m. Equivalently, the generating function \sum_{m \ge 0}
`|mP \cap Z^d|`

t^m is a rational function of the
form h*(t)/(1-t)^{d+1}; we call h*(t) the This is joint work with Esme Bajo (UC Berkeley).

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

__Title__: Tropical Medians by Transportation

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

Dear all,

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

**You all are cordially invited. **

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, June 20 - 14:15**

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

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

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

__Colloquium__: Christian Kipp (Technische Universität
Berlin)

__Title__: Affine Subspace Concentration Conditions for
Polytopes

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

Dear all,

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

**You all are cordially invited. **

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, June 20 - 14:15**

__Lecture__: Wolfgang Mulzer (Freie Universität Berlin)

__Title__: Long Alternating Paths Exist

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

for i /= j.

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

Based on joint work with Pavel Valtr.

__Colloquium__: Michaela Borzechowski (Freie Universität
Berlin)

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

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

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

Dear all,

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

**You all are cordially invited. **

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, July 4 - 14:15**

__Lecture__: Myfanwy Evans (Universität Potsdam)

__Title__: Enumerating triply-periodic tangles

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

__Colloquium__: Marcel Celaya (ETH, Zürich)

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

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

--------------58531C513A1B574B5C266324--