Perfect graphs are important objects in graph theory. The perfect graphs include many important families of graphs, and serve to unify results relating colorings and cliques in those families. One of the most famous and most important results is the strong perfect graph theorem conjectured by Claude Berge and proved by Chudnovsky, Robertson and Thomas. This theorem characterizes perfect graphs. Our interest is to give other characterizations of perfect graphs. In this talk, we construct several lattice polytopes arising from a finite simple graph and characterize when the graph is perfect in terms of the lattice polytopes. This talk is based on joint work with Takayuki Hibi and Hidefumi Ohsugi.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (ground floor)

Oct 22, 2018 | 04:00 PM s.t.

For several graph classes without long induced paths there exists a finite forbidden subgraph characterization for k-colourability. Such a finite set of minimal obstructions allows to provide a “no-certificate" which proves that a graph is not k-colourable. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-colouring P6-free graphs, which solves an open problem posed by Golovach et al. (Here, P6 denotes the induced path on six vertices.) Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand. In this talk we will mainly focus on the algorithmic results by presenting a new algorithm for generating all minimal forbidden subgraphs to k-colourability for given graph classes. This algorithm (combined with new theoretical results) has been successfully applied to fully characterise all forbidden subgraphs for k-colourability for various classes of graphs without long induced paths. (This is joint work with Maria Chudnovsky, Oliver Schaudt and Mingxian Zhong.)

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin room MA 041 (ground floor)

Oct 29, 2018 | 04:00 PM s.t.

There has recently been a lot of interplay between extremal graph theory and the theory of graph limits. After a brief survey of the theory of dense graph limits, we focus on exploring a link between Sidorenko's Conjecture, one of the most prominent open problems in extremal graph theory, and weakly norming graphs, one of the concepts studied in the theory of graph limits. Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko property, i.e., a quasirandom graph minimizes the density of H among all graphs with the same edge density. We are interested in a stronger property, which we call the step Sidorenko property. We relate this property to weakly norming graphs and use our results to construct a bipartite edge-transitive graph that is not weakly norming - this answers a question of Hatami [Israel J. Math. 175 (2010), 125-150]. The talk is based on joint work with Taisa Martins, Peter Pal Pach and Marcin Wrochna.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin room MA 041 (ground floor)

Oct 08, 2018 | 02:00 PM s.t.

For positive integers N and r >= 2, an r-monotone coloring of r-tuples from [N] is a 2-coloring by -1 and +1 that is monotone on the lexicographically ordered sequence of r-tuples of every (r+1)-tuple from [N]. Let ORS(n;r) be the minimum N such that every r-monotone coloring of r tuples from [N] contains n elements with all r-tuples of the same color. For every r >= 3, it is known that ORS(n;r) is bounded from above by a tower function of height r-2 with O(n) on the top. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ORS(n;2)=(n-1)^2+1 and ORS(n;3) = ((2n-4) choose (n-2))+1, respectively. It follows from a result of Eliáš and Matoušek that ORS (n;4) grows as o tower of height 2. We show that ORS(n;r) grows at least as a tower of height r-2 for every r >= 3. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ORS(n;r) and two Ramsey-type problems that have been recently considered by several researchers. We also prove asymptotically tight estimates on the number of r-monotone colorings.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (ground floor)

Jul 16, 2018 | 04:00 PM

We consider random simplicial complexes that are generated from the binomial random hypergraphs by taking the downward-closure. We determine when all cohomology groups with coefficients in F_2 vanish. This is joint work with Oliver Cooley, Nicola Del Giudice, and Philipp Spruessel.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin room MA 041 (ground floor)

Jul 16, 2018 | 02:15 PM

Most computer scientists and discrete mathematicians are familiar with computational complexity due to the famous P = NP conjecture. Some researchers have a more thorough understanding of the classes P, NP, and PSPACE since problems in logic, graph theory, and combinatorial optimization are often classified by their relationship to one of these classes. More recently, these concepts have found a wider audience through their application to puzzles and games. For example, it is known that the number puzzle Sudoku is NP-complete, whereas the box pushing game Sokoban is PSPACE-complete. In this talk we establish the computational complexity of several puzzles and games. We prove that two new paper and pencil puzzles are NP-complete. These puzzles are called Pencils and Sto-Stone, and were created by the Japanese publisher Nikoli that popularized Sudoku. We then prove that several puzzles that have been implemented as video games are PSPACE-complete. These games include a row shifting puzzle called MazezaM, a turnstile puzzle for the Nintendo Game Boy called Kwirk, and a puzzle called Switches that was invented by undergraduate student Jonathan Gabor while he was attending high school. Our reductions use conventional approaches such as Boolean Satisfiability, as well as some less conventional tools including Gray Codes, and the new Constraint Logic model pioneered by Hearn and Demaine in their influential textbook "Games, Puzzles, and Computation". The talk aims to be accessible to a wide audience, and hopes to encourage researchers to seek similar results for problems (or puzzles!) that are close to them. Most of the new results consist of joint work with undergraduate students at Bard College at Simon's Rock.

Jul 09, 2018 | 04:00 PM

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties. In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. In particular, knowing the asymptotic spectrum means knowing the arithmetic complexity of matrix multiplication, a central problem in algebraic complexity theory.I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana.Then I will introduce the analogous object in graph theory: the asymptotic spectrum of graphs. I will explain the relation to Shannon capacity and give an overview of known elements in the asymptotic spectrum of graphs.

Location: Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin Room MA 041 (ground floor)

Jul 09, 2018 | 02:15 PM

Recently, Balletti and I proved that for the h^*-polynomial h_0^*+h_1^*t+... of a lattice polytope, if we assume h_3^*=0, then (h_1^*, h_2^*) satisfies (i) h_2^*=0; or (ii) h_1^* \leq 3h_2^* + 3; or (iii) (h_1^*,h_2^*)=(7,1). These conditions derive from Scott's theorem (1976), who characterized the possible h^*-polynomials of 2-dimensional lattice polytopes, and Scott's theorem is also essentially valid for lattice polytopes with degree at most 2 (Treutlein (2010)). On the other hand, we proved that it also holds under the assumption h_3^*=0. Since the assumption h_3^*=0 is independent of both dimension and degree of polytopes, we call the conditions (i), (ii), (iii) universal. In this talk, towards finding a new universal condition, we investigate the possibility for the polynomial h_0^*+h_1^*t+... to be the h^*-polynomial of some lattice polytope under the assumption that some of h_i^*'s vanish.

Location: Freie Universität Berlin Institut für Mathematik Arnimallee 2 14195 Berlin Seminar Room

Jul 05, 2018 | 02:15 PM

The study of realization spaces of convex polytopes is one of the oldest subjects in Polytope Theory. Most likely, it goes back to Legendre (1794). A lot of progress took place since that time. However, many questions remained open. In general, computing the dimension of the realization space $\mathcal{R}(P)$ of a d-polytope $P$ is hard, even for $d = 4$, as shown by Mnëv (1988) and Richter-Gebert (1996).In this presentation, we will discuss two criteria to determine the dimension of the realization space, and use them to show that $\dim \mathcal{R}(P) = f_1(P) + 6$ for a 3-polytope $P$, and $\dim \mathcal{R}(P) = df_{d-1}(P)$ (resp. $\dim \mathcal{R}(P) = df_0(P)$ ) for a simple (resp. simplicial) $d$-polytope $P$. We will also discuss the realization spaces of some interesting 2-simple 2-simplicial 4-polytopes. Namely, we will consider the realization space of the 24-cell and of a 2s2s polytope with 12 vertices which was found by Miyata (2011), and give a better bound for/determine its dimension.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (ground floor)

Jul 02, 2018 | 04:00 PM

We describe some recent developments in treewidth-based algorithms for knots, which exploit the structure of the underlying 4-valent planar graph. In particular, we show how these led to the first general sub-exponential-time algorithm for the HOMFLY-PT polynomial, and we describe some recent progress on parameterised algorithms for unknot recognition.

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin Room 005 (ground floor)

Jul 02, 2018 | 02:15 PM

A famous and wide-open problem, going back to at least the early 1970's, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute one such set of inequalities when a chromatic polynomial $\chi_G(n) = \chi^*_0 \binom {n+d} d + \chi^*_1 \binom {n+d-1} d + \dots + \chi^*_d \binom n d$ is written in terms of a binomial-coefficient basis. More precisely, we prove that $\chi^*_{d-2}+\chi^*_{d-3}+\dots+\chi^*_{d-j-1} \ \ge \ \chi^*_1+\chi^*_2+\dots+\chi^*_j $, for $1 \le j \le \lfloor \frac{ d }{ 2 } \rfloor - 1$. A similar result holds for flow polynomials enumerating either modular or integral nowhere-zero flows of a graph. Our theorems follow from connections among chromatic, flow, order, and Ehrhart polynomials, and the fact that the latter satisfy a decomposition formula into symmetric polynomials due to Stapledon. (This is joint work with Emerson Le\'on.)

Jun 25, 2018 | 04:00 PM

We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type $B_d$. We discuss connections to the largest diameter of lattice polytopes and to the computational complexity of multicriteria matroid optimization. Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Ben Gurion), Syed Meesum (IMSc Chennai), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).

Jun 25, 2018 | 02:15 PM

In this talk, I will show how techniques from Combinatorial Optimization and Combinatorics can be leveraged to achieve progress on a well-known question in Integer Programming, namely how to solve integer linear programs (ILPs) with bounded subdeterminants. More precisely, I will present an efficient (even strongly polynomial) algorithm to solve ILPs defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2}. This problem class naturally extends the well-known class of ILPs with a totally unimodular (TU) constraint matrix, i.e., where subdeterminants are within {-1,0,1}, and captures some open problems. We employ a variety of techniques common in Combinatorial Optimization, including polyhedral techniques, matroids, and submodular functions. In particular, using a polyhedral result of Veselov and Chirkov, we reduce the problem to a combinatorial one with a so-called parity constraint. We then show how a seminal, purely combinatorial result of Seymour on decomposing TU matrices, which is tightly related to regular matroids and was originally developed in this context, can be used algorithmically to break the problem into smaller ones. Finally, these smaller problems are amenable to combinatorial optimization techniques like parity-constrained submodular minimization. Additionally, I will highlight some of the many open problems in this field and discuss recent related results.

Jun 18, 2018 | 02:15 PM

The cage problem asks for the smallest number c(k, g) of vertices in a k-regular graph of girth g. The (k, g)-graphs which have c(k, g) vertices are known as cages. While cages are known to exist for all integers k > 1 and g > 2, an explicit construction is known only for some small values of k, g and three infinite families for which g is 6, 8 or 12 and k − 1 is a prime power: corresponding to the generalized g/2-gons of order k − 1. To improve the upper bounds on c(k, 6), c(k, 8) and c(k, 12), when k - 1 is not a prime power, one of the main techniques that has been used so far is to construct small (k, g) graphs by picking a prime power q ≥ k and then finding a small k-regular subgraph of the incidence graph of a generalized g/2-gon of order q. In this talk I will present new constructions in generalized quadrangles and hexagons which improve the known upper bound on c(k, 8) when k = p^{2h} and c(k, 12) when k = p^h, where p is an arbitrary prime. Moreover, we will see a spectral lower bound on the number of vertices in a k-regular induced subgraph of an arbitrary regular graph, which in particular will prove the optimality of a known construction in projective planes. (Joint work with John Bamberg and Gordon Royle)

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin room 005 (ground floor)

Jun 11, 2018 | 04:00 PM s.t.

In 1967, F. Arthur Sherk gave a simple proof that the finite metric planes (of Bachmann and Schmidt) are precisely the affine planes of odd order. Moreover, Sherk’s proof holds for a more general class of incidence structures that do not involve the ‘three-reflection theorem’ whatsoever, and thus yields a beautiful characterisation of the finite affine planes of odd order. By relaxing the first of Sherk’s axioms to ‘every pair of points lies on at most one line’, we can study what we call partial Sherk planes. In this talk, we outline our characterisation of these incidence structures as Bruck nets, in the same vein as Sherk’s result, and what it means for connected combinatorial objects such as mutually orthogonal latin squares. (Joint work with Joanna Fawcett and Jesse Lansdown)

Location: Freie Universität Berlin Institut für Informatik Takustr. 9 14195 Berlin room 005 (ground floor)

Jun 11, 2018 | 02:15 PM

From Kalai's classic paper generalizing Cayley's tree-enumeration formula to simplicial complexes, it is known that simplicial complexes on a small number of vertices can have enormous torsion in homology. Moreover, in a random setting one may find instances of this phenomenon such as, for example, a 3-dimensional simplicial complex on 30 vertices with the torsion subgroup of the second homology group having order larger than 10^82. In this talk I will discuss the problem of explicitly constructing such complexes. In particular, I will discuss my work to use the probabilistic method to construct optimally small (up to a constant factor from a known lower bound) simplicial complexes with prescribed torsion in homology. I will also discuss an application of this work to the problem of counting homotopy types of simplicial complexes.

Jun 04, 2018 | 02:15 PM

May 28, 2018 | 04:01 PM s.t.

In the Steiner Tree problem, a set of terminal vertices in an edge-weighted graph needs to be connected in the cheapest possible way. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on the one hand, Steiner Tree is known to be APX-hard, and on the other hand, it is W[2]-hard if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H of G of the minimum cost such that there is a directed path from s to t in H for all arcs st of R. It is known that the problem can be solved in time |V(G)|O(|A(R)|) [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|o(|A(R)|) even if G is planar, unless Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|o(|T|), unless ETH fails. Therefore, there is a significant gap in the complexity with respect to |T| in the exponent. We show that Directed Steiner Network is solvable in time f(|T|) · |V(G)| O(cg · |T|), where cg is a constant depending solely on the genus g of G and f is a computable function.

May 28, 2018 | 04:00 PM s.t.

In the k-Set Packing problem we are given a universe and a family of its subsets, where each of the subsets has size at most k. The goal is to select a maximum number of sets from the family which are pairwise disjoint. It is a well known NP-hard problem, that has been studied from the approximation perspective since the 80's. During the talk I will describe the history of progress on both the weighted and unweighted variants of the problem, with an exposition of methods used to obtain the best known approximation algorithms mostly involving local search based routines.

May 28, 2018 | 02:15 PM