Seminars

02.12.2021 16:45
Krzysztof Michalik
Combinatorial Optimization
Improved lower bound for the list chromatic number of graphs with no Kt minor

This paper begins with recounting known limits regarding Hadwiger's conjecture and related problems including list Hadwiger's conjecture, stating that there does exist constant c, such that Kt minor free graph G has list coloring number not exceeding ct. After introduction, we are presented with a proof that such constant has to be at least equal 2, contrary to previous results, where c was bounded by 4/3 and conjectured to be equal to 3/2.

  1. Krzysztof Michalik. slides. (2021).
02.12.2021 16:00
Krzysztof Ziobro
Combinatorial Optimization
Polynomials over structured grids

Paper discusses properties of multivariate polynomials over finite grids, focaausing on he grids that are in some way "structured". To capture the degree to which a grid is structured, author introduces a notion of nullity, which can give us a numerical measure of structure. It is noted that for more structured grids we can obtain stronger versions of general theorems. This leads to the main results of the paper: the Structured Combinatorial Nullstellensatz and the Complete Coefficient Theorem.

  1. Bogdan Nica. Polynomials over structured grids. arXiv 2110.05616. (2021).
  2. Krzysztof Ziobro. slides. (2021).
08.12.2021 12:15
Katarzyna Król
Computer science foundations
0-1 Laws for Maps by Edward A. Bender, Kevin J. Compton,and L. Bruce Richmond

A class of fnite structures has a 0-1 law with respect to a logic if every property expressible in the logic has a probability approaching a limit of 0 or 1 as the structure size grows. To formulate 0-1 laws for maps (i.e., embeddings of graphs in a surface), it is necessary to represent maps as logical structures. Three such representations are given,
the most general being the full cross representation based on Tutte's theory of combinatorial maps. The main result says that if a class of maps has two properties, richness and large representativity, then the corresponding class of full cross representations has a 0-1 law with respect to first-order logic. As a corollary the following classes of maps
on a surface of fixed type have a first-order 0-1 law: all maps, smooth maps, 2-connected maps, 3-connected maps, triangular maps, 2-connected triangular maps, and 3-connected triangular maps

 

08.12.2021 16:15
István Tomon
ETH Zürich
Theoretical computer science
Ramsey properties of semilinear graphs

A graph G is semilinear of complexity t if the vertices of G are points in some real space, and the edges of G are determined by the sign-patterns of t linear functions. Many natural geometric graph families are semilinear of bounded complexity, e.g. intersection graphs of boxes, shift graphs, interval overlap graphs. There is a long line of research studying the exceptional Ramsey and coloring properties of such geometric graphs; I will show that many of these results can be traced back to their semilinear nature.

09.12.2021 16:00
Krzysztof Potępa, Marcin Serwin
Combinatorial Optimization
Fully Dynamic Graph Orientation

...

  1. Krzysztof Potępa, Marcin Serwin. slides. (2021).
15.12.2021 16:15
Lars Rohwedder
EPFL
Theoretical computer science
A (2+ϵ)-approximation algorithm for preemptive weighted flow time on a single machine

In a recent breakthrough in scheduling, Batra, Garg, and Kumar gave the first constant approximation algorithm for minimizing the sum of weighted flow times. Wiese and I [STOC'21] managed to improve this large unspecified constant to (2+ϵ). I will give a very graphic presentation of the algorithmic techniques behind this.

22.12.2021 16:15
Grzegorz Gutowski
Theoretical computer science
On a problem of Steinhaus

In this talk, inspired by a "17-points" problem of Steinhaus (Problems 6 and 7 from his book "Sto zadań"), we discuss infinite sequences of real numbers in [0,1).
For a function f:N--->N, we say that a sequence X is f-piercing if for every finite m, the first f(m) elements of X contain at least one element in every interval [i/m,(i+1)/m) for i from 0 up to m-1. There is a nice construction of (m/ln2)-piercing sequence due to de Bruijn and Erdős which satisfies even stronger piercing properties. We are able to show that this is best possible, as there are no (am+o(m))-piercing sequences for a<1/ln2. Our results allow for some new tight linear bounds for similar concepts defined for finite sequences.

The talk is based on the manuscript: https://arxiv.org/abs/2111.01887

05.01.2022 16:15
Jakub Kozik
Theoretical computer science
TBA - J.Kozik
12.01.2022 12:15
Filip Synowiec
Computer science foundations
On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface by Albert Atserias, Stephan Kreutzer and Marc Noy

We show that for no surface except for the plane does monadic second-order logic (MSO) have a zero-one-law – and not even a convergence law – on the class of (connected) graphs embeddable on the surface. In addition we show that every rational in [0,1] is the limiting probability of some MSO formula. This strongly refutes a conjecture by Heinig et al. (2014) who proved a convergence law for planar graphs, and a zero-one law for connected planar graphs, and also identified the so-called gaps of [0,1]: the subintervals that are not limiting probabilities of any MSO formula. The proof relies on a combination of methods from structural graph theory, especially large face-width embeddings of graphs on surfaces, analytic combinatorics, and finite model theory, and several parts of the proof may be of independent interest. In particular, we identify precisely the properties that make the zero-one law work on planar graphs but fail for every other surface.

 

13.01.2022 16:00
Demian Banakh
Combinatorial Optimization
A relative of Hadwigers conjecture

...

  1. Demian Banakh. slides. (2021).
13.01.2022 16:45
Jacek Salata
Combinatorial Optimization
Choosability of K5-minor-free graphs

...

  1. Kacek Salata. slides. (2021).
19.01.2022 12:15
Daniel Barczyk
Computer science foundations
Narrow Proofs May Be Maximally Long by Albert Atserias and Massimo Lauria

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size $n^{\Omega (w)}$. This shows that the simple counting argument that any formula refutable in width w must have a proof in size  $n^{O (w)}$ is essentially tight. Moreover, our lower bound generalizes to polynomial calculus resolution (PCR) and Sherali-Adams, implying that the corresponding size upper bounds in terms of degree and rank are tight as well. The lower bound does not extend all the way to Lasserre, however, since we show that there the formulas we study have proofs of constant rank and size polynomial in both n and w.

 

20.01.2022 16:00
Szymon Salabura
Combinatorial Optimization
The Hats game. On max degree and diameter

...

  1. Szymon Salabura. slides. (2021).
26.01.2022 12:15
Jakub Fedak
Computer science foundations
Exact enumeration of satisfiable 2-SAT formulae by Sergey Dovgal, Elie de Panafeu and Vlady Ravelomanana

We obtain exact expressions counting the satisfiable 2-SAT formulae and describe the structure of associated implication digraphs. Our approach is based on generating function manipulations. To reject the combinatorial specificities of the implication digraphs, we introduce a new kind of generating function, the Implication generating function, inspired by the Graphic generating function used in digraph enumeration. Using the underlying recurrences, we make accurate numerical predictions of the phase transition curve of the 2-SAT problem inside the critical window. We expect these exact formulae to be amenable to rigorous asymptotic analysis using complex analytic tools, leading to a more detailed picture of the 2-SAT phase transition in the future.

 

26.01.2022 16:15
Sławomir Lasota
University of Warsaw
Theoretical computer science
TBA - Lasota

Poprzednie referaty

01.12.2021 16:15
Barnaby Martin
Durham University
Theoretical computer science
QCSP monsters and the future of the Chen Conjecture

We elaborate the complexity of the Quantified Constraint Satisfaction Problem, QCSP(A), where A is a finite idempotent algebra. Such a problem is either in NP or is co-NP-hard, and the borderline is given precisely according to whether A enjoys the polynomially-generated powers (PGP) property. This completes the complexity classification problem for QCSPs modulo that co-NP-hard cases might have complexity rising up to Pspace-complete. Our result requires infinite languages, but in this realm represents the proof of a slightly weaker form of a conjecture for QCSP complexity made by Hubie Chen in 2012. The result relies heavily on the algebraic dichotomy between PGP and exponentially-generated powers (EGP), proved by Dmitriy Zhuk in 2015, married carefully to previous work of Chen. Finally, we discuss some recent work with Zhuk in which the aforementioned Chen Conjecture is actually shown to be false. Indeed, the complexity landscape for QCSP(B), where B is a finite constraint language, is much richer than was previously thought.

01.12.2021 12:15
Ignacy Buczek
Computer science foundations
Definability on a Random 3-CNF Formula by Albert Atserias

We consider the question of certifying unsatisfiability of random 3-CNF formulas. At which densities can we hope for a simple sufficient condition for unsatisfiability that holds almost surely? We study this question from the point of view of definability theory. The main result is that first-order logic cannot express any sufficient condition that holds almost surely on random 3-CNF formulas with $n^{2-\alpha}$ clauses, for any irrational positive number \alpha. In contrast, it can when the number of clauses is $n^{2+\alpha}$, for any positive \alpha. As an intermediate step, our proof exploits the planted distribution for 3-CNF formulas in a new technical way. Moreover, the proof requires us to extend the methods of Shelah and Spencer for proving the zero-one law for sparse random graphs to arbitrary relational languages.

 

25.11.2021 16:45
Artur Salawa
Combinatorial Optimization
The Open Problems Project

Paper records open problems in computational geometry and related fields. For every problem, the authors provide a statement, origin, current status, partial results and related problems. My presentation focuses on a few chosen problems explained in a friendly manner.

  1. Erik D. Demaine Joseph, S. B. Mitchell, and Joseph O’Rourke. The Open Problems Project. manuscript. (2020).
  2. Artur Salawa. The Open Problems Project. slides. (2021).
25.11.2021 16:00
Grzegorz Wawrzesta
Combinatorial Optimization
Density conditions for panchromatic colourings of hypergraphs

A hypergraph is defined as a pair H = (V, E), where V is a set of vertices and E is a set of subsets of V - these subsets of vertices are called (hyper)edges. Graphs can be then seen as a concretization where all edges are sets of size 2. This can be shortly ascribed to the hypergraph as being 2-uniform. T-uniformity is a useful assumption for deriving its properties but sometimes one would wish for more general results. This approach is one of a few that are considered by the authors of the following paper which focuses on boundaries we can put on some characteristic properties of hypergraphs relating to their colorability and list-colorability. During the meeting, the basic concepts of hypergraphs and their colorability will be introduced and then the results of the paper will be interpreted alongside the presentation of the theorems and lemmas (and also an exemplar proof of one of them or two) which are used in the paper to attain the results.

  1. Alexandr V. Kostochka, Douglas R. Woodall. Density Conditions for Panchromatic Colourings of Hypergraphs. Combinatorica 21, 515-541. (2001).
  2. Grzegorz Wawrzesta. Density conditions for panchromatic colourings of hypergraphs - introduction and overview. slides. (2021).
25.11.2021 14:15
Miłosz Januszewski, Szymon Salabura
Algorytmika
A Fine-Grained Perspective on Approximating Subset Sum and Partition

W problemie Subset Sum, mając dany zbiór dodatnich liczb X oraz cel t, pytamy czy istnieje dowolny podzbiór sumujący się do dokładnie t. Należy on do klasy problemów NP-zupełnych, zatem naturalne jest badanie jego algorytmów aproksymacyjnych - takich, które szukają podzbioru sumującego się do co najmniej 1-ε wyniku optymalnego. Aktualnie najlepszy znany algorytm robi to w czasie O(min{n/ε,n+1/ε2 log(1/ε)}). W szczególności nie jest znany żaden algorytm rozwiązujący ten problem w O((n+1/ε)c) dla dowolnego c<2.

Autorzy w pracy pokazują równoważność tego problemu do Min-Plus-Convolution przeprowadzając redukcje w obie strony. Dzięki temu uzyskują algorytm aproksymacyjny dla Subset Sum o poprawionym czasie działania oraz udowadniają, że Subset Sum ma algorytm aproksymacyjny w czasie O((n+1/ε)c) dla c<2 wtedy i tylko wtedy, gdy Min-Plus-Convolution może być rozwiązany w O(nc') dla c'<2. Druga część równoważności jest jednak sprzeczna z hipotezą trudności tego problemu.

Dodatkowo, dla specjalnego wariantu Subset Sum zwanego Partition, autorzy stosują powyższą redukcję otrzymując algorytm aproksymacyjny działający w czasie O(n+1/ε3/2). Jest to pierwszy deterministyczny algorytm z podkwadratową złożonością.

24.11.2021 16:15
Jan Derbisz
Theoretical computer science
Circular-arc graphs and the Helly property

Circular-arc graphs, defined as the intersection graphs of arcs of a fixed circle, are probably one of the simplest classes of intersection graphs, which does not satisfy the Helly property in general (i.e. there are circular-arc graphs in which some cliques can be represented by arcs whose common intersection is empty). In particular, some cliques of a circular-arc G graph may satisfy the Helly property in some but not all circular-arc representations of G.

In the Helly Clique Problem, for a given circular-arc graph G and some of its cliques C1,...,Ck (not necessarily maximal in G) one needs to decide whether there exists a circular-arc representation of G in which all the cliques C1,...,Ck satisfy the Helly property. We know that the Helly Clique Problem is NP-complete and, under the ETH, it can not be solved in time 2o(k)poly(n), where n is the number of vertices of G (Ağaoğlu et al.).

In the talk we will consider the Helly Clique Problem in the context of parameterized complexity, where the natural parameter is the number of cliques given in the input. We will show that the Helly Clique Problem:
- admits an algorithm with running time 2O(k log k)poly(n) (and hence it belongs to FPT),
- admits a polynomial kernel of size O(k6).

Moreover, we will discuss the relation of the Helly Clique Problem with the recognition problems of so-called H-graphs; in particular, in the context of those graphs H for which the recognition problem remains open.

This is joint work with T. Krawczyk. The talk also includes joint work with D. Ağaoğlu, O. Cagrici, T. Hartmann, P. Hliněný, J. Kratochvíl, T. Krawczyk, and P. Zeman.

24.11.2021 12:15
Michał Woźny
Computer science foundations
Dance of the Starlings by Henk Barendregt, Jorg Endrullis, Jan Willem Klop, and Johannes Waldmann

In this birdwatching paper our binoculars are focused upon a particular bird from Smullyan's enchanted forest of combinatory birds, to wit the Starling. In the feathers of lambda-calculus this bird has the plumage \abc:ac(bc). This term is usually named S, reminiscent of its inventor Schonfinkel and also the  combinatory ornithologist Smullyan. The combinator S is important for a variety of reasons. First, it is part of the S, K -basis for Combinatory Logic (CL). Second, there are several interesting questions and observations around S, mostly referring to termination and word problems. Our paper collects known facts, but poses in addition several new questions. For some of these we provide solutions, but several tough open questions remain.

 

18.11.2021 16:45
Maciej Nemś
Combinatorial Optimization
Fair Correlation Clustering

In this paper authors propose approximation for Correlation Clustering problem with additional constaint of fairness. In a fair version of correlation clustering vertices have also colors and in the end in each cluster there should be "some" number of vertices of each color. What "some" means is dependent on variant of this constraint. Authors first reduce a problem of fair clustering correlation to a problem they call Fairlet Decomposition and then show approximation algorithm for this problem. In the end they describe some experiments they have done to prove Fair Correlation Clustering a viable version of Correlation Clustering.

  1. Sara Ahmadian, Alessandro Epasto, Ravi Kumar, Mohammad Mahdian. Fair Correlation Clustering, arXiv 2002.02274. (2021).
  2. Maciej Nemś. Fair Correlation Clustering. slides. (2021).
18.11.2021 16:00
Karolina Gontarek
Combinatorial Optimization
Growth properties of power-free languages

Paper surveys common part of two formal language issues. Issue of repetition free words and languages and issue of growth functions for words and languages. Paper gives an overview of current knowledge and search about an intersection of those two areas. It classifies power-free languages with regard to their growth rate. It also describes methods of esimating complexity of power-free languages paying attention to amount of computer resources needed by special method. Finally, it presents future directions of research in this area.

  1. Karolina Gontarek. Growth properties of power-free languages. slides. (2021).
18.11.2021 14:15
Aleksander Katan, Roch Wójtowicz
Algorytmika
Filling crosswords is very hard

Autorzy analizują problem wypełniania krzyżówek, który już był rozważany na przykład przez Garey’a i Johnsona w ich książce „Computers and Intractability: A Guide to the Theory of NP-Completeness”. W problemie tym dostajemy m słów i n poziomych lub pionowych slotów (rubryk) oraz jesteśmy proszeni o wypełnienie ich tak, by przecięcia slotów się zgadzały. Autorzy próbują wskazać źródło trudności tej łamigłówki przyglądając się strukturze grafu przecięć slotów. Skupiają się na przypadku, gdy struktura tego grafu przypomina drzewo. Niestety, jeżeli przyjmiemy, że słowa nie mogą być używane wielokrotnie, okazuje się, że problem pozostaje NP-trudny nawet pod bardzo surowymi restrykcjami, jak na przykład, że graf przecięć jest sumą grafów typu star i alfabet ma rozmiar
2, lub że jest matchingiem (krzyżówka składa się z samych rozłącznych krzyży) z alfabetem rozmiaru 3. Zapytanie staje się prostsze, gdy pozwolimy na powtarzanie słów, gdyż autorom udaje się skonstruować algorytm działający w czasie mtw, gdzie tw oznacza treewitdh (szerokość drzewiastą) grafu. Jednak nawet wtedy nie można algorytmu poprawić, by otrzymać FPT. Co więcej, pod założeniem ETH, problem nie może być rozwiązany w czasie mo(k), gdzie k to liczba poziomych slotów instancji problemu.
Zmotywowani tymi przykrymi wynikami, autorzy rozważają bardziej ograniczony przypadek, gdzie parametryzujemy się liczbą slotów wszystkich, a nie tylko poziomych. Problem staje się FPT (o ile alfabet jest stałego rozmiaru), ale złożoność jest wykładnicza od n2. Wykazują, że pod założeniem ETH, nie istnieje algorytm działający w czasie 2o(n^2), nawet dla dwuznakowego alfabetu. Pod koniec pracy rozważana jest wersja optymalizacyjna, w której staramy się wypełnić jak najwięcej pól. Łatwo jest wtedy uzyskać 1⁄2-aproksymację, nawet dla przypadku ważonego, wystarczy po prostu brać pod uwagę tylko pionowe albo tylko poziome sloty. Ten algorytm jest prawdopodobnie optymalny, gdyż istnienie lepszej aproksymacji działającej w wielomianowym czasie przeczyłoby Unique Games Conjecture. Ostatnie dwa wyniki są prawdziwe niezależnie, czy rozpatrujemy przypadek z powtarzaniem słów czy bez.

17.11.2021 16:15
Nicolas Bousquet
CNRS, Lyon
Theoretical computer science
Local certification of/on sparse graph classes

Local certification consists in assigning labels to the nodes of a graph in order to certify that some given property is satisfied, in such a way that the labels can be checked locally. In this talk, our goal is to certify that a graph G belongs to a given graph class. Such certifications exist for many sparse graph classes such as trees, planar graphs and graphs embedded on surfaces with labels of logarithmic size. It is open if such a certificate exist for any H-minor free graph class. We present some generic tools which allow us to certify the H-minor-free graphs (with logarithmic labels) for each small enough H.

More generally, we consider classes defined by any MSO formula (i.e. the MSO-model checking problem), and show a local version of the well-known Courcelle theorem: in bounded treedepth graphs, logarithmic certificates can be obtained for any MSO formula. We will also discuss many open problems related to  local certification of/on sparse graph classes.

Joint works with Laurent Feuilloley and Théo Pierron

17.11.2021 12:15
Łukasz Selwa
Computer science foundations
An Inverse of the Evaluation Functional for Typed λ-calculus by U. Berger and Η. Schwichtenberg
In any model of typed lambda-calculus containing some basic arithmetic, a functional p ->e (procedure —> expression) will be defined which inverts the evaluation functional for typed lambda-terms. Combined with the evaluation functional, p->e yields an efficient normalization algorithm. The method is extended to lambda-calculi with constants and is used to normalize (the lambda-representations of) natural deduction proofs of (higher order) arithmetic. A consequence of theoretical interest is a strong completeness theorem for \beta \eta-reduction, generalizing results of Friedman and Statman. If two lambda-terms have the same value in some model containing
representations of the primitive recursive functions (of level 1) then they are provably equal in the \beta \eta-calculus.
17.11.2021 12:15
Łukasz Selwa

An Inverse of the Evaluation Functional for Typed λ-calculus by U. Berger and Η. Schwichtenberg
In any model of typed lambda-calculus containing some basic arithmetic, a functional p ->e (procedure —> expression) will be defined which inverts the evaluation functional for typed lambda-terms. Combined with the evaluation functional, p->e yields an efficient normalization algorithm. The method is extended to lambda-calculi with constants and is used to normalize (the lambda-representations of) natural deduction proofs of (higher order) arithmetic. A consequence of theoretical interest is a strong completeness theorem for \beta \eta-reduction, generalizing results of Friedman and Statman. If two lambda-terms have the same value in some model containing
representations of the primitive recursive functions (of level 1) then they are provably equal in the \beta \eta-calculus.
10.11.2021 16:15
Zdeněk Dvořák
Charles University
Theoretical computer science
On asymptotic dimension of planar and geometric graphs

A graph class C has asymptotic dimension at most d if for every r, the r-th distance power of any graph from C can be colored by d+1 colors so that every monchromatic connected subgraph has bounded weak diameter. In a recent breakthrough result, Bonamy, Bousquet, Esperet, Groenland, Liu, Pirot, and Scott proved that all proper minor-closed classes have asymptotic dimension at most two.  We investigate some questions motivated by this result for planar graphs and geometric intersection graphs.

Joint work with Sergey Norin

04.11.2021 16:45
Roch Wójtowicz
Combinatorial Optimization
Problems and results on 3-chromatic hypergraphs and some related questions

Authors in this work aim to establish various bounds and constraints on hypergraphs which are k-chromatic. Hypergraph is a graph where an edge don’t have to link exactly two vertices. Hypergraph is called simple, when none two of his edges has more then one common point, and is called clique when each two of his edges has at least one common point. Hyper graph is r-uniform when each of its edges contains exactly r points. Chromatic number is a smallest number k such that you can color points of the graph using k colors in the way that no edge is monochromatic. Main part of the work involves around the impact that being clique or simple has on 3-chromatic hypergraph structure. The main reason why those two things are connected is following trivial observation: If a hypergraph has chromatic number > 3 then it has two edges with exactly one common point.

  1. Paul Erdős, László Lovász. Problems and results on 3-chromatic Hypergraphs and some related questions. Coll Math Soc J Bolyai. 10. (1974).
  2. Roch Wójtowicz. Problems and results on 3-chromatic hypergraphs and some related questions. slides. (2021).
04.11.2021 16:00
Grzegorz Gawryał
Combinatorial Optimization
Defective and clustered choosability of sparse graphs

This paper explores almost proper graph colorings and list colorings - we allow the coloring to be improper, but we impose restrictions on the maximum number of neighbours of any vertex with the same color as the vertex itself (defect) or the maximum allowed size of a monochromatic connected graph component (clustering). The paper provides new bounds on coloring and list coloring number for sparse graphs, i.e. having bounded maximum average degree, taken over all subgraphs, or limited maximum degree. More precisely, the two main results of this paper are the new bounds on defective choosability and clustered choosability of graphs with bounded maximum average degree, being the best known results for graphs with unbounded maximum degree, but bounded maximum average degree, like k-stack and k-queue graphs.

  1. Kevin Hendrey, David R. Wood. Defective and clustered choosability of sparse graphs. Combinatorics, Probability and Computing, 28, 791-810. (2019).
  2. Grzegorz Gawryał. Defective and clustered choosability of sparse graphs. slides. (2021).
04.11.2021 14:15
Mateusz Pach, Michał Wronka
Algorytmika
Determining 4-edge-connected components in linear time
Prezentujemy pierwszy deterministyczny algorytm obliczający 4-spójne krawędziowo składowe w czasie liniowym. Najpierw pokazujemy algorytm znajdujący wszystkie 3-cięcia krawędziowe w danym grafie 3-spójnym krawędziowo i korzystając z jego wyniku budujemy 4-spójne składowe oryginalnego grafu.
03.11.2021 16:15
Torsten Mütze
University of Warwick & Charles University
Theoretical computer science
Efficient generation of elimination trees and Hamilton paths on graph associahedra
An elimination tree for a connected graph G is a rooted tree on the vertices of G obtained by choosing a root x and recursing on the connected components of G−x to produce the subtrees of x. Elimination trees appear in many guises in computer science and discrete mathematics, and they are closely related to centered colorings and tree-depth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent Hartung-Hoang-Mütze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph G can be generated by tree rotations using a simple greedy algorithm (see www.combos.org/elim). This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs. Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations. As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations. Our algorithm for generating all elimination trees for a chordal graph G can be implemented in time O(m+n) per generated elimination tree, where m and n are the number of edges and vertices of G, respectively. If G is a tree, we improve this to a loopless algorithm running in time O(1) per generated elimination tree. We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of G, rather than just Hamilton path, if the graph G is chordal and 2-connected. Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of G if and only if G is chordal.
 
This is joint work with Jean Cardinal (ULB) and Arturo Merino (TU Berlin)
03.11.2021 12:15
Juliusz Wajgelt
Computer science foundations
On Repetitive Right Application of B-Terms by Mirai Ikebuchi and Keisuke Nakano
B-terms are built from the B combinator alone defined by B \f.\g.\x.f (g x), which is well known as a function composition operator. This paper investigates an interesting property of B-terms, that is, whether repetitive right applications of a B-term cycles or not. We discuss conditions for B-terms to have and not to have the property through a sound and complete equational axiomatization. Specifically, we give examples of B-terms which have the property and show that there are infinitely many B-terms which do not have the property. Also, we introduce a canonical representation of B-terms that is useful to detect cycles, or equivalently, to prove the property, with an efficient algorithm.
28.10.2021 14:15
Piotr Kaliciak, Kamil Galewski
Algorytmika
Turing Completeness and Sid Meier’s Civilization
W pracy zostało wykazane, że trzy gry strategiczne z serii Sid Meier's Civilization: Sid Meier’s Civilization: Beyond Earth, Sid Meier’s Civilization V, i Sid Meier’s Civilization VI, są zupełne w sensie Turinga. Dla każdej gry została pokazana, oparta na jej mechanikach, konstrukcja uniwersalnej maszyny Turinga. Istnienie takich maszyn oznacza, że pod pewnymi założeniami gry te są nierozstrzygalne. Praca pokazuje działanie przykładowej maszyny - Zajętego Bobra złożonego z trzech stanów, zaimplementowanej w jednej z gier.
27.10.2021 12:15
Jan Kościsz
Computer science foundations
FIXED POINT COMBINATORS AS FIXED POINTS OF HIGHER-ORDER FIXED POINT GENERATORS by ANDREW POLONSKY
Corrado Bohm once observed that if Y is any fixed point combinator (fpc), then Y (\yx:x(yx)) is again fpc. He thus discovered the first \fpc generating scheme" a generic way to build new fpcs from old. Continuing this idea, define an fpc generator to be any sequence of terms G_1, ..., G_n such that
                               Y is fpc then Y G_1...G_n is fpc:
In this contribution, we take first steps in studying the structure of (weak) fpc generators. We isolate several robust classes of such generators, by examining their elementary properties like injectivity and (weak) constancy. We provide sufficient conditions for existence of fixed points of a given generator (G_1, ..., G_n): an fpc Y such that Y = Y G_1 ... G_n. We conjecture that weak constancy is a necessary condition for existence of such (higher-order) fixed points. This statement generalizes Statman's conjecture on non-existence of "double fpcs": fixed points of the generator (G) = (\yx:x(yx)) discovered by Bohm. Finally, we define and make a few observations about the monoid of (weak) fpc generators. This enables us to formulate new conjectures about their structure.
26.10.2021 11:00
David Wood
Monash University
Theoretical computer science
Universality in minor-closed graph classes*

Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain an infinite complete graph as a minor. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite n-vertex subgraph has O(n1/2) treewidth (which implies the Lipton-Tarjan separator theorem). More generally, for every fixed positive integer t we construct a countable graph that contains every countable Kt-minor-free graph and has the above key properties.

Joint work with Tony Huynh, Bojan Mohar, Robert Šámal and Carsten Thomassen

exceptionally: Tuesday at 11:00

21.10.2021 14:15
Daniel Bobrzyk, Mateusz Golonka
Algorytmika
Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks
20.10.2021 16:15
Bartłomiej Kielak
Theoretical computer science
Inducibility of small oriented graphs

For a fixed graph H, let i(H, n) be the maximum induced density of H in any graph on n vertices. The limit i(H, n), as n goes to infinity, always exists and is called inducibility of H. Fox, Huang, and Lee proved that for almost all graphs H (think of large 'typical' graphs), inducibility of H can be obtained as the limit of induced density of H in its iterated blowups. Apart from that, inducibility is well understood only for narrow classes of graphs; in particular, it is still not determined for H being a path on 4 vertices.

Definition of inducibility can be easily adapted to different settings of combinatorial structures. In this talk, I will focus on the setting of oriented graphs and discuss the inducibility of oriented graphs on at most 4 vertices.
 
Joint work with Łukasz Bożyk and Andrzej Grzesik
14.10.2021 16:00
Jędrzej Hodor
Combinatorial Optimization
Reconfiguring Independent Sets on Interval Graphs

In the reconfiguration problem, we are given a set of objects and rules of how one object can be reconfigured into another one. The main questions to be asked are if it is possible to reconfigure two given objects into each other (Reachability Problem) or how long is the shortest possible reconfiguration sequence. We focus on reconfiguring independent sets in a given graph. Two independent sets are reconfiguration-adjacent if their symmetric difference consists exactly of two vertices connected by an edge. It is known that for some graph classes the Reachability Problem can be solved in polynomial time. I briefly survey the topic and show that the problem is computationally hard for incomparability graphs. Moreover, I discuss the reconfiguration paths length problem in general and in more detail in the class of interval graphs.

  1. Marcin Briański, Stefan Felsner, Jędrzej Hodor, Piotr Micek. Reconfiguring Independent Sets on Interval Graphs. arXiv, 2105.03402, (2021).
  2. Marcin Brianski, Stefan Felsner, Jedrzej Hodor and Piotr Micek. Reconfiguring Independent Sets On Interval Graphs. slides. (2021).
13.10.2021 16:15
Daniel Kráľ
Masaryk University in Brno
Theoretical computer science
Uniform Turán density of hypergraphs

In the early 1980s, Erdős and Sós, initiated the study of the classical Turán problem with a uniformity condition: the uniform Turán density of a hypergraph H is the infimum over all d for which any sufficiently large hypergraph with the property that all its linear-size subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K43, the complete 4-vertex 3-uniform hypergraph, and K43-, the hypergraph K43 with an edge removed. The latter question was solved only recently in [Israel J. Math. 211 (2016), 349–366] and [J. Eur. Math. Soc. 97 (2018), 77–97], while the former still remains open for almost 40 years.

Prior to our work, the hypergraph K43- was the only 3-uniform hypergraph with non-zero uniform Turán density determined exactly. During the talk, we will present the following two results:

  • We construct a family of 3-uniform hypergraphs with uniform Turán density equal to 1/27. This answers a question of Reiher, Rödl and Schacht [J. London Math. Soc. 97 (2018), 77–97] on the existence of such hypergraphs, stemming from their result that the uniform Turán density of every 3-uniform hypergraph is either 0 or at least 1/27.
  • We show that the uniform Turán density of the tight 3-uniform cycle of length k5 is equal to 4/27 if k is not divisible by three, and equal to zero otherwise. The case k=5 resolves a problem suggested by Reiher [European J. Combin. 88 (2020), 103117].

The talk is based on results obtained jointly with (subsets of) Matija Bucić, Jacob W. Cooper, Frederik Garbe, Ander Lamaison, Samuel Mohr and David Munhá Correia.

07.10.2021 16:15
Bartłomiej Bosek
Combinatorial Optimization
Open problem session

Several open problems related to 1-2-3 Conjecture are presented.

06.10.2021 16:15
Virginia Vassilevska Williams
MIT
Theoretical computer science
A refined laser method and (slightly) faster matrix multiplication

Matrix multiplication is one of the most basic linear algebraic operations outside elementary arithmetic. The study of matrix multiplication algorithms is very well motivated from practice, as the applications are plentiful. Matrix multiplication is also of great mathematical interest. Since Strassen's discovery in 1969 that n-by-n matrices can be multiplied asymptotically much faster than the brute-force O(n3) time algorithm, many fascinating techniques have been developed, incorporating ideas from computer science, combinatorics, and algebraic geometry.

The fastest algorithms over the last three decades have used Strassen's "laser method" and its optimization by Coppersmith and Winograd. The method has remained unchanged; the algorithms have differed in what the method was applied to. In recent work, joint with Josh Alman, we improve the method so that applying it to the same objects that the old method was applied to immediately yields faster algorithms. Using this new method, we obtain the theoretically fastest algorithm for matrix multiplication to date, with running time O(n2.37286).

This talk will give an overview of the main techniques and will also outline our recent improvement of the laser method.

17.06.2021 17:00
Szymon Salabura
Combinatorial Optimization
The Fixing Block Method in Combinatorics on Words

A word is repetitive if it contains two consecutive identical blocks. A sequence is non-repetitive up to mod r if each of its mod k (1⩽k⩽r) subsequences is non-repetitive. Let L be a language of non-repetitive (up to mod r) words. In this seminar, we are going to take a look at fixing blocks - a special kind of suffixes preventing words of L to have an extension in L. Using the fixing blocks method we are going to show some interesting properties of such languages. We also outline a method of attack for more complex problems.

  1. James D. Currie, Cameron W. Pierce. The Fixing Block Method in Combinatorics on Words. Combinatorica 23, 571-584, (2003).
  2. Szymon Salabura. The Fixing Block Method in Combinatorics on Words. slides. (2021).

(the seminar will only be online)

17.06.2021 16:15
Wojciech Węgrzynek
Combinatorial Optimization
Non-repetetive words: ages and essences

The age of an infinite word will be the set of all its finite subwords, it's essence will be the set of all finite subwords occurring infinitely many times. The language L{121,323} is the language of all square-free infinite words, such that they don’t have 121 or 323 as subwords. It turns out if we consider the equivalence relations on L{121,323} in respect to the ages and the essences we will get an uncountable cardinality of equivalence classes and 1 equivalence class respectively.

  1. James D. Currie. Non-repetitive words: Ages and essences. Combinatorica 16, 19-40, (1996).
  2. Wojciech Węgrzynek. Non-repetitive words: ages and essences. slides. (2021).

(the seminar will only be online)

16.06.2021 16:15
Krzysztof Turowski
Theoretical computer science
Degree Distribution of Dynamic Graphs Generated by a Duplication-Divergence Models
We analyze the structure of dynamic graphs generated from duplication models in which a new vertex selects an existing vertex and copies some of its neighbors and then we add some random divergence. We analyze various graph parameters like mean degree, number of open triangles, number of triangles, number of vertices of degree k or maximum degree in a graph generated from such models. We provide asymptotic analysis of expected values and tail behavior of these parameters. We also point to further extensions of this approach towards computing symmetries in these graphs and algorithms for graph compression.
 
Joint work with Philippe Jacquet, Alan Frieze and Wojciech Szpankowski
10.06.2021 17:00
Bartosz Wodziński
Combinatorial Optimization
Zarankiewicz's Problem and some related results

In 1951, Kazimierz Zarankiewicz posed a problem asking for the largest possible number of edges in a bipartite graph that has a given number of vertices (n) and has no complete bipartite subgraphs of a given size. Although solved for some specific cases, it still remains open in general. It led to some interesting results in extremal graph theory, such as Kővári–Sós–Turán theorem which gives an upper bound for this problem. During the seminar, I will discuss several problems related to forbidding subgraphs, from easy up to unsolved ones. I will also show their connection with some geometric problems such as creating a maximum number of unit distances between n points on a plane.

  1. Matoušek J. Incidence Problems. In: Matoušek J. (eds) Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol 212. Springer, New York, NY. (2002).
  2. Yufei Zhao. Graph Theory and Additive Combinatorics. course. MIT. (2020).
  3. Bartosz Wodziński. Zarankiewicz's Problem and some related results. slides. (2021).

(the seminar will only be online)

10.06.2021 16:15
Michał Zwonek
Combinatorial Optimization
Polyomino Tilings

A polyomino is a subset of R2 formed by a strongly connected union of axis-aligned unit squares centered at locations on the square lattice Z2. Let T = {T1,T2,...} be an infinite set of finite simply connected closed sets of R2. Provided the elements of T have pairwise disjoint interiors and cover the Euclidean plane, then T is a tiling and the elements of T are called tiles. Provided every T∈ T is congruent to a common shape T, then T is monohedral, T is the prototile of T, and the elements of T are called copies of T. In this case, T is said to have a tiling. We will go through some of the open problems related to polyomino tilings.

  1. Michał Zwonek. Polyomino Tilings. slides. (2021).

(the seminar will only be online)

09.06.2021 16:15
Paweł Rzążewski
Warsaw University of Technology
Theoretical computer science
Treewidth of graphs with forbidden induced subgraphs

The notion of treewidth and tree decompositions plays a central role in the study of graphs with forbidden minors. Besides structural characterizations, the property of having boundedtreewidth, or a tree decomposision with certain "nice" properties, can be used algorithmically. However, until very recently, there were very few results that allowed to analyze the treewidth of graphs that exclude certain induced subgraphs. Indeed, a large clique has large treewidth, but is H-free for any graph H which is not a clique. It turns out that some intresting relations between the two worlds can be found if we additionally put some restrictions on vertex degrees - either just by bounding the maximum degree, or, in some cases, by bounding the degeneracy.

During the talk we will discuss some results of this flavor. In particular, we will show that

  • graphs of bounded degeneracy that exclude all cycles of length at least t have bounded treewidth;
  • graphs of bounded degree that exclude a fixed subdivision of the claw admit a certain type of an "*induced* grid/wall theorem": they either contain the line graph of a big subdivided wall as an *induced subgraph*, or have bounded treewidth.

 

Based on the joint work with Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and with Abrishami, Chudnovsky, and Dibek.

08.06.2021 09:00
Bartosz Walczak
Theoretical computer science
Coloring polygon visibility graphs and their generalizations

The visibility graph of a polygon P is formed by the pairs of vertices u and v of P such that the segment uv is disjoint from the exterior of P. We show that the class of polygon visibility graphs is χ-bounded, thus answering a question by Kára, Pór, and Wood from 2005. Specifically, we prove the bound χ≤3⋅4ω−1. We obtain the same bound for generalizations of polygon visibility graphs in which the polygon is replaced by a curve and straight-line segments are replaced by segments in a pseudo-line arrangement. The proof is carried through in the setting of ordered graphs. In particular, we show χ-boundedness of several classes of ordered graphs with excluded ordered substructures.

Joint work with James Davies, Tomasz Krawczyk, and Rose McCarty.

This is a part of Round the World Relay in Combinatorics organized by Oxford University.

Here is the full schedule: http://people.maths.ox.ac.uk/scott/relay.htm

And the zoom link for the whole event:

https://us02web.zoom.us/j/87593953555?pwd=UWl4eTVsanpEUHJDWFo3SWpNNWtxdz09

meeting id: 875 9395 3555
password: relay

02.06.2021 16:15
Marthe Bonamy
Université de Bordeaux
Theoretical computer science
Graph recolouring

Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to real-life scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.

27.05.2021 17:00
Jan Mełech
Combinatorial Optimization
Rödl Nibble

For positive integers r<k<n let m(n,k,r) be the maximal size of a family F of k-element subsets of [n] such that no r vertices lie in more than one A in F. The Erdös-Hanani conjecture states that as n grows to infinity m(n,k,r) tends to (n choose r)/(k choose r). Firstly, we will see a sketch of the proof of this conjecture proposed by Vojtech Rödll. Then we will talk about how this is connected with packing in hypergraph and discuss the idea of an algorithm called Rödl nibble that achieves asymptotically optimal packing k-uniform hypergraphs.

  1. Joonleng Tan. Rödl Nibble. manuscript. (2012).
  2. Jan Mełech. Rödl Nibble. slides. (2021).

(the seminar will only be online)

27.05.2021 16:15
Krzysztof Pióro
Combinatorial Optimization
Decomposing planar graphs into graphs with degree restrictions

Given a graph G, its (d,h)-decomposition is a partition of a set of edges of this graph into a d-degenerate graph and a graph with maximum degree at most h. We will study (d,h)-decomposability of planar graphs and consider the problem of finding minimum hd such that every planar graph is (d,hd)-decomposable. Since every planar graph is 5-degenerate, we will consider only the case of d less than 5.

  1. Krzysztof Pióro. Decomposing planar graphs into graphs with degree restrictions. slides. (2021).

(the seminar will only be online)

26.05.2021
Piotr Kawałek
Theoretical computer science
Constant depth circuits

We will overview the state-of-the-art results and techniques used in proofs of the lower bounds for constant depth circuits. We focus mostly on classes AC[0], ACC[0] and CC[0]. The most important challenges and some open problems are to be discussed.

20.05.2021 17:00
Maciej Nemś
Combinatorial Optimization
Ant Colony Optimization

Ant Colony Optimization algorithms are part of swarm intelligence approach to solving problems. They are inspired by behavior of ants. After finding a desired destination ants leave pheromones on the way back to the colony. This way all ants can detect the scent and decide to go in the direction suggested by pheromone trail. ACO is based on this concept and involves multi-agent computation. Communication between agents is done by changing the stimuli for all agents, to make a certain action. This is similar to ants leaving pheromones. Presentation will include basic concept of Ant Colony Optimization and an example of solving a well known problem using it. I will also present a formalization of ACO into a metaheuristic for combinatorial optimization problems. Presentation will end with talk about current state of ACO, its limitation and possible future.

  1. M. Dorigo, M. Birattari, and T. Stutzle. Ant colony optimization. IEEE Computational Intelligence Magazine1(4), 28-39. (2006).
  2. M. Dorigo and T. Stützle. Ant Colony Optimization: Overview and Recent Advances. In: Gendreau M., Potvin JY. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 146. Springer, Boston, MA. (2010).
  3. Maciej Nemś. Ant Colony Optimization. slides. (2021).
  4. ANTS International Conference on Swarm Intelligence.

(the seminar will only be online)

20.05.2021 16:15
Wojciech Buczek
Combinatorial Optimization
Woodall’s conjecture

Woodall’s conjecture tells us, that any directed cut with at least k edges has at least k disjoint dijoins. Set of edges D is a dijoin if and only if the digraph (V, E ∪ D-1) is strongly connected. We will say about the linear programming formulation of this problem, equivalent and related problems to it, and some partial results by Shrijver, Lee and Wakabayashi, and Meszaros. We will also show counterexamples to a generalized version of the conjecture.

  1. Paulo Feofiloff. Woodall’s conjecture on Packing Dijoins: a survey. manuscript. (2005)
  2. Wojciech Buczek. Woodall’s conjecture. slides. (2021).

(the seminar will only be online)

19.05.2021 16:15
Paweł Idziak
Theoretical computer science
Modular circuits satisfiability of intermediate complexity

In our paper [LICS'18] a generalization of Boolean circuits to arbitrary finite algebras was introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However nilpotent but not supernilpotent algebras have not been put on any side of this borderline.

This paper provides a broad class of examples, lying in this grey area, and show that, under the Exponential Time Hypothesis and Strong Exponential Size Hypothesis (saying that Boolean circuits need exponentially many modular counting gates to produce Boolean conjunctions of any arity), satisfiability over these algebras have intermediate complexity. We also sketch how these examples could be used as paradigms to fill the nilpotent versus supernilpotent gap in general.

Our examples are striking in view of the natural strong connections between circuits satisfiability and Constraint Satisfaction Problem for which the dichotomy was shown by Bulatov and Zhuk.

Joint work with Piotr Kawałek and Jacek Krzaczkowski

13.05.2021 16:15
Vladyslav Rachek, Ruslan Yevdokymov
Combinatorial Optimization
An Introduction to the Discharging Method via Graph Coloring

The discharging method is a technique that can be used to show that some global properties of a graph imply the existence of local structures. Then, we can sometimes show, that such structures imply that the graph has another global property. The discharging method is thus a "connector" between global properties of a graph (via local properties, e.g. having subgraphs or minors). In the first part of the presentation, we talk about the structure and coloring of sparse and plane graphs. Typical statements will sound like "If there is some global degree bound, then the chromatic number is somehow bounded"

  1. D. Cranston, D. West. A Guide to the Discharging Method. manuscript. (2013).
  2. Vladyslav Rachek, Ruslan Yevdokymov. An Introduction to the Discharging Method via Graph Coloring. slides. (2021).

(the seminar will only be online)

12.05.2021 16:15
Grzegorz Gutowski
Theoretical computer science
Filling blanks in matrices to avoid singularity: progress report

Given an n-by-n generator matrix with entries being subsets of a fixed field we generate the set of all matrices with entries coming from the corresponding entries in the generator matrix. Such a set of matrices is strongly singular if each member is a singular matrix. In this talk I will survey natural generalizations and connections to other problems. In particular, I will describe algorithm by Geelen for  maximum rank matrix completion problem.

06.05.2021 17:00
Marcin Serwin
Combinatorial Optimization
Aanderaa-Karp-Rosenberg conjecture

The conjecture deals with queries on graph. More concretely given property of a graph (such as connectedness or non-emptiness) we may ask whether it is possible to recognize a graph with this property without querying all of its edges. It turns out that for many properties it is indeed not possible to do so in a deterministic manner for all graphs. The Aanderaa–Karp–Rosenberg conjecture states that any non-trivial monotone graph property cannot be determined by a deterministic algorithm with less than n(n-1)/2 queries. Such graph properties are called evasive, thus this conjecture is sometimes called evasiveness conjecture.

  1. Marcin Serwin. Aanderaa-Karp-Rosenberg conjecture. slides. (2021).

(the seminar will only be online)

06.05.2021 16:15
Krzysztof Potępa
Combinatorial Optimization
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds

In the edge orientation problem, one is asked to orient edges of a given graph such that the out-degrees of vertices are bounded by some function. In the fully dynamic variant, we want to process arbitrary edge insertions and deletions in an online fashion. We will show an algorithm for graphs with bounded arboricity that achieves logarithmic out-degree bound and supports updates in O(log n) worst-case time.

  1. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. ICALP 2014, LNCS 8573, 532-543, (2014). (arXiv:1312.1382)
  2. Krzysztof Potępa. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. slides. (2021).

(the seminar will only be online)

05.05.2021 16:15
Louis Esperet
Université Grenoble Alpes
Theoretical computer science
Universal graphs and labelling schemes

Given a graph class C, a graph G is universal for C if it "contains" all the graphs from C. As there are several notions of containment, there are several notions of universal graphs. In this talk I'll mention two versions:

  • induced-universal graphs: here G contains all the graphs of C as induced subgraphs
  • isometric-universal graphs: here G contains isometric copies of all the graphs from C (isometric means that the distances are preserved in the embedding)

Note that an isometric copy is an induced copy, so the second notion is stronger. These notions are closely related to the notion of labelling schemes in graphs. The goal is to assign labels to the vertices of each graph G from C such that upon reading the labels of any two vertices u and v, we know some properties of u and v in G (whether they are adjacent, or their distance, or whether u is reachable from v if G is a digraph). It turns out that minimizing the size of the labels is equivalent to constructing small universal graphs, at least in the case of induced-universal graphs. For isometric-universal graphs some additional work needs to be done.

I'll survey some recent progress in this area. In particular I'll show how to construct induced-universal graphs of almost optimal size for any hereditary class, using the regularity lemma. In particular this implies almost optimal reachabilty labelling schemes in digraphs and comparability labelling schemes in posets, and the construction of an almost optimal universal poset for the class of all n-element posets (of size 2n/4+o(n)). I will also show how to construct isometric-universal graphs of size 3n+o(n) for the class of all n-vertex graphs, answering a question of Peter Winkler.

Based on joint work with Marthe Bonamy, Cyril Gavoille, Carla Groenland, and Alex Scott.

29.04.2021 16:15
Mateusz Kaczmarek
Combinatorial Optimization
On triangles in Kr-minor free graphs

There is a close connection between minors of the graph and a lower bound on such number k that each edge (or vertex) belongs to at least k triangles. One of the most interesting classes of minors is the class of complete graphs Kr. In the paper 'On triangles in Kr-minor free graphs', Boris Albar and Daniel Gonçalves take a closer look at this class of graphs. Based on their work I will present some interesting results regarding this connection and show how it correlates with Hadwiger's conjecture.

  1. Boris Albar Daniel Gonçalves. On triangles in Kr‐minor free graphs. Journal of Graph Theory, 88(1), 154-173, (2017). (arXiv:1304.5468)
  2. Mateusz Kaczmarek. On triangles and minors. slides. (2021).

(the seminar will only be online)

28.04.2021 16:15
Daniel Kráľ
Masaryk University in Brno
Theoretical computer science
Quasirandom combinatorial structures

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.

We will discuss quasirandom properties of other combinatorial structures, tournaments, permutations and Latin squares in particular, and present several recent results obtained using analytic tools of the theory of combinatorial limits.

The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Adam Kabela, Ander Lamaison, Taísa Martins, Roberto Parente, Samuel Mohr, Jonathan A. Noel, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Fiona Skerman and Jan Volec.

22.04.2021 16:15
Bartłomiej Jachowicz
Combinatorial Optimization
Acyclic coloring of graphs with fixed maximum degree

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted as a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. Known problem in this area is to find an upper bound for an acyclic chromatic number for graphs with a fixed maximum degree. One of the first papers on this topic is Hocquard's article "Graphs with maximum degree 6 are acyclically 11-colorable". The proofing technique from his work has been used in many later papers that show similar bounds for graphs with fixed maximum grades.

  1. Hervé Hocquard. Graphs with maximum degree 6 are acyclically 11-colorable. Information Processing Letters, 111(15), 748-753, (2011). (manuscript)
  2. Bartłomiej Jachowicz. Acyclic coloring of graphs with fixed maximum degree. slides. (2021).

(the seminar will only be online)

21.04.2021 16:15
Paweł Gawrychowski
University of Wrocław
Theoretical computer science
Fully Dynamic Longest Increasing Subsequence

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under

(i) inserting an element, and

(ii) deleting an element of an array.

In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/ϵ)O(1/ϵ))-approximation of LIS under both operations with worst-case update time ~O(nϵ), for any constant ϵ>0. We exponentially improve on their result by designing an algorithm that maintains a (1+ϵ)-approximation of LIS under both operations with worst-case update time ~O(ϵ−5). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.

While this essentially settles the complexity of the approximate version of the problem, the exact version seems more elusive. The only known sublinear solution was given very recently by Kociumaka and Seddighin [STOC 2021] and takes ~O(n2/3) time per update. We show polynomial conditional lower bounds for two natural extensions of this problem: weighted LIS and LIS in any subarray.

Joint work with Wojciech Janczewski

 

15.04.2021 16:15
Piotr Mikołajczyk
Combinatorial Optimization
Thomassen's choosability argument revisited

The Hadwiger Conjecture states that if a graph G does not contain a clique on t vertices as a minor, then G is (t-1)-colorable. For low values of t (<7) it was already shown that this claim is actually true. Currently, the best-known upper bound on the chromatic number of Kt-minor-free graphs is O(ct*sqrt(log(t))) and the proof follows from a degeneracy argument. Unfortunately, this approach cannot be exploited further. However, by revisiting Thomassen's reasoning from '94 we can try to prepare the ground for a new way of attacking the Hadwiger Conjecture based on graph choosability. For that, we will take a look at a new proof of a theorem that every K5-minor-free graph is 5-choosable.

  1. David R. Wood, Svante Linusson. Thomassen's Choosability Argument Revisited. SIAM Journal on Discrete Mathematics, 24(4), 1632-1637, (2010). (arXiv:1005.5194)
  2. Piotr Mikołajczyk. Thomassen's choosability argument revisited. slides. (2021).

(the seminar will only be online)

14.04.2021 16:15
Michał Seweryn
Theoretical computer science
Dimension of posets with k-outerplanar cover graphs

In 2015, Felsner, Trotter, and Wiechert showed that posets with outerplanar cover graphs have bounded dimension. We generalise this result to posets with k-outerplanar cover graphs. Namely, we show that posets with k-outerplanar cover graph have dimension O(k3). As a consequence, we show that every poset with a planar cover graph and height h has dimension O(h3). This improves the previously best known bound of O(h6) by Kozik, Micek and Trotter.

Joint work with Maximilian Gorsky

https://arxiv.org/abs/2103.15920

08.04.2021 16:15
Jędrzej Kula
Combinatorial Optimization
Combinatorial Nullstellensatz

Proposed by Noga Alon in 1999 an algebraic technique inspired by Hilbert’s Nullstellensatz. Despite being an observation about roots of a polynomial in n variables, it finds a usage in numerous fields - from Combinatorial Number Theory to Graph Theory. The theory itself is simple, but can be used in ingenious ways - appearing even as almost a necessary step to solve a problem during the 2007 IMO competition. During this time slot I will present a theorem and prove it with as I believe a simpler proof constructed by Mateusz Michałek, that is using a basic induction idea over a polynomial degree. Finally we will again follow the original N. Alon paper to see applications of a theorem in the graph coloring problems and some more.

  1. Noga Alon. Combinatorial Nullstellensatz. Combinatorics Probability and Computing, 8 (1999), 7-29. (manuscript)
  2. Mateusz Michałek. A short proof of Combinatorial Nullstellensatz. American Mathematical Monthly, 117 (2010), 821-823. (arXiv:0904.4573)
  3. Tomasz Kochanek. Combinatorial Nullstellensatz. (2012) (pl). manuscript.
  4. Jędrzej Kula. Combinatorial Nullstellensatz. slides. (2021).

(the seminar will only be online)

07.04.2021 16:15
Mikołaj Bojańczyk
University of Warsaw
Theoretical computer science
Recognisable languages over monads
Algebraic language theory originated in the study of regular languages via semigroups, instead of automata. The advantage of the semigroup approach is a richer structural theory, e.g. Green’s theory or the Factorisation Forest Theorem. (In contrast, the structural analysis of automata seldom goes beyond such elementary notions as “cycle” or “connected component”.) In this talk, I will discuss a more abstract view on semigroups, as Eilenberg-Moore algebras over the monad of finite words (aka the list monad in programming languages). Using this abstract view, by changing the monad, one can get the appropriate notion of “semigroup” for objects beyond finite words, e.g. trees or graphs. Sometimes, even theorems can be proved using this abstract view.
 
This talk is based on the draft monograph 
31.03.2021 16:15
Andrzej Dorobisz
Theoretical computer science
Local Computation Algorithms for Coloring of Uniform Hypergraphs

We present a progress on local computation algorithms for two coloring of k-uniform hypergraphs. We focus on instances that (for a parameter α) satisfy strengthened assumption of Local Lemma of the form 21-αk(Δ+1)e<1, where Δ is the bound on the maximum edge degree of the hypergraph. We discuss how previous works on the subject can be used to obtain an algorithm that works in polylogarithmic time per query for α up to about 0.139. Then, we present a procedure that, within similar bounds on running time, solves wider range of instances by allowing α to be at most about 0.227.

Joint work with Jakub Kozik

25.03.2021 16:15
Bartłomiej Bosek
Combinatorial Optimization
Local Dimension of Planar Poset

In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter.

Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter. Local Dimension is Unbounded for Planar Posets. arXiv, pages 1-12, 2017.

(the seminar will only be online)

24.03.2021 16:15
Marcin Pilipczuk
University of Warsaw
Theoretical computer science
Recent progress in understanding H-free graphs for H being a path or a subdivided claw

Graph classes excluding a path or a subdivided claw as an induced subgraph are so far mysterious: on one hand, beside some corner cases, they do not seem to have any good structural description, but on the other hand, a number of combinatorial problems - including Maximum Independent Set (MIS) - lack an NP-hardness proof in these graph classes, indicating a possible hidden structure that can be used algorithmically. Furthermore, graphs excluding a fixed path as an induced subgraph were one of the earliest examples of a chi-bounded graph class, with an elegant proof technique dubbed the Gyarfas' path argument. In the recent years the progress accelerated, leading to, among other results, (a) a quasi-polynomial-time algorithm for MIS in graphs excluding a fixed path as an induced subgraph, (b) a QPTAS for MIS in graphs excluding a subdivided claw as an induced subgraph, (c) the proof of the Erdos-Hajnal property in graph classes excluding a fixed forest and its complement. In the talk, I will survey these results, showing the role of the Gyarfas' path argument in most (all?) of them, and outline research directions for the future.

18.03.2021 16:15
Bartłomiej Bosek
Combinatorial Optimization
The 1/3 - 2/3 conjecture

A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field.

(the seminar will only be online)

17.03.2021 16:15
Stefan Felsner
Technische Universität Berlin
Theoretical computer science
Combinatorics of Pseudocircle Arrangements

In this talk we survey results for pseudocircle arrangements. Along the way we present several open problems. Among others we plan to touch the following topics:

 * The taxonomy of classes of pseudocircle arrangements.
 * The facial structure with emphasis on triangles and digons.
 * Circularizability.
 * Coloring problems for pseudocircle arrangements.

The talk includes work of Grünbaum, Snoeyink, Pinchasi, Scheucher, myself, and others.

11.03.2021 16:15
Jędrzej Hodor
Combinatorial Optimization
Polynomial Treedepth Bounds in Linear Colorings

Centered graph coloring is graph coloring, such that for every connected subgraph, this subgraph contains a vertex with a unique color (we call such a vertex center). Linear coloring is coloring, such that every path has a center. We denote by cen(G) and lin(G) respectively, a minimal number of colors needed. It is obvious that lin(G) ≤ cen(G). What about the other direction? Authors of the paper show that cen f(lin), where f is a polynomial of the degree 190. Moreover, the authors conjecture that cen 2 lin for every graph. What is interesting, we don't know how to prove such abound even for trees. Luckily, for some classes of graphs, we can do better than 190-poly. During the seminar, I will present results for simple classes of graphs and I will try to sketch the general proof. In particular, I will present a cubic bound for interval graphs. The proof in the paper is incorrect, but I and dr Micek managed to fix it. Finally, I will present our new result for graphs with bounded path width.

  1. Jeremy Kun, Michael P. O’Brien, Marcin Pilipczuk, and Blair D. Sullivan. Polynomial Treedepth Bounds in Linear Colorings. Algorithmica. volume 83, pages 361–386. 2021.
  2. Jędrzej Hodor. Polynomial Treedepth Bounds in Linear Colorings. slides. 2021.

(the seminar will only be online)

10.03.2021 16:15
Bartosz Walczak
Theoretical computer science
Approximating Pathwidth for Graphs of Small Treewidth

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t log t). This is the first algorithm to achieve an f(t)-approximation for some function f.

Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(kc) has treewidth at least k or contains a subdivision of a complete binary tree of height k.

Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t' in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t'+1)h+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.

 

Joint work with Carla Groenland, Gwenaël Joret, and Wojciech Nadara.

04.03.2021 16:15
Bartłomiej Bosek
Combinatorial Optimization
Majority choosability of digraphs

One of the variations of coloring a graph is assigning colors to vertices such that for each vertex v, at most half of the neighbors of v have the same color as v. Such coloring is called majority coloring of the graph. The goal is to color the graph as a majority with the fewest possible colors. During the presentation, various variants of this problem, historical results, the latest results as well as still intriguing hypotheses will be discussed. Among other things, the results of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented.

  1. László Lovász, On decomposition of graphs Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences, 1, 237–238, 1966.
  2. Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 25, 303–312, 1974.
  3. Dominic van der Zypen, Majority coloring for directed graphs MathOverflow, 2016.
  4. Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, and David R. Wood, Majority colourings of digraphs, Electronic Journal of Combinatorics, 24(2):Paper 2.25, 9, 2017.
  5. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Majority Choosability of Digraphs Electronic Journal of Combinatorics, 24(3), Paper 3.57, 2017.
  6. António Girao, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Samal, Linear bound for majority colourings of digraphs, Electronic Journal of Combinatorics, 25(3):Paper 3.29, 4, 2018.
  8. Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak, Majority Coloring Game, Discrete Applied Mathematics, 255, 15–20, 2019.

(the seminar will only be online)

25.02.2021 16:15
Kamil Kropiewnicki
Combinatorial Optimization
Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming

We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the Exponential Time Hypothesis fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems. This presentation might be of interest for, among the others, the participants of the Algorithmic Game Theory course as it presents the modern approach for maximizing revenue in second-price auctions.

  1. Joey Huchette, Haihao Lu, Hossein Esfandiari, Vahab Mirrokni. Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming. arXiv:2002.08841. 2020.
  2. Kamil Kropiewnicki. Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming. slides. 2021.

(the seminar will only be online)

28.01.2021 17:00
Rafał Burczyński
Combinatorial Optimization
Bollobás-Eldridge-Catlin Conjecture on graph packing

Let G1, G2 be n-vertex graphs. We say that they pack if they are edge-disjoint subgraphs of a complete graph on n vertices. The Bollobás-Eldridge-Catlin conjecture states that if (Δ(G1) + 1) (Δ(G2) + 1) < n + 1, then G1 and G2 pack. During the seminar, we will take a look at current results related to this problem, i.e. classes of graphs for which it has been proven as well as similar conjectures stemming from it.

  1. Rafał Burczyński. Bollobás-Eldridge-Catlin Conjecture. slides. 2021.

(the seminar will only be online)