Seminaria

05.10.2022 16:15
Paul Seymour
Princeton University
Informatyka Teoretyczna
Getting closer to the Erdős-Hajnal conjecture
A general n-vertex graph may not have a clique or stable set larger than O(log n), but excluding an induced subgraph makes a significant difference. The Erdős-Hajnal conjecture (from 1977) says that for every graph H, there exists c such that every H-free graph G (that is, not containing H as an induced subgraph) has a clique or stable set of size at least |G|c. This is still open, and is notoriously intractable.


Erdős and Hajnal proved a general bound: for every H there exists c>0 such that every H-free graph has a clique or stable set of size at least exp(c (log|G|)1/2). This is still the record for most graphs H, but in some instances one can do better. Let us say H is "friendly" if there exists c>0 such that every H-free graph G has a clique or stable set of size at least exp(c (log|G| loglog|G|)1/2). We prove that many graphs are friendly – for instance, all split graphs are friendly, and so is the eight-vertex path, and all graphs obtained from a cograph by adding a new vertex joined arbitrarily.

Joint work with Matija Bucić, Tung Nguyen and Alex Scott

12.10.2022 12:14
Mateusz Olszewski
Podstawy Informatyki
Implicit computation complexity in higher-order programming languages (A Survey in Memory of Martin Hofmann) by Ugo Dal Lago
This paper is meant to be a survey about implicit characterizations of complexity classes by fragments of higher-order programming languages, with a special focus on type systems and subsystems of linear logic. Particular emphasis will be put on Martin Hofmann’s contributions to the subject, which very much helped in shaping the field.
12.10.2022 16:15
Friedrich Eisenbrand
École Polytechnique Fédérale de Lausanne
Informatyka Teoretyczna
TBA - Friedrich Eisenbrand
19.10.2022 12:14
Juliusz Wajgelt
Podstawy Informatyki
Short Proofs of Normalization for the simply-typed λ-calculus, permutative conversions and Godel’s T by Felix Joachimski and Ralph Matthes
Inductive characterizations of the sets of terms, the subset of strongly normalizing terms and normal forms are studied in order to reprove weak and strong normalization for the simply typed λ-calculus and for an extension by sum types with permutative conversions. The analogous treatment of a new system with generalized applications inspired by generalized elimination rules in natural deduction, advocated by von Plato, shows the flexibility of the approach which does not use the strong computability/candidate style `a la Tait and Girard. It
is also shown that the extension of the system with permutative conversions by (\eta) rules is still strongly normalizing, and likewise for an extension of the system of generalized applications by a rule of “immediate simplification”. By introducing an infinitely branching inductive rule the method even extends to Godel’s T
19.10.2022 16:15
Vida Dujmović
University of Ottawa
Informatyka Teoretyczna
TBA - Vida Dujmović
26.10.2022 12:14
Julian Leśniak
Podstawy Informatyki
Tight rank lower bounds for the Sherali–Adams proof system by Stefan Dantchev, Barnaby Martin and Mark Rhodes

We consider a proof (more accurately, refutation) system based on the Sherali–Adams (SA) operator associated with integer linear programming. If F is a CNF contradiction that admits a Resolution refutation of width k and size s, then we prove that the SA rank of F is k and the SA size of F is  \leq (k + 1)s + 1. We establish that the SA rank of both the Pigeonhole Principle PHP_n^{n-1} and the Least Number Principle LNP_n  is n 2. Since the SA refutation system rank simulates the refutation system of Lovász–Schrijver without semidefinite cuts (LS), we obtain as a corollary linear rank lower bounds for both of these principles in LS.

26.10.2022 16:15
Dömötör Pálvölgyi
Eötvös Loránd University
Informatyka Teoretyczna
At most 3.55^n stable matchings

We improve the upper bound for the maximum possible number of stable matchings among n jobs and n applicants (formerly known as n men and n women) from 131072n to 3.55n. To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects.

Joint work with Cory Palmer

02.11.2022 12:14
Aleksander Katan
Podstawy Informatyki
The combinator M and the Mockingbird lattice by Samuele Giraudo
We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator M. This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule Mx_1 x_1x_1. We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on M and that all connected components of its rewrite graph are Hasse diagram of lattices. This last result is based on the introduction of new lattices on duplicative forests, which are sorts of treelike structures. These lattices are not graded, not self-dual, and not semidistributive. We present some enumerative properties of these lattices like the enumeration of their elements, of the edges of their Hasse diagrams, and of their intervals. These results are derived from formal power series on terms and on duplicative forests endowed with particular operations.
02.11.2022 16:15
Jędrzej Hodor
Jagiellonian
Informatyka Teoretyczna
Forcing the wheel in posets with planar cover graph, zero, and large dimension

It is a longstanding open problem if posets with planar cover graph are dim-bounded (meaning that large dimension yields a large standard example as a subposet). We focus on a slightly different problem. Suppose that a poset with planar cover graph has a large standard example as a subposet. Then, how does this standard example look like? We know only few constructions of such posets, namely, Kelly's example and Trotter's wheel. The latter has the property that we can attach a unique minimal element to the poset without violating planarity. We prove that posets with planar cover graph and a unique minimal element that have a large standard example as a subposet, have a large wheel as a subposet. Moreover, as a byproduct, we obtain that such posets' cover graphs have large treewidth.

The results are joint work with W.T.Trotter and heavily rely on the tools introduced by P.Micek, H.C.Smith Blake, and W.T.Trotter in the paper "Boolean dimension and dim-boundedness: Planar cover graph with a zero

09.11.2022 16:15
Wojciech Czerwiński
University of Warsaw
Informatyka Teoretyczna
TBA - Wojciech Czerwiński
16.11.2022 12:14
Michał Sowiński
Podstawy Informatyki
Satisfiability is Decidable for a Fragment of AMSO Logic on Infinite Words by Achim Blumensath, Thomas Colcombet, and Paweł Parys

We prove that satisfiability over infinite words is decidable for a fragment of asymptotic monadic second-order logic. In this fragment we only allow formulae of the form tsr φ(r, s, t), where φ does not use quantifiers over number variables, and variables r and s can be only used simultaneously, in subformulae of the form

$s < f (x) r$.

16.11.2022 16:15

Informatyka Teoretyczna
TBA - 16.11
23.11.2022 12:14
Piotr Kubaty
Podstawy Informatyki
Decision Problems for Second-Order Holonomic Recurrences by Eike Neumann, Joel Ouaknine and James Worrel

We study decision problems for sequences which obey a second-order holonomic recurrence of the form

$f (n + 2) = P (n)f (n + 1) + Q(n)f (n)$

with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P . We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f (1), f (2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones.
 

23.11.2022 16:15
Sophie Spirkl
University of Waterloo
Informatyka Teoretyczna
TBA - Sophie Spirkl
30.11.2022 12:14
Tomasz Buczyński
Podstawy Informatyki
The Variable Containment Problem by Stefan Kahrs

The essentially free variables of a term t in some lambda calculus $FV(t)$ form the set $\{x : \forall t =_{beta} u \rightarrow x\in FV(u) \}. This set is signicant once we consider equivalence classes of \lambda terms rather than \lambda terms themselves as for instance in higher order rewriting. An important problem for (generalised) higher order rewrite systems is the variable containment problem. This property is important when we want to consider $t \rightarrow u$ as a rewrite rule and keep n-step rewriting decidable. Variable containment is in general not implied by $FV(t) \supseteq FV(u)$. We give a decision procedure for the variable containment problem of the second order fragment of $\lambda^\rightarrow$. For full  $\lambda^\rightarrow$ we show the equivalence of variable containment to an open problem in the theory of PCF;  this equivalence also shows that the problem is decidable in the third order case.

30.11.2022 16:15

Informatyka Teoretyczna
TBA - 30.11
07.12.2022 12:14
Katarzyna Król
Podstawy Informatyki
Universal Skolem Sets by Florian Luca, Joel Ouaknine, and James Worrell
It is a longstanding open problem whether there is an algorithm to decide the Skolem Problem for linear recurrence sequences, namely whether a given such sequence has a zero term. In this paper we introduce the notion of a Universal Skolem Set: an infinite subset S of the positive integers such that there is an effective procedure that inputs a linear recurrence sequence u = (u(n))n0 and decides whether u(n) = 0 for some n S . The main technical contribution of the paper is to exhibit such a set
07.12.2022 16:15
László Végh
London School of Economics
Informatyka Teoretyczna
TBA - László Végh
14.12.2022 12:14
Filip Jasiński
Podstawy Informatyki
A Universal Skolem Set of Positive Lower by Density Florian Luca, Joël Ouaknine and James Worrell
The Skolem Problem asks to decide whether a given integer linear recurrence sequence (LRS) has a zero term. Decidability of this problem has been open for many decades, with little progress since the 1980s. Recently, a new approach was initiated via the notion of a Skolem set – a set of positive integers relative to which the Skolem Problem is decidable. More precisely, S is a Skolem set for a class L of integer LRS if there is an effective procedure that, given an LRS in L, decides whether the sequence has a zero in S. A recent work exhibited a Skolem set for the class of all LRS that, while infinite, had density zero. In the present work we construct a Skolem set of positive lower density for the class of simple LRS.
14.12.2022 16:15

Informatyka Teoretyczna
TBA - 14.12
21.12.2022 12:14
Łukasz Grobelczyk
Podstawy Informatyki
Bijections between planar maps and planar linear normal \lambda-terms with connectivity condition by Wenjie Fang
The enumeration of linear λ-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal λ-terms and planar maps, which, when restricted to 2-connected λ-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal λ-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal λ-terms and planar maps, whose restriction to 2-connected λ-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections.
21.12.2022 16:15
Ross Kang
University of Amsterdam
Informatyka Teoretyczna
TBA - Ross Kang
04.01.2023 12:14
Sebastain Spyrzewski
Podstawy Informatyki
A characterization of lambda-terms transforming numerals by PAWEŁ PARYS
It is well known that simply typed λ-terms can be used to represent numbers, as well as some other data types. We show that λ-terms of each fixed (but possibly very complicated) type can be described by a finite piece of information (a set of appropriately defined intersection types) and by a vector of natural numbers. On the one hand, the description is compositional:
having only the finite piece of information for two closed λ-terms M and N, we can determine its counterpart for M N, and a linear transformation that applied to the vectors of numbers for M and N gives us the vector for M N. On the other hand, when a λ-term represents a natural number, then this number is approximated by a number in the vector corresponding to this λ-term. As a consequence, we prove that in a λ-term of a fixed type, we can store only a fixed number of natural numbers, in such a way that they can be extracted using λ-terms. More precisely, while representing k numbers in a closed λ-term of some type, we
only require that there are k closed λ-terms M1, . . . , M k such that M i takes as argument the λ-term representing the k-tuple, and returns the i-th number in the tuple (we do not require that, using λ-calculus, one can construct the representation of the k-tuple out of the k numbers in the tuple). Moreover, the same result holds when we allow that the numbers can be extracted approximately, up to some error (even when we only want to know whether a set is bounded or not). All the results remain true when we allow the Y combinator (recursion) in our λ-terms, as well as uninterpreted constants.
04.01.2023 16:15

Informatyka Teoretyczna
TBA - 04.01
11.01.2023 12:14
Rafał Loska
Podstawy Informatyki
Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study by Olivier Bodini, Antoine Genitrini, Cécile Mailler and Mehdi Naima
In this paper we study two models of labelled random trees that generalise the original unlabelled Schroder tree. Our new models can be seen as models for phylogenetic trees in which nodes represent species and labels encode the order of appearance of these species, and thus the chronology of evolution. One important feature of our trees is that they can be generated
efficiently thanks to a dynamical, recursive construction. Our first model is an increasing tree in the classical sense (labels increase along each branch of the tree and each label appears only once). To better model phylogenetic trees, we relax the rules of labelling by allowing repetitions in the second model. For each of the two models, we provide asymptotic theorems for different characteristics of the tree (e.g. degree of the root, degree distribution, height, etc), thus giving extensive information about the typical shapes of these trees. We also provide efficient algorithms to generate large trees efficiently in the two models. The proofs are based on a combination of analytic combinatorics, probabilistic methods, and bijective methods (we exhibit bijections between our models and well-known models of the literature such as permutations and Stirling numbers of both kinds). It turns out that even though our models are labelled, they can be specified simply in the world of ordinary generating functions. However, the resulting generating functions will be formal. Then, by applying Borel transforms the models will be amenable to techniques of analytic combinatorics.
11.01.2023 16:15

Informatyka Teoretyczna
TBA - 11.01
18.01.2023 12:14
Roman Madej
Podstawy Informatyki
Modular Construction of Fixed Point Combinators and Clocked Bohm Trees by Jorg Endrullis, Dimitri Hendriks and Jan Willem Klop

Fixed point combinators (and their generalization: looping combinators) are classic notions belonging to the heart of λ-calculus and logic. We start with an exploration of the structure of fixed point combinators (fpc’s), vastly generalizing the well-known fact that if Y is an fpc, Y (SI) is again an fpc, generating the B ̈ohm sequence of fpc’s. Using the infinitary λ-calculus we devise infinitely many other generation schemes for fpc’s. In this way we find schemes and building blocks to construct new fpc’s in a modular way. Having created a plethora of new fixed point combinators, the task is to prove that they are indeed new. That is, we have to prove their β-inconvertibility. Known techniques via B ̈ohm Trees do not apply, because all fpc’s have the same Bohm Tree (BT). Therefore, we employ ‘clocked BT’s’, with annotations that convey information of the tempo in which the data in the BT are produced. BT’s are thus enriched with an intrinsic clock behaviour, leading to a refined discrimination method for λ-terms. The corresponding equality is strictly intermediate between =β and =BT, the equality in the classical models of λ-calculus. An analogous approach pertains to L ́evy–Longo and Berarducci trees. Finally, we increase the discrimination power by a precision of the clock notion that we call ‘atomic clock’.


The theory of sage birds (technically called fixed point combinators) is a fascinating and basic part of combinatory logic; we have only scratched the surface.

18.01.2023 16:15

Informatyka Teoretyczna
TBA - 18.01
25.01.2023 16:15

Informatyka Teoretyczna
TBA - 25.01

Poprzednie referaty

15.06.2022 16:15
Piotr Micek
Jagiellonian
Informatyka Teoretyczna
Boolean dimension and dim-boundedness of posets with a unique minimal element whose cover graphs are planar

In 1989, Nešetřil and Pudlák posed the following challenging question: Do planar posets have bounded Boolean dimension?  We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most 13. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of O(log n) bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with O(log2n) bits [Thorup, JACM 2004], and it remains open to determine whether a scheme using labels with O(log n) bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.

Within this talk after a quick introduction, I aim to lay out all the ideas behind the proof bounding Boolean dimension.

This is a joint work with Heather Smith Blake and Tom Trotter.

09.06.2022 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.

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.

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.

02.06.2022 17:00
Krzysztof Pióro
Optymalizacja Kombinatoryczna
Brooks' Theorem via the Alon-Tarsi Theorem

Brooks' Theorem states that every connected graph G with maximum degree d is d-colorable unless G is an odd cycle or a complete graph. It is one of the most famous theorem on graph colorings. In the paper, the author presents yet another proof of this theorem. This proof is based on Alon-Tarsi Theorem and it remains valid in a more general choosability version of Brooks' theorem.

  1. Jan Hladký, Daniel Král’, Uwe Schauz. Brooks’ Theorem via the Alon–Tarsi Theorem. Discrete Mathematics. 310 (23), 3426-3428. (2010).
  2. Krzysztof Pióro. Brooks’ Theorem via the Alon-Tarsi Theorem. slides. (2022).
02.06.2022 16:15
Demian Banakh
Optymalizacja Kombinatoryczna
Separating polynomial χ-boundedness from χ-boundedness

A class of graphs is hereditary χ-bounded if it is closed under taking induced subgraphs and every graph’s chromatic number is bounded by some function of its clique number. A well-known recently stated open question has been whether for every hereditary χ-bounded class that function can be chosen to be a polynomial. We provide a counterexample for it; namely, for any function f, we construct a hereditary χ-bounded class containing graphs of large chromatic number. In particular, for any polynomial f, such a class exists, which answers the aforementioned question negatively.

  1. Marcin Briański, James Davies, Bartosz Walczak. Separating polynomial χ-boundedness from χ-boundedness. arXiv:2201.08814. (2022).
  2. Demian Banakh. Separating polynomial χ-boundedness from χ-boundedness. slides. (2022).
02.06.2022 14:15
Jędrzej Kula, Maciej Nemś
Algorytmika
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

Grafy przecięć geometrycznych to grafy, gdzie wierzchołki odpowiadają figurom geometrycznym w d-wymiarowej przestrzeni euklidesowej. Mogą do to być na przykład kule, kwadraty, hiperkostki. Krawędź między dwoma wierzchołkami istnieje, jeśli dwie figury przecinają się. Jest to typowy sposób modelowania na przykład komunikacji bezprzewodowej.

W pracy autorzy zajmują się obliczaniem średnicy tego typu grafów. Dokładniej rozważają to, czy da się ten problem rozwiązać w czasie poniżej kwadratowym względem liczby wierzchołków. Na referacie zostanie pokazany dowód algorytmu o czasie działania O(n logn) dla sprawdzania, czy średnica jest mniejsza bądź równa 2 dla grafów przecięć kwadratów jednostkowych równoległych do osi. Następnie zostanie pokazane dolne ograniczenie szukania średnicy dla kul jednostkowych na bazie Orthogonal Vectors Hypothesis. Ograniczenie to pokazuje, że nie ma algorytmów pod kwadratowych przy założeniu Orthogonal Vectors Hypothesis.

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.
26.05.2022 17:00
Bartosz Podkanowicz
Optymalizacja Kombinatoryczna
Digraphs are 2-weight choosable

Consider following problem. We are given a digraph. For every edge, there are 2 options to choose a weight for this edge. We want to pick the weights of edges in a specific way. After picking weights we color vertices. The color of the vertex will be the sum of incoming edges minus the sum of outgoing edges from that vertex. We show that it is always possible to choose weights of edges such that the resulting coloring will be proper. This property is called 2-weight-choosability.

  1. Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, Brett Stevens. Digraphs are 2-Weight Choosable. Electronic Journal of Combinatorics. 18(1), P21. (2011).
  2. Bartosz Podkanowicz. Digraphs are 2-weight choosable. slides. (2022).
26.05.2022 16:15
Łukasz Selwa
Optymalizacja Kombinatoryczna
A better lower bound on average degree of 4-list-critical graphs

A graph G is k-list-critical if it is not (k-1)-choosable, but every proper subgraph of G is (k-1)-choosable. We give a new lower bound for the average degree of incomplete k-list-critical graphs and online k-list-critical graphs. The presented bound improves the earlier known lower bounds for k = 4,5,6.

  1. Hal Kierstead, Landon Rabern. Extracting list colorings from large independent sets. arXiv:1512.08130. (2015).
  2. Landon Rabern. A better lower bound on average degree of 4-list-critical graphs. arXiv:1602.08532. (2016).
  3. Łukasz Selwa. A better lower bound on average degree of 4-list-critical graphs. slides. (2022).
26.05.2022 14:15
Grzegorz Gawryał, Rafał Kilar
Algorytmika
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
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.
19.05.2022 17:00
Rafał Kilar
Optymalizacja Kombinatoryczna
Lower Bounds on the On-line Chain Partitioning of Semi-orders with Representation

An online chain partitioning algorithm is presented with one element of a poset at a time and has to assign it to a chain, partitioning the poset. We consider posets with elements represented by unit length intervals. The paper slightly improves the lower bound for the minimum number of chains needed by an online algorithm to partition these posets from ⌊3/2 w⌋ to ⌈3/2 w⌉.

  1. Csaba Biró, Israel R. Curbelo. Improved lower bound on the on-line chain partitioning of semi-orders with representation. arXiv:2111.04790. (2021).
  2. Rafał Kilar. Lower Bounds on the On-line Chain Partitioning of Semi-orders with Representation. slides. (2022).
19.05.2022 16:15
Krzysztof Potępa
Optymalizacja Kombinatoryczna
Unit-Monge matrices and seaweed braids

Simple unit-Monge matrices form a special subclass of square matrices, which can be represented implicitly in linear space by permutations. Somewhat surprisingly, the subclass is closed under distance multiplication. We will show connection between simple unit-Monge matrices and seaweed braids: braids in which each pair of strings crosses at most once. In particular, distance multiplication is equivalent to a "combing procedure", where double-crossings in braid are removed. We will discuss applications of these methods to a few subsequence problems. In particular, the combing procedure can be exploited to obtain an elegant algorithm for all-substring LCS problem.

  1. Alexander Tiskin. Semi-local string comparison: algorithmic techniques and applications. arXiv:0707.3619. (2007).
  2. Krzysztof Potępa. Unit-Monge matrices and seaweed braids. slides. (2022).
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

Nash-Williams theorem (tree-packing theorem) is a classical result due to Nash-Williams (1961) that characterizes graphs with k edge-disjoint spanning trees. In the seminar, I will present a short and elegant proof of the theorem.

  1. Boliong Chen, Makoto Matsumoto, Jianfang Wang, Zhongfu Zhang, Jianxun Zhang. A short proof of Nash-Williams' theorem for the arboricity of a graph. Graphs and Combinatorics, 10 (1). 27-28. (1994).
  2. Jacek Salata. A Short Proof of Nash-Williams' Theorem for the Arboricity of a Graph. slides. (2022).
12.05.2022 16:15
Kamil Galewski
Optymalizacja Kombinatoryczna
Bears with Hats and Independence Polynomials

The hat guessing game is a game in which bears sit in the vertices of an undirected graph. A demon puts hats on the bears' heads. Each hat has one of the h available colors. Each bear sees only the hat colors of his neighbors. The goal of the bears is to guess the color of their hats - each bear has g tries to guess his hat color. The bears win if at least one of them has guessed the color of his hat correctly. This paper describes the relationship between the hat guessing game and the independence polynomial of graphs.

  1. Václav Blažej, Pavel Dvořák, Michal Opler. Bears with Hats and Independence Polynomials. arXiv:2103.07401. (2021).
  2. Kamil Galewski. Bears with Hats and Independence Polynomials. slides. (2022).
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

A contact graph of a ball packing is a graph with non-intersecting balls as vertices and edges between pairs of tangent balls. In the seminar, we will focus on the upper bounds for the average degree of such graphs in any number of dimensions.

  1. Alexey Glazyrin. Contact graphs of ball packings. arXiv:1707.02526. (2017).
  2. Szymon Salabura. Contact Graphs on Ball Packings. slides. (2022).
05.05.2022 16:15
Mateusz Pach
Optymalizacja Kombinatoryczna
Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

It has been conjectured that every planar triangle-free graph G has exponentially many proper vertex-3-colorings. In this paper, the conjecture is disproved. It is also shown that the conjecture holds if we add an assumption about the non-existence of separating cycles of lengths 4 and 5. Specifically, it is proved that the number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2n/17700000.

  1. Carsten Thomassen. Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles. Journal of Combinatorial Theory, Series B. (2021).
  2. Mateusz Pach. Exponentially many 3-colorings of planar graphs with no short separating cycles. slides. (2022).
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

The paper considers two classes of planar graphs: maximal planar graphs and maximal bipartite planar graphs. The authors describe how these graphs can be oriented in the way that each vertex has prescribed indegree. Then the relation of such orientations to specific graph decompositions and orderings on the vertex set is provided. Discussed orientations can be used to characterize some of the planar graphs. Described properties have applications e.g. in graph drawing and planar augmentation problems.

  1. Hubert de Fraysseix, Patrice Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics. 229(1-3). 57-72. (2001).
  2. Karolina Gontarek. On topological aspects of orientations. slides. (2022).
28.04.2022 16:15
Ruslan Yevdokymov
Optymalizacja Kombinatoryczna
Flexible Color Lists in Alon and Tarsi’s Theorem, and Time Scheduling with Unreliable Participants

By describing a winning strategy for Mrs. Correct in the coloring game of Mr. Paint and Mrs. Correct author presents a purely combinatorial proof of a strengthening of Alon and Tarsi's Theorem. Strengthening of the theorem also leads to the strengthening of its applications, for example, upper bounds for list chromatic numbers of bipartite graphs, list chromatic indices of complete graphs, and chess tournament time scheduling problem with unreliable participants.

  1. Uwe Schauz. Flexible Color Lists in Alon and Tarsi's Theorem, and Time Scheduling with Unreliable Participants. Electronic Journal of Combinatorics. 17. R13. (2010).
  2. Ruslan Yevdokymov. Flexible Color Lists in Alon and Tarsi’s Theorem. slides. (2022).
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. On an early paper of Maryam Mirzakhani. 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ś. Avoiding squares over words with lists of size three amongst four symbols. 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.