Seminaria

25.05.2022 16:15
Szymon Toruńczyk
University of Warsaw
Informatyka Teoretyczna
Ordered graphs of bounded twin-width and monadically NIP graph classes

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.

This has several consequences.First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobás, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.

Those results are joint work with Bonnet, Giocanti, Ossona de Mendez, Simon, Thomasse, accepted to STOC'22.

Time permitting, I will also discuss the more general landscape of monadically NIP graph classes, generalizing both nowhere dense classes and classes of bounded twin-width.

25.05.2022 12:15
Vitaliy Mysak
Podstawy Informatyki
An Introduction to the Clocked Lambda Calculus byJörg Endrullis, Dimitri Hendriks, Jan Willem Klop, and Andrew Polonsky
We give a brief introduction to the clocked λ-calculus, an extension of the classical λ-calculus with a unary symbol τ used to witness the β-steps. In contrast to the classical λ-calculus, this extension is infinitary strongly normalising and infinitary confluent. The infinitary normal forms are enriched Lévy–Longo Trees, which we call clocked Lévy–Longo Trees.
01.06.2022 12:15
Juliusz Wajgelt
Podstawy Informatyki
EFFICIENT FULL HIGHER-ORDER UNIFICATION by PETAR VUKMIROVIC, ALEXANDER BENTKAMP, AND VISA NUMMELIN
We developed a procedure to enumerate complete sets of higher-order unifiers based on work by Jensen and Pietrzykowski. Our procedure removes many redundant unifiers by carefully restricting the search space and tightly integrating decision procedures for fragments that admit a nite complete set of uni ers. We identify a new such fragment and describe a procedure for computing its uni ers. Our uni cation procedure, together with new higher-order term indexing data structures, is implemented in the Zipperposition theorem prover. Experimental evaluation shows a clear advantage over Jensen and Pietrzykowski's procedure.
08.06.2022 12:15
Karolina Gontarek
Podstawy Informatyki
THE TU–DENG CONJECTURE HOLDS ALMOST SURELY by LUKAS SPIEGELHOFER AND MICHAEL WALLNER

The Tu–Deng Conjecture is concerned with the sum of digits w(n) of n in base 2 (the Hamming weight of the binary expansion of n) and states the following: assume that k is a positive integer and t \in  {1, . . . , 2^k 2}. Then

#\{ (a, b) {0, . . . , 2k 2}^2 : a + b t mod 2^k 1, w(a) + w(b) < k \ \leq 2^{k-1}


We prove that the Tu–Deng Conjecture holds almost surely in the following sense: the proportion of t \in {1, . . . , 2^k 2} such that the above inequality holds approaches 1 as k tends to infinity. Moreover, we prove that the Tu–Deng Conjecture implies a conjecture due to T. W. Cusick concerning the sum of digits of n and n + t.

08.06.2022 16:15
Michał Wrona
Jagiellonian
Informatyka Teoretyczna
Local consistency methods in Solving CSPs and CSP-like problems over omega-categorical structures

Feder-Vardi conjecture has been settled independently by Dmitriy Zhuk and Andrei Bulatov. What is perhaps even more interesting, though, is that they not only confirmed the complexity (Feder-Vardi) conjecture, i.e., CSP(B) for a finite structure B is either in P or it is NP-complete, but they also confirmed the algebraic dichotomy conjecture describing  tractable B in terms of operations preserving B.

A similar algebraic dichotomy conjecture called an infinite algebraic dichotomy conjecture has been established for CSP(B) over first-order reducts B of finitely bounded homogeneous structures, all of which are in particular omega-categorical. Despite recent advances towards solving this dichotomy, it still seems to be wide open. One of the reasons is probably that local consistency  and similar algorithmic techniques are in this context not yet fully understood. This step seems to be crucial since the characterization of finite-domain CSP solvable by local consistency  is considered as a major step towards the resolution of the dichotomy.

In this talk, I will survey the results on the local consistency methods in solving CSP and CSP-like problems over omega-categorical structures.

Poprzednie referaty

19.05.2022 14:15
Andrii Orap, Maksym Zub
Algorytmika
Grundy Distinguishes Treewidth from Pathwidth

Strukturalne parametry grafów, takie jak treewidth, pathwidth i clique-width, są głównym tematem badań sparametryzowanej złożoności. Głównym celem badań w tej dziedzinie jest zrozumienie „ceny ogólności” tych szerokości: kiedy przechodzimy od pojęć bardziej restrykcyjnych do bardziej ogólnych, jakie są problemy, w których złożoność pogarsza się z fixed-parameter tractable do intractable? Ten rodzaj pytania jest już bardzo dobrze zbadany, ale, co jest dość uderzające, algorytmiczna granica między dwoma (prawdopodobnie) najbardziej centralnymi pojęciami szerokości (notacjami), treewidth i pathwidth, jest nadal niezrozumiała: obecnie nie jest znany żaden naturalny problem na grafie, który byłby W-trudny dla jednego, ale FPT dla drugiego. Rzeczywiście, zaskakującym rozwojem ostatnich kilku lat była obserwacja, że: w przypadku wielu najbardziej paradygmatycznych problemów ich złożoność dla tych dwóch parametrów w rzeczywistości dokładnie się pokrywają, pomimo faktu, że szerokość drzewa jest parametrem o wiele bardziej ogólnym. W ten sposób wydaje się, że dodatkowa ogólność szerokości drzewa nad szerokością ścieżki często przychodzi „za darmo”.

Naszym głównym wkładem w ten artykuł jest odkrycie pierwszego naturalnego przykładu, w którym ta ogólność ma wysoką cenę. Rozważamy Grundy Coloring, wariację kolorowania, w której próbujemy obliczyć najgorsze możliwe kolorowanie, które można przypisać do grafu przez zachłanny algorytm First-Fit . Pokazujemy, że ten dobrze zbadany problem jest parametryzowany (FPT) przez pathwidth; jednakże to staje się znacznie trudniejsze (W[1]-hard), gdy jest sparametryzowany przez treewidth. Ponadto pokazujemy, że Grundy Coloring sprawia, że jest drugi skok złożoności dla bardziej ogólnych szerokości, gdy staje się para-NP-hard dla clique-width. Dlatego Grundy Coloring ładnie oddaje złożoność kompromisów między trzema najlepiej zbadanymi parametrami. Uzupełniając obraz, pokazujemy, że Grundy Coloring jest parametryzowane przez FPT według modular-width.

18.05.2022 16:15
Rose McCarty
University of Warsaw
Informatyka Teoretyczna
Circuit decompositions of group-labelled graphs

This talk focuses on Eulerian graphs whose arcs are directed and labelled in a group. Each circuit yields a word over the group, and a circuit is non-zero if this word does not evaluate to 0. We give a precise min-max theorem for the following problem. Given a vertex v, what is the maximum number of non-zero circuits in a circuit-decomposition where each circuit begins and ends at v?

This is joint work with Jim Geelen and Paul Wollan. Our main motivation is a surprising connection with vertex-minors which is due to Bouchet and Kotzig.

18.05.2022 12:15
Jan Koscisz
Podstawy Informatyki
Functions-as-constructors higher-order unification: extended pattern unification by Tomer Libal and Dale Miller
Unification is a central operation in constructing a range of computational logic systems based on first-order and higher-order logics. First-order unification has several properties that guide its incorporation in such systems. In particular, first-order unification is decidable, unary, and can be performed on untyped term structures. None of these three properties hold for full higher-order unification: unification is undecidable, unifiers can be incomparable, and term-level typing can dominate the search for unifiers. The so-called pattern subset of higher-order unification was designed to be a small extension to first-order unification that respects the laws governing λ-binding (i.e., the equalities for α, β, and η-conversion) but which also satisfied those three properties. While the pattern fragment of higher-order unification has been used in numerous implemented systems and in various theoretical settings, it is too weak for many applications. This paper defines an extension of pattern unification that should make it more generally applicable, especially in proof assistants that allow for higher-order functions. This extension’s main idea is that the arguments to a higher-order, free variable can be more than just distinct bound variables. In particular, such arguments can be terms constructed from (sufficient numbers of) such bound variables using term constructors and where no argument is a subterm of any other argument. We show that this extension to pattern unification satisfies the three properties mentioned above.
12.05.2022 17:00
Jacek Salata
Optymalizacja Kombinatoryczna
A Short Proof of Nash-Williams' Theorem for the Arboricity of a Graph

TBA

12.05.2022 16:15
Kamil Galewski
Optymalizacja Kombinatoryczna
Bears with Hats and Independence Polynomials

TBA

12.05.2022 14:15
Nazarii Denha, Ruslan Yevdokymov
Algorytmika
Finding Balance-Fair Short Paths in Graphs
11.05.2022 16:15
Michał Seweryn
Jagiellonian
Informatyka Teoretyczna
Forcing walls with divisibility constraints

An n-wall is a graph obtained from the square grid with n rows and 2n columns by deleting every odd vertical edge in every odd row and even vertical edge in every even row, then deleting the two resulting vertices of degree 1, and finally subdividing each edge any number of times. Thomassen showed that there exists a function f(n,m) such that every f(n,m)-wall contains an n-wall such that every path between two branch vertices has length divisible by m. We study the asymptotics of the optimal such function f(n,m). For odd m we show that f(n,m) = O(n·poly(m)). In the case m=2, we obtain a bound f(n, 2) = O(n·log n).

This is joint work with Piotr Micek, Raphael Steiner and Sebastian Wiederrecht.

11.05.2022 12:14
Roch Wójtowicz
Podstawy Informatyki
SHARP THRESHOLDS OF GRAPH PROPERTIES, AND THE k-SAT PROBLEM by EHUD FRIEDGUT AND AN APPENDIX BY JEAN BOURGAIN

Consider G(n, p) to be the probability space of random graphs on n vertices with edge probability p. We will be considering subsets of this space defined by monotone graph properties. A monotone graph property P is a property of graphs such that


a) P is invariant under graph automorphisims.
b) If graph H has property P , then so does any graph G having H as a subgraph.
 

A monotone symmetric family of graphs is a family defined by such a property. One of the first observations made about random graphs by Erdos and Renyi in their seminal work on random graph theory [12] was the existence of threshold phenomena, the fact that for many interesting properties P , the probability of P appearing in G(n, p) exhibits a sharp increase at a certain critical value of the parameter p. Bollob ́as and Thomason proved the existence of threshold functions for all monotone set properties ([6]), and in [14] it is shown that this behavior is quite general, and that all monotone graph properties exhibit threshold behavior, i.e. the probability of their appearance increases from values very close to 0 to values close to 1 in a very small interval. More precise analysis of the size of the threshold interval is done in [7]. This threshold behavior which occurs in various settings which arise in combinatorics and computer science is an instance of the phenomenon of phase transitions which is the subject of much interest in statistical physics. One of the main questions that arises in studying phase transitions is: how “sharp” is the transition? For example, one of the motivations for this paper arose from the question of the sharpness of the phase transition for the property of satisfiability of a random k-CNF Boolean formula. Nati Linial, who introduced me to this problem, suggested that although much concrete analysis was being performed on this problem the best approach would be to find general conditions for sharpness of the phase transition, answering the question posed in [14] as to the relation between the length of the threshold interval and the value of the critical probability.

05.05.2022 17:00
Szymon Salabura
Optymalizacja Kombinatoryczna
Contact graphs of ball packings

TBA

05.05.2022 16:15
Mateusz Pach
Optymalizacja Kombinatoryczna
Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

TBA

05.05.2022 14:15
Krzysztof Pióro, Krzysztof Potępa
Algorytmika
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance

W problemie odległości między drzewami dane są dwa ukorzenione drzewa z etykietami na krawędziach. Dodatkowo dla każdego wierzchołka jego dzieci mają ustalony porządek. Naszym celem jest znalezienie minimalnej liczby operacji kontrakcji krawędzi i zmiany etykiety krawędzi, tak aby doprowadzić oba drzewa do takiego samego drzewa.

Autor pracy pokazuje algorytm o złożoności O(n2.9546) dla wariantu tego problemu, w którym operacje mają koszty jednostkowe. Jest to pierwszy podsześcienny algorytm dla problemu odległości edycyjnej między drzewami. Warto tutaj zwrócić uwagę, że dla wariantu o dowolnych kosztach operacji istnieje warunkowe ograniczenie dolne, które mówi, że nie istnieje dla tego problemu algorytm podsześcienny. Zatem autor pokazuje, że wariant z jednostkowymi kosztami najprawdopodobniej jest istotnie prostszy od wariantu ogólnego.

Aby złamać granicę O(n3) autor redukuje problem do mnożenia macierzy max-plus, w których sąsiednie elementy różnią się co najwyżej o stałą. O takim problemie zostało już udowodnione wcześniej, że może zostać rozwiązany w czasie podsześciennym. 

04.05.2022 16:15
Jakub Kozik
Jagiellonian
Informatyka Teoretyczna
Deterministic Constructions of 3-Chromatic Hypergraphs with Few Edges

How many edges do we need to build a k-uniform hypergraph that cannot be properly two colored? Using the probabilistic argument Erdös proved in 1964, that there exist such hypergraphs with roughly k2·2k edges. However, without a random source at hand, the sizes that we can achieve by efficient procedures are much larger. The first and only known explicit construction with 2k+o(k) edges was proposed by Gebauer in 2013. We will discuss how it can be improved first by randomizing and then derandomizing it once more.

28.04.2022 17:00
Karolina Gontarek
Optymalizacja Kombinatoryczna
On topological aspects of orientations

TBA

28.04.2022 16:15
Ruslan Yevdokymov
Optymalizacja Kombinatoryczna
Flexible Color Lists in Alon and Tarsi’s Theorem, and Time Scheduling with Unreliable Participants

TBA

28.04.2022 14:15
Jakub Fedak, Mateusz Golonka
Algorytmika
Wordle is NP-hard
Wordle jest grą dla jednego gracza, której celem jest zgadnięcie pewnego słowa x wybranego ze słownika D. Aby zgadnąć słowo x gracz może wykonać co najwyżej k prób, przy czym w każdej próbie gracz musi podać słowo, które również znajduje się w słowniku D. Wszystkie słowa w słowniku mają długość n. Po każdej próbie zgadnięcia gracz otrzymuje informację o pozycjach, na których jego słowo zgadza się z rozwiązaniem oraz o literach z podanego słowa, które znajdują się w rozwiązaniu, lecz na innej pozycji. Autorzy udowadniają, że następujący problem jest NP-trudny: mając dany słownik D oraz liczbę naturalną k powiedzieć, czy gracz może zagwarantować zgadnięcie słowa w k próbach. Ponadto autorzy dowodzą, że dla słów długości 5 ten problem pozostaje trudny, a nawet w tym przypadku przybliżenie najmniejszej liczby prób potrzebnej do zagwarantowania zgadnięcia słowa jest NP-trudne. W pracy znajdują się również wyniki dotyczące złożoności parametryzowanej oraz kilka pytań otwartych związanych z tym tematem.
27.04.2022 16:15
Andrew Suk
University of California at San Diego
Informatyka Teoretyczna
Unavoidable patterns in simple topological graphs

A simple topological graph is a graph drawn in the plane so that its vertices are represented by points, and its edges are represented by non-self-intersecting arcs connecting the corresponding points, with the property that any two edges have at most one point in common. In 2003, Pach-Solymosi-Tóth showed that every n-vertex complete simple topological graph contains a topological subgraph on m = Ω(log n) vertices that is weakly isomorphic to the complete convex geometric graph or to the complete twisted graph on m vertices. Here,  we improve this bound to  (log n)1/4−o(1). I will also discuss other related problems as well.

This is joint work with Ji Zeng.

27.04.2022 12:15
Roch Wójtowicz
Podstawy Informatyki
SEMINARIUM i WYSTĄPIENIE ROCHA WÓJTOWICZA PRZENIESINE NA 11.05.2022

Consider G(n, p) to be the probability space of random graphs on n vertices with edge probability p. We will be considering subsets of this space defined by monotone graph properties. A monotone graph property P is a property of graphs such that


a) P is invariant under graph automorphisims.
b) If graph H has property P , then so does any graph G having H as a subgraph.
 

A monotone symmetric family of graphs is a family defined by such a property. One of the first observations made about random graphs by Erdos and Renyi in their seminal work on random graph theory [12] was the existence of threshold phenomena, the fact that for many interesting properties P , the probability of P appearing in G(n, p) exhibits a sharp increase at a certain critical value of the parameter p. Bollob ́as and Thomason proved the existence of threshold functions for all monotone set properties ([6]), and in [14] it is shown that this behavior is quite general, and that all monotone graph properties exhibit threshold behavior, i.e. the probability of their appearance increases from values very close to 0 to values close to 1 in a very small interval. More precise analysis of the size of the threshold interval is done in [7]. This threshold behavior which occurs in various settings which arise in combinatorics and computer science is an instance of the phenomenon of phase transitions which is the subject of much interest in statistical physics. One of the main questions that arises in studying phase transitions is: how “sharp” is the transition? For example, one of the motivations for this paper arose from the question of the sharpness of the phase transition for the property of satisfiability of a random k-CNF Boolean formula. Nati Linial, who introduced me to this problem, suggested that although much concrete analysis was being performed on this problem the best approach would be to find general conditions for sharpness of the phase transition, answering the question posed in [14] as to the relation between the length of the threshold interval and the value of the critical probability.

21.04.2022 17:00
Wojciech Buczek
Optymalizacja Kombinatoryczna
On an early paper of Maryam Mirzakhani

In this seminar, we will talk about Maryam Mirzakhani, who had an enormous influence on research about Combinatorics. We will study her idea of creating a small (with (only!) 63 vertices), non-4-choosable planar graph, which is also 3-choosable. We will also consider other problems she worked on.

  1. William J. Martin. On an early paper of Maryam Mirzakhani. arXiv:1709.07540. (2017).
  2. Wojciech Buczek. slides. (2022).
21.04.2022 16:15
Maciej Nemś
Optymalizacja Kombinatoryczna
Avoiding squares over words with lists of size three amongst four symbols

Word creation from lists of size t is a problem where for alphabet Σ each sign of created word is chosen from a list of t different signs from Σ. Word is "square-free" when it does not contain any squares. A square is a word of form ww with w being a nonempty word. The author first shows that there are at least 2.45n square-free words of length n created from lists of 4. This is an improvement from the previous bound which is 2n. After that, the main result of the paper is shown which is an existence of at least 1.25n words of length n from lists of 3.

  1. Rosenfeld, Matthieu. Avoiding squares over words with lists of size three amongst four symbols. arXiv:2104.09965. (2021).
  2. Maciej Nemś. slides. (2022).
21.04.2022 14:15
Piotr Kaliciak, Kamil Galewski
Algorytmika
A Simple Algorithm for Graph Reconstruction
Praca skupia się na efektywnej rekonstrukcji grafu, przy pomocy zapytań o odległości między wierzchołkami. Rozważane grafy są spójne, nieważone oraz mają ograniczony stopień, a celem jest znalezienie wszystkich krawędzi w grafie.
Analizowany jest prosty algorytm rekonstrukcji. Autorzy dowodzą, że na ∆-regularnym grafie wykonuje on O(n*polylog(n)) zapytań. Ponadto można go zmodyfikować pod inne rodzaje zapytań. Co więcej, algorytm ten łatwo jest zrównoleglić. W przypadku grafów o ograniczonym stopniu, algorytm potrzebuje o(n2) zapytań.
20.04.2022 16:15
Sergey Norin
McGill University
Informatyka Teoretyczna
Brambles, stack number and topological overlap

A (strict) bramble in a graph G is a collection of subgraphs of G such that the union of any number of them is connected. The order of a bramble is the smallest size of a set of vertices that intersects each of the subgraphs in it. Brambles have long been part of the graph minor theory toolkit, in particular, because a bramble of high order is an obstruction to existence of  a low width tree decomposition.

We will discuss two dimensional analogues of brambles. In particular, we show that a bramble of high order in a two-dimensional simplicial complex X is an obstruction to existence of a low multiplicity continuous map from X  to the plane (and more generally to any two-dimensional collapsible complex). As an application, we show that strong products of three paths have unbounded stack number.

Based primarily on joint work with David Eppstein,  Robert Hickingbotham, Laura Merker, Michał T. Seweryn and David R. Wood. (https://arxiv.org/abs/2202.05327)

14.04.2022 16:15
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
From 1-2-3 conjecture to Riemann hypothesis

We consider some coloring issues related to the famous Erdős Discrepancy Problem. A set of the form As,k={s,2s,…,ks}, with s,k ∈ N, is called a homogeneous arithmetic progression. We prove that for every fixed k there exists a 2-coloring of N such that every set As,k is perfectly balanced (the numbers of red and blue elements in the set As,k differ by at most one). This prompts reflection on various restricted versions of Erdős' problem, obtained by imposing diverse confinements on parameters s,k. In a slightly different direction, we discuss a majority variant of the problem, in which each set As,k should have an excess of elements colored differently than the first element in the set. This problem leads, unexpectedly, to some deep questions concerning completely multiplicative functions with values in {+1,−1}. In particular, whether there is such a function with partial sums bounded from above.

13.04.2022 16:15
Alex Scott
University of Oxford
Informatyka Teoretyczna
Induced subgraphs of induced subgraphs of large chromatic number

We prove that for every graph F with at least one edge there is a constant cF and there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most cF. (Here a graph is F-free if it does not contain an induced copy of F.) This generalizes theorems of Briański, Davies and Walczak, and of Carbonero, Hompe, Moore and Spirkl.  We further show an analogous statement where clique number is replaced by odd girth.

Joint work with Antonio Girao, Freddie Illingworth, Emil Powierski, Michael Savery, Youri Tamitegama and Jane Tan.

07.04.2022 17:00
Marcin Serwin
Optymalizacja Kombinatoryczna
Can a party represent its constituency?

Upon gaining p% votes in an election in a proportional system, a party appoints p% of its proposed candidates to represent the party. The order of candidates to appoint is chosen beforehand. This may create tensions if the party members are not perfectly aligned politically, if some candidates of particular tendency are lower down the list and thus less likely to be appointed. This presentation examines the problem of existence and characterization of the list that would not create such tension and related problems.

  1. Amoz Kats. Can a Party Represent Its Constituency?. Public Choice. 44(3), 453-456. (1984).
  2. Marcin Serwin. Can a party represent its constituency? slides. (2022).
07.04.2022 16:15
Piotr Kaliciak
Optymalizacja Kombinatoryczna
2-List-coloring planar graphs without monochromatic triangles

The author is considering a planar graph, where every vertex has a list of 2 colors, and every coloring of this graph has to choose for every vertex one of these two colors. Unlike the standard colorings, the author doesn't mind having a monochromatic edge, but he tries to avoid having a monochromatic triangle. In this paper, he not only proves, that every planar graph can be colored this way, for every list assignment, but also he proves a stronger result for graphs with some vertices pre-colored.

  1. Carsten Thomassen. 2-List-coloring planar graphs without monochromatic triangles. Journal of Combinatorial Theory, Series B. 98(6). 1337-1348. (2008).
  2. Piotr Kaliciak. List coloring planar graphs without monochromatic triangles. slides. (2022).
07.04.2022 14:15
Bartłomiej Błoniarz, Inka Sokołowska
Algorytmika
On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
Unbounded SubsetSum to problem w którym dane są liczby c,u oraz n liczb całkowitych w1,...,wn z przedziału [1,u]. Trzeba odpowiedzieć na pytanie czy istnieją liczby całkowite m1,...,mn spełniające c = w1*m1 + ... + wn*mn. W wersji all-target problemu dana jest liczba naturalna t i należy podać odpowiedź dla wszystkich instancji z c z przedziału [0,t].
Praca skupia się na trzech generalizacjach tego problemu:
1. All-target Unbounded Knapsack - wariant dobrze znanego problemu plecakowego, dla którego przedstawiony jest algorytm Õ(T(u)+t) gdzie T(n) to czas obliczania (min,+)-splotu dla tablic długości n
2. All-target CoinChange - wariant problemu wydawania reszty, dla którego przedstawiony jest algorytm Õ(u+t)
3. Residue Table, dla którego przedstawiony jest algorytm Õ(u).
06.04.2022 16:15
Marcin Briański
Jagiellonian
Informatyka Teoretyczna
Separating polynomial χ-boundedness from χ-boundedness and thereabouts

If a graph contains no large complete subgraph but nonetheless has high chromatic number what can we say about the structure of such a graph? This question naturally leads to investigation of χ-bounded classes of graphs — graph classes where a graph needs to contain a large complete subgraph in order to have high chromatic number. This an active subfield of graph theory with many long standing open problems as well as interesting recent developments.

In this talk I will present a construction of a hereditary class of graphs which is χ-bounded but not polynomially χ-bounded. This construction provides a negative answer to a conjecture of Esperet that every χ-bounded hereditary class of graphs is polynomially χ-bounded. The construction is inspired by a recent paper of Carbonero, Hompe, Moore, and Spirkl which provided a counterexample to another conjecture of Esperet.

This is joint work with James Davies and Bartosz Walczak (available at arXiv:2201.08814)

06.04.2022 12:15
Aleksander Katan
Podstawy Informatyki
A simple proof of the undecidability of strong normalization by Paweł Urzyczyn
The purpose of this note is to give a methodologically simple proof of the undecidability of strong normalization in the pure lambda calculus. For this we show how to represent an arbitrary partial recursive function by a term whose application to any Church numeral is either strongly normalizable or has no normal form. Intersection types are used for the strong normalization argument.
31.03.2022 17:00
Katarzyna Król
Optymalizacja Kombinatoryczna
On List-Coloring Outerplanar Graphs

An outerplanar graf is a planar graph whose vertices can all be drawn on the outer face. The author researched the problem of coloring outerplanar graphs from lists. First, it is shown that the outerplanar graph is L-colorable if satisfies |L(v)| ≥ min{deg(v),4} and is bipartite. Then additional assumptions are searched for so that a similar inequality could define L-colorability in general outerplanar graphs. The results given by the author are the best possible for each condition in the bounds and hypotheses.

  1. J.P. Hutchinson. On list-coloring outerplanar graphs. J. Graph Theory. 59, 59-74. (2008).
  2. Katarzyna Król. On List-Coloring Outerplanar Graphs. slides. (2022).
31.03.2022 16:15
Jędrzej Kula
Optymalizacja Kombinatoryczna
Multiple list colouring of planar graphs

Since every planar graph G can be colored by 4 colors, there is also an integer m such that G is (4m,m)-choosable. The problem here is that such m is changing with G. The author of this paper proves that there cannot be such a universal m that every planar graph is (4m,m)-choosable. To be precise he shows that for each positive integer m, there is a planar graph G which is not (4m+⌊(2m-1)/9⌋,m)-choosable. Also, he poses some conjectures about planar graphs multiple list coloring.

  1. Xuding Zhu. Multiple list colouring of planar graphs. Journal of Combinatorial Theory, Series B. 122, 794-799. (2017).
  2. Jędrzej Kula. Multiple list colouring of planar graphs. slides. (2022).
31.03.2022 14:15
Tomasz Buczyński, Łukasz Gniecki
Algorytmika
On Determinism Versus Non-Determinism and Related Problems
Pokazujemy, że dla wielotaśmowych maszyn Turinga działających w czasie liniowym, niedeterminizm jest mocniejszy od determinizmu, czyli że klasa języków rozpoznawanych przez takie maszyny deterministyczne jest ścisłą podklasą języków rozpoznawanych przez takie maszyny niedeterministyczne.
30.03.2022 16:15
Raphael Steiner
ETH Zürich
Informatyka Teoretyczna
New bounds for relatives of Hadwiger's conjecture

In this talk, I will present some recent results on two variants of Hadwiger's conjecture.

             First, I will discuss the so-called Odd Hadwiger's conjecture, a strengthening of Hadwiger's conjecture proposed by Gerards and Seymour in 1995. First I will show how, using a simple new trick, one can reduce the problem of coloring graphs with no odd Kt-minor to coloring graphs with no Kt-minor up to a constant factor of 2, thereby improving previous upper bounds for this problem. Then, I will outline how a similar idea can be used to significantly improve the known bounds for clustered colorings of odd Kt-minor free graphs, in which we look for (possibly improper) colorings with monochromatic components of small size.

            Second,  I will discuss the so-called List Hadwiger's conjecture,  which states that there exists a constant c such that every graph with no Kt-minor is ct-choosable (i.e.,  list colorable).   I will show a probabilistic construction of a new lower bound  2t-o(t)  for list coloring  Kt-minor free graphs,  this refutes a conjecture by Kawarabayashi and Mohar which stated that one can take c=3/2.  I will then show how some well-chosen modifications to our construction can be used to prove lower bounds also for list coloring  H-minor free graphs where  H  is non-complete. In particular, I will show that   Ks,t-minor free graphs  for large comparable  s  and  t  can have list chromatic number  at least  (1-o(1))(s+t+min(s,t)),  this refutes a 2001 conjecture by Woodall.

30.03.2022 12:15
Filip Synowiec
Podstawy Informatyki
Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability by Antoine Genitrini and Cécile Mailler
This article is motivated by the following satisfiability question: pick uniformly at random an and{or Boolean expression of length n, built on a set of $k_n$ Boolean variables. What is the probability that this expression is satisfiable? asymptotically when n tends to infinity? The model of random Boolean expressions developed in the present paper is the model of Boolean Catalan trees, already extensively studied in the literature for a constant sequence. The fundamental breakthrough of this paper is to generalize the previous results for any (reasonable) sequence of integers which enables us, in particular, to solve the above satisfiability question. We also analyze the effect of introducing a natural equivalence relation on the set of Boolean expressions. This new quotient model happens to exhibit a very interesting threshold (or saturation) phenomenon.
24.03.2022 17:00
Jędrzej Hodor
Optymalizacja Kombinatoryczna
Clustered Coloring and Hadwiger's conjecture

Hadwiger conjecture states, that for every Ks+1 minor free graph it can be colored with s colors. For now, it is wide open. There are plenty of well-known results improving the bound on the number of colors. However, there exists another approach to make the problem easier. We can relax the notion of proper coloring. A graph class can be η-clustered colored with n colors if in every graph only n colors are used and the size of each monochromatic component is bounded by η. Liu and Wood proved that for a class of graphs excluding Ks+1 minor can be η(s)-clustered colored with s+2 colors, which is almost optimal (s < s+2). I will describe their approach and prove the result in a simplified case.

  1. Chun-Hung Liu, David R. Wood. Clustered Coloring of Graphs Excluding a Subgraph and a Minor. arXiv:1905.09495. 2019.
  2. Jędrzej Hodor. Clustered Coloring of Graphs Excluding a Subgraph and a Minor. slides. (2022).
24.03.2022 16:15
Grzegorz Gawryał
Optymalizacja Kombinatoryczna
The Catalan matroid

A path of length 2n, that starts in (0,0) and at each step moves from (x,y) to (x+1,y+1) or (x+1,y-1) is a Dyck path, if it ends in (2n,0) and never passes below y=0 line. Such paths are counted by Catalan numbers. In this presentation, we'll show, that the Dyck paths for fixed n form a matroid. We'll show what are bases, independent sets, and other matroid-related terms in this object, explore some properties of this matroid, and see how it generalizes to shifted matroids.

  1. Federico Ardila. The Catalan matroid. arXiv:math/0209354. 2002.
  2. Grzegorz Gawryał. The Catalan Matroid. slides. (2022).
24.03.2022 14:15
Mateusz Pach, Michał Wronka
Algorytmika
Making Life More Confusing for Firefighters
Problem Firefighter polega na opracowaniu strategii rozsyłania strażaków do obrony wierzchołków grafu przed rozprzestrzeniającym się przez krawędzie ogniem, tak by jak najmniej wierzchołków spłonęło; problem ten jest NP-trudny dla znakomitej większości klas grafów. By zamodelować scenariusz z cywilami pomagającymi strażakom, wprowadzamy problem Temporal Firefighter będący rozszerzeniem na dynamiczne grafy. Pokazujemy, że problem Temporal Firefighter jest NP-trudny i pozostaje taki dla wszystkich klas grafów (poza jedną) o których wiadomo, że posiadają wielomianowe rozwiązanie problemu Firefighter. Pokazujemy też algorytm FPT dla Temporal Firefighter, parametryzowany wartością vertex-interval-membership-width.
23.03.2022 16:15
Mathieu Mari
University of Warsaw and IDEAS-NCBR
Informatyka Teoretyczna
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles

We study the Maximum Independent Set of Rectangles (MISR) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality. In a recent breakthrough, Mitchell [2021] obtained the first constant-factor approximation algorithm for MISR. His algorithm achieves an approximation ratio of 10 and it is based on a dynamic program that intuitively recursively partitions the input plane into special polygons called corner-clipped rectangles (CCRs), without intersecting certain special horizontal line segments called fences.

In this talk, I will present a (2+ϵ)-approximation algorithm for MISR which is also based on a recursive partitioning scheme. First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than CCRs. This allows us to provide an arguably simpler analysis and at the same time already improves the approximation ratio to 4. Then, using a more elaborate charging scheme and a recursive partitioning into general axis-parallel polygons with constant complexity, we improve our approximation ratio to 2+ϵ. In particular, we construct a recursive partitioning based on more general fences which can be sequences of up to O(1/ϵ) line segments each. This partitioning routine and our other new ideas may be useful for future work towards a PTAS for MISR.

At the end of the talk, I will present a bunch of open questions related to the problem.

This is a joint work with Waldo Gálvez, Arindam Khan, Tobias Mömke, Madhusudhan Reddy and Andreas Wiese
23.03.2022 12:15
Michał Woźny
Podstawy Informatyki
COUNTING WITH IRRATIONAL TILES by SCOTT GARRABRANT and IGOR PAK
We introduce and study the number of tilings of unit height rectangles with irrational tiles. We prove that the class of sequences of these numbers coincides with the class of diagonals of N-rational generating functions and a class of certain binomial multisums. We then give asymptotic applications and establish connections to hypergeometric
functions and Catalan numbers.
17.03.2022 16:15
Krzysztof Ziobro
Optymalizacja Kombinatoryczna
A note on polynomials and f-factors of graphs

The factor of a graph is its spanning subgraph which adheres to given constraints on the degrees. The authors of the article discuss the f-factor, which for every vertex defines a set of possible degrees. The main result shows a new sufficient condition for the existence of an f-factor in a given graph. Authors obtain it by using Combinatorial Nullstellensatz.

  1. Hamed Shirazi, Jacques Verstraëte. A Note on Polynomials and f-Factors of Graphs. Electronic journal of combinatorics. 15, N22. 2008.
  2. Krzysztof Ziobro. A note on polynomials and f -factors of graphs. slides. (2022).
17.03.2022 14:15
Ignacy Buczek, Michał Woźny
Algorytmika
Sorting Balls and Water: Equivalence and Computational Complexity

Problemy sortowania od długiego czasu są obiektem różnego rodzaju badań. Ostatnio dwie gry na telefon w tematyce sortowania zyskały na popularności. W tych grach, gracz ma do dyspozycji urny wypełnione kolorowymi obiektami (w przypadku jednej są to kule, a w przypadku drugiej woda) oraz kilka pustych urn, a jego celem jest posortowanie obiektów zgodnie z kolorami. W jednym ruchu może on przenieść obiekty z jednej urny do drugiej, jeżeli kolor przenoszonych obiektów zgadza się z kolorem najwyższego obiektu docelowej urny lub urna ta jest pusta.

W pracy autorzy badają złożoność obliczeniową tych łamigłówek. Na początku pokazują, że te gry są w równoważne pod kątem rozwiązywalności. Dokładniej mówiąc, rozwiązywalność stanu początkowego gry nie zależy od tego czy obiekty zachowują się jak kule, czy jak woda. Dowodzą również, że dla każdej tak-instancji istnieje rozwiązanie wielomianowego rozmiaru, co pokazuje, że problem rozwiązywalności tych łamigłówek jest w NP. Następnie uzasadniają, że ten problem jest NP-zupełny. Znajdują również wielomianowe algorytmy dla szczególnych przypadków. Na samym końcu zastanawiają się, jak wiele pustych urn jest potrzebnych, aby instancja była rozwiązywalna niezależnie od początkowego rozmieszczenia obiektów. Pokazują nietrywialne ograniczenia (dolne i górne) zależne od ilości początkowo zapełnionych urn i ich pojemności.

16.03.2022 16:15
Marek Sokołowski
University of Warsaw
Informatyka Teoretyczna
Graphs of bounded twin-width are quasi-polynomially χ-bounded

We prove that for every t∈ℕ there is a constant γ(t) such that every graph with twin-width at most t and clique number ω has chromatic number bounded by 2γ(t) log^{4t+3} ω. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially χ-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially χ-bounded.

This is a joint work with Michał Pilipczuk

16.03.2022 12:15
Ignacy Buczek
Podstawy Informatyki
Dömösi, Horváth and Ito’s Hypothesis on the Language of Primitive Words
A word is called primitive if it is not a repetition of another word. The language of all primitive words over a fixed alphabet \Sigma is denoted as Q. We consider the question of whether Q over \Sigma with at least 2 different characters is context-free or not. We show that Q is not regular and that it is context-sensitive. We exclude Q from language classes that are in-between the classes of regular languages and context-free languages, such as unambiguous context-free languages, linear context-free languages, and deterministic context-free languages. We also show that Q satisfies a number of context-free-like conditions, such as the Bar-Hillel lemma, the Ogden condition, the nonempty version of the strong Bader-Moura condition, and strengthened interchange property. In addition, we analyze some less typical (and unsuccessful) attempts of proving non-context-freeness of Q.
09.03.2022 16:15
Pat Morin
Carleton University
Informatyka Teoretyczna
Free Sets in Planar Graphs

A k-vertex set S of vertices in a planar graph G is free if, for any k-point set X, there exists a non-crossing straight-line drawing of G with the vertices of S mapped to the points in X.  In this talk we survey the history and applications of free sets and present two recent results [1,2]:

1. Free sets and collinear sets: If G has any drawing in which all vertices of S appear on a line, then S is a free set.

2. Free sets and dual circumference:  If G has bounded degree, then the size of the largest collinear set in G is proportional to the length of the longest cycle in the dual of G.

[1] Vida Dujmović, Fabrizio Frati, Daniel Gonçalves, Pat Morin, and Günter Rote: Every collinear set in a planar graph is free. Discrete & Computational Geometry, 65:999–1027, 2021.

[2] Vida Dujmovic, Pat Morin: Dual Circumference and Collinear Sets. SoCG 2019: 29:1-29:17.

02.03.2022 16:15
Jarosław Byrka
University of Wrocław
Informatyka Teoretyczna
Online Facility Location with Linear Delay

We study the problem of online facility location with delay. In this problem, a sequence of n clients appear in the metric space, and they need to be eventually connected to some open facility. The clients do not have to be connected immediately, but such a choice comes with a penalty: each client incurs a waiting cost (the difference between its arrival and connection time). At any point in time, an algorithm may decide to open a facility and connect any subset of clients to it. This is a well-studied problem both of its own, and within the general class of network design problems with delays.
Our main focus is on a new variant of this problem, where clients may be connected also to an already open facility, but such action incurs an extra cost: an algorithm pays for waiting of the facility (a cost incurred separately for each such "late" connection). This is reminiscent of online matching with delays, where both sides of the connection incur a waiting cost. We call this variant two-sided delay to differentiate it from the previously studied one-sided delay.
We present an O(1)-competitive deterministic algorithm for the two-sided delay variant. On the technical side, we study a greedy strategy, which grows budgets with increasing waiting delays and opens facilities for subsets of clients once sums of these budgets reach certain thresholds. Our technique is a substantial extension of the approach used by Jain, Mahdian and Saberi [STOC 2002] for analyzing the performance of offline algorithms for facility location.
We then show how to transform our O(1)-competitive algorithm for the two-sided delay variant to O(logn/loglogn)-competitive deterministic algorithm for one-sided delays. We note that all previous online algorithms for problems with delays in general metrics have at least logarithmic ratios.

Joint work with Marcin Bienkowski, Martin Böhm and Jan Marcinkowski

27.01.2022 17:30
Bartosz Podkanowicz
Optymalizacja Kombinatoryczna
Alon Tarsi number of planar graphs

We prove that the Alon-Tarsi number of a planar graph is less or equal to 5. Alon Tarsi number is an important parameter for the graph. It is greater than the choice number and paintability for every graph. We show the modification of the standard argument presented by Carsten Thomassen. We construct a special orientation that doesn't have Euler subgraphs and allows us to reason about the Alon-Tarsi number.

  1. X. Zhu. The Alon-Tarsi number of planar graphs. arXiv:1711.10817. (2017).
  2. Bartosz Podkanowicz. Thomassen orientations. slides. (2022).
27.01.2022 16:45
Jędrzej Kula
Optymalizacja Kombinatoryczna
Bipartite Perfect Matching is in quasi-NC

The class NC represents the problems that have efficient parallel algorithms. In this work, the authors present two algorithms. The first algorithm proves that the perfect matching problem for bipartite graphs is in quasi-NC2. The second algorithm proves that the same problem is in the RNC class and uses only O(log2 n) random bits. Note that a complete derandomization would be achieved when the number of random bits comes down to O(log n).

  1. S. A. Fenner, R. Gurjar, T. Thierauf. Bipartite Perfect Matching is in quasi-NC. arXiv:1601.06319. (2016).
  2. Jędrzej Kula. Bipartite Perfect Matching is in quasi-NC. slides. (2022).
27.01.2022 16:00
Krzysztof Pióro
Optymalizacja Kombinatoryczna
Graph coloring game

In the game coloring game two players are given graph and a set of k colors. Players take turns, coloring properly an uncolored vertex. The goal of the first player is to complete the coloring of the graph, while the other one tries to prevent him from achieving it. The game chromatic number of a graph is the minimum number of colors needed for the first player to win. In this presentation I will show bounds for the game chromatic number for some classes of graphs.

  1. Krzysztof Pióro. Graph Coloring Game. slides. (2022).
26.01.2022 16:15
Sławomir Lasota
University of Warsaw
Informatyka Teoretyczna
Improved Ackermannian lower bound for the reachability problem of vector addition systems
Vector addition systems, equivalent to Petri nets, are an established model of concurrency with widespread applications. The reachability problem, where we ask whether from a given initial configuration there exists a sequence of valid execution steps reaching a given final configuration, is the central algorithmic problem for this model. The complexity of the problem has remained, until recently, one of the hardest open questions in verification of concurrent systems. A first upper bound has been provided only in 2015 by Leroux and Schmitz, then refined by the same authors to Ackermannian upper bound in 2019. The exponential space lower bound, shown by Lipton already in 1976, remained the only known for over 40 years until a breakthrough non-elementary lower bound by Czerwiński et al in 2019. Finally, a matching Ackermannian lower bound announced in 2021 by Czerwiński and Orlikowski, and independently by Leroux, established the complexity of the problem.
 
I will present an improvement of the former construction, making it conceptually simpler and more direct and, on the way, improving the lower bound for vector addition systems  in fixed dimension (or, equivalently, Petri nets with fixed number of places).
26.01.2022 12:15
Jakub Fedak
Podstawy Informatyki
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.

 

20.01.2022 16:00
Szymon Salabura
Optymalizacja Kombinatoryczna
The Hats game. On max degree and diameter

In the Hats game, the sages, located at graph vertices, try to guess colors of their own hats, only seeing colors of hats on sages at the adjacent vertices. If using a deterministic strategy, at least one sage can guess the color of his own hat correctly, we say that the sages win. In this presentation, we consider the hat guessing number - the maximum number of possible colors, for which the sages can guarantee the win. We will see examples of graphs contradicting the previously stated hypothesis, that the hat guessing number is smaller than the graph's maximal degree + 1. We also show its independence from the graph's diameter.

  1. Aleksei Latyshev, Konstantin Kokhas. The Hats game. On max degree and diameter. arXiv:2108.08065. (2021).
  2. Szymon Salabura. The Hats game. On max degree and diameter. slides. (2021).
19.01.2022 16:15
James Davies
University of Waterloo
Informatyka Teoretyczna
Ringel's circle problem

A constellation is a finite collection of circles in the plane in which no three circles are tangent at the same point. In 1959, Ringel asked how many colours are required to colour the circles of a constellation so that tangent circles receive different colours. We present a solution to Ringel's circle problem by constructing constellations that require arbitrarily many colours.

Joint work with Chaya Keller, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak

19.01.2022 12:15
Daniel Barczyk
Podstawy Informatyki
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.

 

13.01.2022 16:45
Jacek Salata
Optymalizacja Kombinatoryczna
Choosability of K5-minor-free graphs

Thomassen showed in 1994 that all planar graphs are 5-choosable and Škrekovski showed in 1998 that all K5-minor-free graphs also are 5-choosable. In this presentation we will take a look at two different proofs of the latter theorem: the Škrekovski's one from the original paper, and the one proposed by Wenjie Hea, Wenjing Miao and Yufa Shenb in 2007.

  1. Wenjie He, Wenjing Miao, Yufa Shen. Another proof of the 5-choosability of -minor-free graphs. Discrete Mathematics. 308(17), 4024-4026. (2008).
  2. Kacek Salata. Choosability of K5-minor-free graphs. slides. (2022).
13.01.2022 16:00
Demian Banakh
Optymalizacja Kombinatoryczna
A relative of Hadwigers conjecture

The well-known open Hadwiger's conjecture asserts that every simple graph G which is not t-colorable has Kt+1 minor. In this presentation, we will take a look at the proof of a relaxed version of this conjecture (in terms of so-called "defective colorings" - i.e. allowing a "small" number of monochromatic edges), as well as see how it can be useful for solving some other graph problems.

  1. Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, Paul Seymour. A relative of Hadwiger's conjecture. arXiv:1407.5236. (2014).
  2. Demian Banakh. A Relative of Hadwiger’s Conjecture. slides. (2022).
12.01.2022 16:15
Grzegorz Gutowski
Informatyka Teoretyczna
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

12.01.2022 12:15
Filip Synowiec
Podstawy Informatyki
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.

 

16.12.2021 16:45
Wojciech Buczek
Optymalizacja Kombinatoryczna
Parking functions: From combinatorics to probability

Let's say m drivers have their favourite parking spot in the linear car park with n spots. Now, in some order, drivers will try to park their car at their favourite spot, and if they fail (because other car is standing there), they will try to park at the next avaible spot. If all drivers could park their car, we call this choices a parking function. In this seminar, we will look at this function proporties, create bijection from them to spanning forests and talk about some conjectures related to parking functions.

  1. Richard Kenyon, Mei Yin. Parking functions: From combinatorics to probability. arXiv 2103.17180. (2021).
  2. Wojciech Buczek. Parking functions. slides. (2021).
16.12.2021 16:00
Rafał Kilar
Optymalizacja Kombinatoryczna
A first moment proof of the Johansson-Molloy Theorem

The paper provides a simple proof of a stronger version of Johansson-Molloy theorem, providing a bound on the list chromatic number of a graph based on maximum degree and neighbouhood density. The new proof only makes use of the first moment method. The counting argument used in the proof is inspired by work by Rosenfeld in the contex of non-repetitive graph coloring. The result is than extended to graphs with neighbourhoods with bounded density, which strengthens previous results. Lastly, the method is adapted to show asymptotically tight lowe bound on the number of colourings of sparse graphs .

  1. François Pirot, Eoin Hurley. Colouring locally sparse graphs with the first moment method. arXiv 2109.15215. (2021).
  2. Rafał Kilar. Colouring locally sparse graphs with the first moment method. slides. (2021).
15.12.2021 16:15
Lars Rohwedder
EPFL
Informatyka Teoretyczna
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.

09.12.2021 16:45
Marcin Serwin
Optymalizacja Kombinatoryczna
Bears with Hats and Independence Polynomials

A hat guessing game consists of a graph and bears assigned to vertices with a certain hat color. Each bear knows the colors of the bears belonging to the neighborhood of their vertex but does not know their own color. The bears win if at least one of them can guess the color of their hat. This presentation will introduce the aforementioned game, its variants and present findings of Václav Blažej, Pavel Dvořák and Michal Opler regarding fractional hat chromatic number of graphs with independence polynomials.

  1. Václav Blažej, Pavel Dvořák, Michal Opler. Bears with Hats and Independence Polynomials. arXiv 2103.07401. 2021.
  2. Marcin Serwin. Bears with Hats and Independence Polynomials. slides. (2021).
09.12.2021 16:00
Krzysztof Potępa
Optymalizacja Kombinatoryczna
Weak degeneracy of graphs

The paper introduces a new graph parameter called "weak degeneracy", a variant of the degeneracy parameter. The authors show various applications of weak degeneracy. For example, it turns out that this new parameter is strongly correlated with graph coloring. Authors derive alternative proofs for several classic upper bounds in graph coloring theory, including 5-list-coloring of planar graphs. My presentation will summarize the findings of the paper.

  1. Anton Bernshteyn, Eugene Lee. Weak degeneracy of graphs. arXiv 2111.05908, (2021).
  2. Krzysztof Potępa. Weak degeneracy of graphs. slides. (2021).
08.12.2021 16:15
István Tomon
ETH Zürich
Informatyka Teoretyczna
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.

08.12.2021 12:15
Katarzyna Król
Podstawy Informatyki
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

 

02.12.2021 16:45
Krzysztof Michalik
Optymalizacja Kombinatoryczna
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 the introduction, we are presented with proof that such constant has to be at least equal to 2, contrary to previous results, where c was bounded by 4/3 and conjectured to be equal to 3/2.

  1. Krzysztof Michalik. Improved Lower Bound For The List Chromatic Number Of Graphs With No Kt Minor. slides. (2021).
02.12.2021 16:00
Krzysztof Ziobro
Optymalizacja Kombinatoryczna
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. Polynomials over structured grids. slides. (2021).
01.12.2021 16:15
Barnaby Martin
Durham University
Informatyka Teoretyczna
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
Podstawy Informatyki
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
Optymalizacja Kombinatoryczna
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
Optymalizacja Kombinatoryczna
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
Informatyka Teoretyczna
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
Podstawy Informatyki
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ś
Optymalizacja Kombinatoryczna
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
Optymalizacja Kombinatoryczna
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.