Seminaria
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 3CNF 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 SheraliAdams, 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.

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 
20.01.2022 16:00 Szymon Salabura 
Optymalizacja Kombinatoryczna The Hats game. On max degree and diameter 
...

20.01.2022 16:45 Bartosz Podkanowicz 
Optymalizacja Kombinatoryczna 2Listcoloring planar graphs without monochromatic triangles 
In 2008 Thomassen showed that it is possible to color planar graph from lists of length two (every vertex have available 2 colors) in such a way that every triangle is colored by at least two colors. In other words, in every triangle, there exist two vertices with different colors. In this presentation, we will show the proof. 
26.01.2022 12:15 Jakub Fedak 
Podstawy Informatyki Exact enumeration of satisfiable 2SAT formulae by Sergey Dovgal, Elie de Panafeu and Vlady Ravelomanana 
We obtain exact expressions counting the satisfiable 2SAT 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 2SAT 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 2SAT phase transition in the future.

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 nonelementary 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). 
27.01.2022 16:45 Jędrzej Kula 
Optymalizacja Kombinatoryczna Bipartite Perfect Matching is in quasiNC 
...

16.03.2022 16:15 Jakub Kozik 
Informatyka Teoretyczna TBA  J.Kozik 
Poprzednie referaty
13.01.2022 16:45 Jacek Salata 
Optymalizacja Kombinatoryczna Choosability of K5minorfree graphs 
Thomassen showed in 1994 that all planar graphs are 5choosable and Škrekovski showed in 1998 that all K_{5}minorfree graphs also are 5choosable. 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. 
13.01.2022 16:00 Demian Banakh 
Optymalizacja Kombinatoryczna A relative of Hadwigers conjecture 
The wellknown open Hadwiger's conjecture asserts that every simple graph G which is not tcolorable has K_{t+1} minor. In this presentation, we will take a look at the proof of a relaxed version of this conjecture (in terms of socalled "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. 
12.01.2022 16:15 Grzegorz Gutowski 
Informatyka Teoretyczna On a problem of Steinhaus 
In this talk, inspired by a "17points" problem of Steinhaus (Problems 6 and 7 from his book "Sto zadań"), we discuss infinite sequences of real numbers in [0,1). 
12.01.2022 12:15 Filip Synowiec 
Podstawy Informatyki On ZeroOne 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 secondorder logic (MSO) have a zeroonelaw – 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 zeroone law for connected planar graphs, and also identified the socalled 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 facewidth 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 zeroone 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. 
16.12.2021 16:00 Rafał Kilar 
Optymalizacja Kombinatoryczna A first moment proof of the JohanssonMolloy Theorem 
The paper provides a simple proof of a stronger version of JohanssonMolloy 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 nonrepetitive 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 . 
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. 
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 5listcoloring of planar graphs. My presentation will summarize the findings of the paper. 
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 signpatterns 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 01 Laws for Maps by Edward A. Bender, Kevin J. Compton,and L. Bruce Richmond 
A class of fnite structures has a 01 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 01 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,

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 K_{t} 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. 
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. 
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 coNPhard, and the borderline is given precisely according to whether A enjoys the polynomiallygenerated powers (PGP) property. This completes the complexity classification problem for QCSPs modulo that coNPhard cases might have complexity rising up to Pspacecomplete. 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 exponentiallygenerated 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 3CNF Formula by Albert Atserias 
We consider the question of certifying unsatisfiability of random 3CNF 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 firstorder logic cannot express any sufficient condition that holds almost surely on random 3CNF 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 3CNF formulas in a new technical way. Moreover, the proof requires us to extend the methods of Shelah and Spencer for proving the zeroone 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. 
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 2uniform. Tuniformity 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 listcolorability. 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. 
25.11.2021 14:15 Miłosz Januszewski, Szymon Salabura 
Algorytmika A FineGrained 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 NPzupeł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 MinPlusConvolution 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 MinPlusConvolution może być rozwiązany w O(n^{c'}) 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 Circulararc graphs and the Helly property 
Circulararc 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 circulararc graphs in which some cliques can be represented by arcs whose common intersection is empty). In particular, some cliques of a circulararc G graph may satisfy the Helly property in some but not all circulararc representations of G. In the Helly Clique Problem, for a given circulararc graph G and some of its cliques C_{1},...,C_{k} (not necessarily maximal in G) one needs to decide whether there exists a circulararc representation of G in which all the cliques C_{1},...,C_{k }satisfy the Helly property. We know that the Helly Clique Problem is NPcomplete and, under the ETH, it can not be solved in time 2^{o(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: Moreover, we will discuss the relation of the Helly Clique Problem with the recognition problems of socalled Hgraphs; 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 lambdacalculus 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. 
18.11.2021 16:00 Karolina Gontarek 
Optymalizacja Kombinatoryczna Growth properties of powerfree 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 powerfree languages with regard to their growth rate. It also describes methods of esimating complexity of powerfree languages paying attention to amount of computer resources needed by special method. Finally, it presents future directions of research in this area. 
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 NPCompleteness”. 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 NPtrudny nawet pod bardzo surowymi restrykcjami, jak na przykład, że graf przecięć jest sumą grafów typu star i alfabet ma rozmiar 
17.11.2021 16:15 Nicolas Bousquet CNRS, Lyon 
Informatyka Teoretyczna 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 Hminor free graph class. We present some generic tools which allow us to certify the Hminorfree graphs (with logarithmic labels) for each small enough H. More generally, we consider classes defined by any MSO formula (i.e. the MSOmodel checking problem), and show a local version of the wellknown 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 
Podstawy Informatyki An Inverse of the Evaluation Functional for Typed λcalculus by U. Berger and Η. Schwichtenberg 
In any model of typed lambdacalculus containing some basic arithmetic, a functional p >e (procedure —> expression) will be defined which inverts the evaluation functional for typed lambdaterms. Combined with the evaluation functional, p>e yields an efficient normalization algorithm. The method is extended to lambdacalculi with constants and is used to normalize (the lambdarepresentations of) natural deduction proofs of (higher order) arithmetic. A consequence of theoretical interest is a strong completeness theorem for \beta \etareduction, generalizing results of Friedman and Statman. If two lambdaterms 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 \etacalculus. 
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 lambdacalculus containing some basic arithmetic, a functional p >e (procedure —> expression) will be defined which inverts the evaluation functional for typed lambdaterms. Combined with the evaluation functional, p>e yields an efficient normalization algorithm. The method is extended to lambdacalculi with constants and is used to normalize (the lambdarepresentations of) natural deduction proofs of (higher order) arithmetic. A consequence of theoretical interest is a strong completeness theorem for \beta \etareduction, generalizing results of Friedman and Statman. If two lambdaterms 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 \etacalculus. 
10.11.2021 16:15 Zdeněk Dvořák Charles University 
Informatyka Teoretyczna On asymptotic dimension of planar and geometric graphs 
A graph class C has asymptotic dimension at most d if for every r, the rth 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 minorclosed 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 
Optymalizacja Kombinatoryczna Problems and results on 3chromatic hypergraphs and some related questions 
Authors in this work aim to establish various bounds and constraints on hypergraphs which are kchromatic. 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 runiform 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 3chromatic 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.

04.11.2021 16:00 Grzegorz Gawryał 
Optymalizacja Kombinatoryczna 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 kstack and kqueue graphs. 
04.11.2021 14:15 Mateusz Pach, Michał Wronka 
Algorytmika Determining 4edgeconnected components in linear time 
Prezentujemy pierwszy deterministyczny algorytm obliczający 4spójne krawędziowo składowe w czasie liniowym. Najpierw pokazujemy algorytm znajdujący wszystkie 3cięcia krawędziowe w danym grafie 3spójnym krawędziowo i korzystając z jego wyniku budujemy 4spójne składowe oryginalnego grafu. 
03.11.2021 16:15 Torsten Mütze University of Warwick & Charles University 
Informatyka Teoretyczna 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 treedepth. They also encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees. We apply the recent HartungHoangMützeWilliams 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 highdimensional 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 2connected. 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 
Podstawy Informatyki On Repetitive Right Application of BTerms by Mirai Ikebuchi and Keisuke Nakano 
Bterms 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 Bterms, that is, whether repetitive right applications of a Bterm cycles or not. We discuss conditions for Bterms to have and not to have the property through a sound and complete equational axiomatization. Specifically, we give examples of Bterms which have the property and show that there are infinitely many Bterms which do not have the property. Also, we introduce a canonical representation of Bterms 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 
Podstawy Informatyki FIXED POINT COMBINATORS AS FIXED POINTS OF HIGHERORDER 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 (higherorder) fixed points. This statement generalizes Statman's conjecture on nonexistence 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 
Informatyka Teoretyczna Universality in minorclosed 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 nvertex subgraph has O(n^{1/2}) treewidth (which implies the LiptonTarjan separator theorem). More generally, for every fixed positive integer t we construct a countable graph that contains every countable K_{t}minorfree 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 EnergyEfficient Algorithm for Maximal Matching in Radio Networks 
20.10.2021 16:15 Bartłomiej Kielak 
Informatyka Teoretyczna 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 
Optymalizacja Kombinatoryczna 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 reconfigurationadjacent 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. 
13.10.2021 16:15 Daniel Kráľ Masaryk University in Brno 
Informatyka Teoretyczna 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 linearsize subhyperghraphs have density at least d contains H. In particular, they raise the questions of determining the uniform Turán densities of K_{4}^{3}, the complete 4vertex 3uniform hypergraph, and K_{4}^{3}, the hypergraph K_{4}^{3} 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 K_{4}^{3} was the only 3uniform hypergraph with nonzero uniform Turán density determined exactly. During the talk, we will present the following two results:
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 
Optymalizacja Kombinatoryczna Open problem session 
Several open problems related to 123 Conjecture are presented. 
06.10.2021 16:15 Virginia Vassilevska Williams MIT 
Informatyka Teoretyczna 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 nbyn matrices can be multiplied asymptotically much faster than the bruteforce O(n^{3}) 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(n^{2.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 
Optymalizacja Kombinatoryczna The Fixing Block Method in Combinatorics on Words 
A word is repetitive if it contains two consecutive identical blocks. A sequence is nonrepetitive up to mod r if each of its mod k (1⩽k⩽r) subsequences is nonrepetitive. Let L be a language of nonrepetitive (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.
(the seminar will only be online) 
17.06.2021 16:15 Wojciech Węgrzynek 
Optymalizacja Kombinatoryczna Nonrepetetive 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 squarefree 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.
(the seminar will only be online) 
16.06.2021 16:15 Krzysztof Turowski 
Informatyka Teoretyczna Degree Distribution of Dynamic Graphs Generated by a DuplicationDivergence 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.

10.06.2021 17:00 Bartosz Wodziński 
Optymalizacja Kombinatoryczna 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.
(the seminar will only be online) 
10.06.2021 16:15 Michał Zwonek 
Optymalizacja Kombinatoryczna Polyomino Tilings 
A polyomino is a subset of R^{2} formed by a strongly connected union of axisaligned unit squares centered at locations on the square lattice Z^{2}. Let T = {T_{1},T_{2},...} be an infinite set of finite simply connected closed sets of R^{2}. 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_{i }∈ 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. (the seminar will only be online) 
09.06.2021 16:15 Paweł Rzążewski Warsaw University of Technology 
Informatyka Teoretyczna 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 Hfree 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
Based on the joint work with Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and with Abrishami, Chudnovsky, and Dibek. 
08.06.2021 09:00 Bartosz Walczak 
Informatyka Teoretyczna 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 straightline segments are replaced by segments in a pseudoline 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: 
02.06.2021 16:15 Marthe Bonamy Université de Bordeaux 
Informatyka Teoretyczna 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 reallife 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 
Optymalizacja Kombinatoryczna Rödl Nibble 
For positive integers r<k<n let m(n,k,r) be the maximal size of a family F of kelement subsets of [n] such that no r vertices lie in more than one A in F. The ErdösHanani 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 kuniform hypergraphs. (the seminar will only be online) 
27.05.2021 16:15 Krzysztof Pióro 
Optymalizacja Kombinatoryczna 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 ddegenerate 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 h_{d} such that every planar graph is (d,h_{d})decomposable. Since every planar graph is 5degenerate, we will consider only the case of d less than 5. (the seminar will only be online) 
26.05.2021 Piotr Kawałek 
Informatyka Teoretyczna Constant depth circuits 
We will overview the stateoftheart 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ś 
Optymalizacja Kombinatoryczna 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 multiagent 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.
(the seminar will only be online) 
20.05.2021 16:15 Wojciech Buczek 
Optymalizacja Kombinatoryczna 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.
(the seminar will only be online) 
19.05.2021 16:15 Paweł Idziak 
Informatyka Teoretyczna 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 NPcomplete 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 
Optymalizacja Kombinatoryczna 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"
(the seminar will only be online) 
12.05.2021 16:15 Grzegorz Gutowski 
Informatyka Teoretyczna Filling blanks in matrices to avoid singularity: progress report 
Given an nbyn 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 
Optymalizacja Kombinatoryczna AanderaaKarpRosenberg conjecture 
The conjecture deals with queries on graph. More concretely given property of a graph (such as connectedness or nonemptiness) 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 nontrivial monotone graph property cannot be determined by a deterministic algorithm with less than n(n1)/2 queries. Such graph properties are called evasive, thus this conjecture is sometimes called evasiveness conjecture. (the seminar will only be online) 
06.05.2021 16:15 Krzysztof Potępa 
Optymalizacja Kombinatoryczna Orienting Fully Dynamic Graphs with WorstCase Time Bounds 
In the edge orientation problem, one is asked to orient edges of a given graph such that the outdegrees 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 outdegree bound and supports updates in O(log n) worstcase time.
(the seminar will only be online) 
05.05.2021 16:15 Louis Esperet Université Grenoble Alpes 
Informatyka Teoretyczna 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:
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 induceduniversal graphs. For isometricuniversal 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 induceduniversal 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 nelement posets (of size 2^{n/4+o(n)}). I will also show how to construct isometricuniversal graphs of size 3^{n+o(n)} for the class of all nvertex 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 
Optymalizacja Kombinatoryczna On triangles in Krminor 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 K_{r}. In the paper 'On triangles in K_{r}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.
(the seminar will only be online) 
28.04.2021 16:15 Daniel Kráľ Masaryk University in Brno 
Informatyka Teoretyczna 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 
Optymalizacja Kombinatoryczna 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 11colorable". The proofing technique from his work has been used in many later papers that show similar bounds for graphs with fixed maximum grades.
(the seminar will only be online) 
21.04.2021 16:15 Paweł Gawrychowski University of Wrocław 
Informatyka Teoretyczna 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 worstcase 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 worstcase 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(n^{2/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 
Optymalizacja Kombinatoryczna 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 (t1)colorable. For low values of t (<7) it was already shown that this claim is actually true. Currently, the bestknown upper bound on the chromatic number of K_{t}minorfree 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 K_{5}minorfree graph is 5choosable.
(the seminar will only be online) 
14.04.2021 16:15 Michał Seweryn 
Informatyka Teoretyczna Dimension of posets with kouterplanar 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 kouterplanar cover graphs. Namely, we show that posets with kouterplanar cover graph have dimension O(k^{3}). As a consequence, we show that every poset with a planar cover graph and height h has dimension O(h^{3}). This improves the previously best known bound of O(h^{6}) by Kozik, Micek and Trotter. Joint work with Maximilian Gorsky 
08.04.2021 16:15 Jędrzej Kula 
Optymalizacja Kombinatoryczna 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.
(the seminar will only be online) 
07.04.2021 16:15 Mikołaj Bojańczyk University of Warsaw 
Informatyka Teoretyczna 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 EilenbergMoore 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 
Informatyka Teoretyczna Local Computation Algorithms for Coloring of Uniform Hypergraphs 
We present a progress on local computation algorithms for two coloring of kuniform hypergraphs. We focus on instances that (for a parameter α) satisfy strengthened assumption of Local Lemma of the form 2^{1α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 
Optymalizacja Kombinatoryczna 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 DushnikMiller concept of dimension, and establishing links between both parameters and structural graph theory, pathwidth and treewidth 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 treewidth of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter. (the seminar will only be online) 
24.03.2021 16:15 Marcin Pilipczuk University of Warsaw 
Informatyka Teoretyczna Recent progress in understanding Hfree 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 NPhardness 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 chibounded 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 quasipolynomialtime 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 ErdosHajnal 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 
Optymalizacja Kombinatoryczna 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) 
 Strona Główna
 Katedra Algorytmiki
 Katedra Podstaw Informatyki
 Wydział Matematyki i Informatyki
 Kontakt
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Galeria
 Ludzie
 Bartłomiej Bosek
 Iwona Cieślik
 Jan Derbisz
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Guśpiel
 Grzegorz Gutowski
 Grzegorz Herman
 Pawel M. Idziak
 Piotr Kawałek
 Marcin Kozik
 Jakub Kozik
 Tomasz Krawczyk
 Jacek Krzaczkowski
 Agnieszka Łupińska
 Marcin Mazur
 Piotr Micek
 Andrzej Pezarski
 Adam Polak
 Michał Seweryn
 Wojciech Szpankowski
 Maciej Ślusarek
 Krzysztof Turowski
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Byli współpracownicy