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

Invitation link:

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

No password required.

Zoom - Invitation

__Time__: **Monday, April 26th - 14:15 h**

__Lecture__: Kolja Knauer (Universitat de Barcelona**)**

__Title__: On sensitivity in Cayley graphs

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

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

On the positive side, we consider Cayley graphs of Coxeter
groups, where a lower bound similar to Huang's can be shown. A
generalization of the construction of Chung, F\"uredi, Graham,
and Seymour shows that this bound is tight for products of
Coxeter groups of type $\mathbf{A_n}$, $\mathbf{I_n}(2k+1)$,
most exceptional cases and not far from optimal in general.

Then, we show that also induced subgraphs on more than half the
vertices of Levi graphs of projective planes and of the
Ramanujan graphs of Lubotzky, Phillips, and Sarnak have
unbounded degree. This yields more classes of Cayley graphs with
properties similar to the ones provided by Huang's results.
However, in contrast to Coxeter groups these graphs have no
large subcubes.

Joint with Ignacio Garcia-Marco.

**Break**

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

__Colloquium__: Matthieu Rosenfeld (LIRMM)

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

Monadic second
order logic can be used to express many classical notions of sets
of vertices of a graph as for instance: dominating sets, induced
matchings, perfect codes, independent sets, or irredundant sets.
Bounds on the number of sets of any such family of sets are
interesting from a combinatorial point of view and have
algorithmic applications. Many such bounds on different families
of sets over different classes of graphs are already provided in
the literature. In particular, Rote recently showed that the
number of minimal dominating sets in trees of order n is at most
95^(n/13) and that this bound is asymptotically sharp up to a
multiplicative constant. We build on his work to show that what he
did for minimal dominating sets can be done for any family of sets
definable by a monadic second-order formula.

I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique.

--------------CA9FAD0069990D70BDA834A2--
From itabrunke@zedat.fu-berlin.de Mon Apr 26 19:14:12 2021
Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66])
by list1.zedat.fu-berlin.de (Exim 4.94)
for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2)
tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384
(envelope-from I will first illustrate the general technique with a really simple concrete example ( Dominating independent sets). Then I will explain how to generalize this into a more general technique. I will end my talk by mentioning a few of the results obtained with this technique.

You are cordially invited to our next Monday Lecture on May 3rd.

Exceptionally, there will only be the Lecture.

Exceptionally this Lecture will be at** 16:30.**

Invitation link:

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

No password is required.

Zoom - Invitation

__Time__: **Monday, May 3rd - 16:30 h !!**

__Lecture__: Chris Eur (Stanford University)

__Title__: Tautological classes of matroids

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

--------------B36D404131B85FED86BDA878-- From itabrunke@zedat.fu-berlin.de Wed May 05 19:12:57 2021 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

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

Invitation link:

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

No password is required.

Zoom - Invitation

__Time__: **Monday, May 10th - 14:15 h**

__Lecture__: Max Klimm (Technische Universität Berlin**)**

__Title__: tba

tba

**Break**

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

__Colloquium__: Aniket Shah (Ohio State University)

__Title__: A q-analogue of Brion's identity

--------------49B4EDFC7554157E59AC272D-- From itabrunke@zedat.fu-berlin.de Thu May 06 15:28:05 2021 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

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

Invitation link:

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

No password required.

Zoom - Invitation

__Time__: **Monday, May 10th - 14:15 h**

__Lecture__: Max Klimm (Technische Universität Berlin**)**

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

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

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

__Colloquium__: Aniket Shah (Ohio State University)

__Title__: A q-analogue of Brion's identity

--------------D50532DAD8442909C2F28B0D-- From rote@zedat.fu-berlin.de Mon May 10 16:32:03 2021 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

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

Due to technical difficulties we will have the Colloquium's talk
from Monday 10th again this week, on Monday 17th.

There possibly will also be a *random* Lecture on Monday
17th.

Invitation link:

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

No password required.

Zoom - Invitation

__Time__: **Monday, May 17th - 14:15 h ***(po**tentially
takling place)*

__Lecture__: So far unknown speaker (**Universität
Berlin****)**

__Title__: Random.

*Random content.*

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

__Colloquium__: Aniket Shah (Ohio State University)

__Title__: A q-analogue of Brion's identity

--------------FFD6A71E67E1975990C0F90D-- From itabrunke@zedat.fu-berlin.de Tue Jun 01 21:15:57 2021 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

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

Invitation link:

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

No password is required.

Zoom - Invitation

__Time__: **Monday, June 7th - 14:15 h**

__Lecture__: Michael Joswig (Technische Universität Berlin**)**

__Title__: Tropical bisectors and Voronoi diagrams

We consider norms in real vector spaces where the unit ball is
an arbitrary convex polytope, possibly centrally symmetric. In
contrast with the Euclidean norm, the topological shape of
bisectors may be complicated. Our first main result is a
formula for the Betti numbers of bisectors of three points in
sufficiently general position.

Specializing our results to the tropical polyhedral norm then
yields structural results and algorithms for tropical Voronoi
diagrams. The tropical distance function plays a key role in
current applications of tropical geometry.

Joint work with Francisco Criado and Francisco Santos.

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

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

No password is required.

Zoom - Invitation

__Time__: **Monday, June 14th - 16:30
h !!!**

__Lecture__: Alex Postnikov (MIT**)**

__Title__: Polypositroids

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

__Time__: **Monday, ****June 14th**** - 14:45
h !!!**

__Colloquium__: Davide Lofano (Technische Universität
Berlin)

__Title__: Random Simple-Homotopy Theory

A standard task in topology is to simplify a given finite presentation of a topological space. Bistellar flips allow to search for vertex-minimal triangulations of surfaces or higher-dimensional manifolds, and elementary collapses are often used to reduce a simplicial complex in size and potentially in dimension. Simple-homotopy theory, as introduced by Whitehead in 1939, generalizes both concepts.

The procedure also allows to find substructures in complexes, e.g., surfaces in higher-dimensional manifolds or subcomplexes with torsion in lens spaces.

(Joint work with Bruno Benedetti, Crystal Lai, and Frank Lutz.)

--------------4C86F57C96E768FB5C4371B3-- From itabrunke@zedat.fu-berlin.de Tue Jun 15 18:14:19 2021 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

Time is back to normal.

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

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

No password is required.

Zoom - Invitation

__Time__: **Monday, June 21st - 14:15 h**

__Lecture__: Alexey Pokrovskiy (University College London)

__Title__: Linear size Ramsey numbers of hypergraphs

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

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

__Colloquium__: Patrick Morris (Freie Universität Berlin)

__Title__: Triangle factors in pseudorandom graphs

An (n, d, λ)-graph is an n vertex, d-regular graph with second eigenvalue in absolute value λ. When λ is small compared to d, such graphs have pseudo-random properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n, d, λ)-graph with d = Θ(n^2/3) and λ = Θ(d^2/n). This construction is optimal as having λ = o(d^2/n) guarantees the existence of a triangle in a (n, d, λ)-graph. Krivelevich, Sudakov and Szab ́o (2004) conjectured that if n ∈ 3N and λ = o(d^2/n) then an (n, d, λ)-graph G in fact contains a triangle factor: vertex disjoint triangles covering the whole vertex set. In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab ́o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph G contains every graph on n vertices with maximum degree at most 2.

Time is back to normal.

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

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

No password is required.

Zoom - Invitation

__Time__: **Monday, June 28th - 14:15 h**

__Lecture__: Xavier Allamigeon (Inria and Ecole
Polytechnique)

__Title__: Formalizing the theory of polyhedra in a proof
assistant

In this talk, I will present the project Coq-Polyhedra that
aims at formalizing the theory of polyhedra as well as
polyhedral computations in the proof assistant Coq.

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

Joint work with Quentin Canu, Ricardo D. Katz and Pierre-Yves
Strub.

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

__Colloquium__: Gorav Jindal (Technische Universität
Berlin)

__Title__: Arithmetic Circuit Complexity of Division and
Truncation

Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)).

The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute. We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy.

This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/ . --------------339FA4DB2735BDFFB682D62A-- From itabrunke@zedat.fu-berlin.de Tue Jun 29 17:02:57 2021 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.94) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLS1.2) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (envelope-from

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

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

No password is required.

Zoom - Invitation

__Time__: **Monday, July 5th - 14:15 h**

__Lecture__: Papa Sissokho (Illinois State University)

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

Let a_{1},...,a_{n} and b_{1},...,b_{m}
be fixed positive integers, and let S denote the set of all
nonnegative integer solutions of the equation x_{1}a_{1}+...+x_{n}a_{n}=y_{1}b_{1}+...+y_{m}b_{m}.
A solution (x_{1},...,x_{n},y_{1},...,y_{m})
in S is called *minimal* if it cannot be expressed as
the sum of two nonzero solutions in S. For each pair (i,j),
with 1 ≤ i ≤ n and 1 ≤ j ≤ m, the solution whose only nonzero
coordinates are x_{i} = b_{j} and y_{j}
= a_{i} is called a *generator*. We show that
every minimal solution is a convex combination of the generators
and the zero-solution. This proves a conjecture of
Henk-Weismantel and, independently, Hosten-Sturmfels.

Break!

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

__Colloquium__: Ansgar Freyer (Technische Universität
Berlin)

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

A key step in the proof is a technique from convex geometry known as Blascke's shaking procedure by which the problem can be reduced to anti-blocking bodies, i.e., convex bodies that are "located in the corner of the positive orthant".

As a corollary of
our result, we will obtain an upper bound on the number of lattice
points in K in terms of the successive minima, which is equivalent
to Minkowski's Second Theorem, giving a partial answer to a
conjecture by Betke et al. from 1993.

This is a joint work with Eduardo Lucas Marín.

--------------7560A4D987F8378D0A650454--
This is a joint work with Eduardo Lucas Marín.