02.10.2024 14:15
Informatyka Teoretyczna
TBA - 2024.10.02
09.10.2024 14:15
Informatyka Teoretyczna
TBA - 2024.10.09
16.10.2024 14:15
Informatyka Teoretyczna
TBA - 2024.10.16

Poprzednie referaty

13.06.2024 16:00
Łukasz Gniecki
Optymalizacja Kombinatoryczna
The Alon–Tarsi Number of A Toroidal Grid

The Alon–Tarsi number AT(G) of a graph G is the smallest k for which there is an orientation D of G with max outdegree k - 1 such that the number of even and odd circulations in D are different. A toroidal grid T(m, n) is a graph that is a cartesian product of two cycles C(m) and C(n). The authors show that AT(T(m, n)) is equal to 4 when m, n are both odd, and 3 otherwise.

  1. Zhiguo Li, Zeling Shao, Fedor Petrov, Alexey Gordeev. The Alon-Tarsi Number of A Toroidal Grid. arXiv:1912.12466. (2019).
  2. Łukasz Gniecki. slides. (2024).
12.06.2024 16:15
António Girão
University of Oxford
Informatyka Teoretyczna
Induced C_4-free subgraphs with high average degree

A longstanding conjecture from 1983 due to Thomassen states that for all g,k≥2, there exists f(g,k) such that every graph G with average degree at least f(g,k) contains a subgraph with girth at least g and average degree at least k. The first non-trivial case g=5 was resolved in a remarkable paper by Kühn and Osthus in 2004 and since then no further progress has been made. Recently, a second proof of this result was given by Montgomery, Pokrovskiy, and Sudakov, which gives the best bounds currently known. More precisely, they proved that there exists a constant C so that for all k∈ℕ, every graph with average degree at least k(Ck^2) contains a subgraph which is C4-free and has average degree at least k. In this talk based on a joint work with Zach Hunter, I will discuss a recent result namely that for all s,k∈ℕ, every Ks,s-free graph with average degree at least Ck·sCk^4 contains an induced subgraph which is C4-free and has average degree at least k. We use this result as a tool to solve a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, namely that for every H, every graph with average degree at least CH·sC|H|^4 either contains a Ks,s or an induced subdivision of H.

06.06.2024 16:45
Jędrzej Hodor
Optymalizacja Kombinatoryczna
Planarity and dimension

There are various parameters used to measure the complexity of posets (partially ordered sets), and many intriguing questions arise when exploring the relationships between these parameters. Our focus is on the complexity of posets that can be drawn in the plane, analogous to planar graphs. The parameters we discuss include dimension, height, number of minimal elements, and the standard example number. In this talk, I will give a proper introduction to the theory, then present recent developments in this theory, and finally highlight the most exciting open questions in the area.

  1. Jędrzej Hodor. slides. (2024).
05.06.2024 16:15
Maria Chudnovsky
Princeton University
Informatyka Teoretyczna
Anticomplete subgraphs of large treewidth

We will discuss recent progress on the topic of induced subgraphs and tree-decompositions. In particular this talk with focus on the proof of a conjecture of Hajebi that asserts that (if we exclude a few obvious counterexamples) for every integer t, every graph with large enough treewidth contains two anticomplete induced subgraphs each of treewidth at least t.

This is joint work with Sepher Hajebi and Sophie Spirkl.

29.05.2024 16:15
Alexander Wolff
Universität Würzburg
Informatyka Teoretyczna
Eliminating Crossings in Ordered Graphs

Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn without crossings. We study both problems in a book-embedding setting for ordered graphs, that is, graphs with a fixed vertex order. In this setting, the vertices lie on a straight line, called the spine, in the given order, and each edge must be drawn on one of several pages of a book such that every edge has at most a fixed number of crossings. In book embeddings, there is another way to reduce or avoid crossings; namely by using more pages. The minimum number of pages needed to draw an ordered graph without any crossings is its (fixed-vertex-order) page number.

We show that the page number of an ordered graph with n vertices and m edges can be computed in 2m⋅poly(n) time. An O(log n)-approximation of this number can be computed efficiently. We can decide in 2O(d√k⋅log(d+k))⋅poly(n) time whether it suffices to delete k edges of an ordered graph to obtain a d-planar layout (where every edge crosses at most d other edges) on one page. As an additional parameter, we consider the size h of a hitting set, that is, a set of points on the spine such that every edge, seen as an open interval, contains at least one of the points. For h=1, we can efficiently compute the minimum number of edges whose deletion yields fixed-vertex-order page number p. For h>1, we give an XP algorithm with respect to h+p. Finally, we consider spine+t-track drawings, where some but not all vertices lie on the spine. The vertex order on the spine is given; we must map every vertex that does not lie on the spine to one of t tracks, each of which is a straight line on a separate page, parallel to the spine.

Joint work with Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, and Yushi Uno.

16.05.2024 16:45
Rafał Pyzik
Optymalizacja Kombinatoryczna
The Alon-Tarsi number of K3,3-minor-free graphs

For a graph G, denote AT(G) as the Alon-Tarsi number of G. It is known, that if a graph G is planar then AT(G) ≤ 5, AT(G - M)  4 for some matching M in G and AT(G - F)  3 for some forest F in G. Also, by Wagner's theorem, G is planar if and only if it doesn't contain K5 and K3,3 as a minor. We prove these three Alon-Tarsi number bounds for G that is only K3,3-minor-free, strengthening the result for planar graphs.

  1. Leyou Xu, Bo Zhou. The Alon-Tarsi number of K3,3-minor-free graphs. arXiv:2310.07445. (2023).
  2. Rafał Pyzik. slides. (2024).
16.05.2024 16:00
Filip Konieczny
Optymalizacja Kombinatoryczna
Hall's Theorem for hypergraps

Standard Hall's Theorem provides sufficient and necessary condition for a bipartite graph to have a perfect matching. We will formulate and proof generalization of this theorem in hypergraph setting. Interestingly, we make use of Sperner lemma and approach the problem from topological perspective.

  1. Ron Aharoni, Penny Haxell. Hall's theorem for hypergraphs. J. Graph Theory, 35: 83-88. (2000).
  2. Filip Konieczny. slides. (2024).
15.05.2024 16:15
Marta Kwiatkowska
University of Oxford
Informatyka Teoretyczna
Strategy synthesis for partially observable stochastic games with neural perception mechanisms

Strategic reasoning is essential to ensure stable multi-agent coordination in complex environments, as it enables synthesis of optimal (or near-optimal) agent strategies and equilibria that guarantee expected outcomes, even in adversarial scenarios. Partially-observable stochastic games (POSGs) are a natural model for real-world settings involving multiple agents, uncertainty and partial information, but lack practical algorithms for computing or approximating optimal values and strategies. Recently, progress has been made for one-sided POSGs, a subclass of two-agent, zero-sum POSGs where only one agent has partial information while the other agent is assumed to have full knowledge of the state, with heuristic search value iteration (HSVI) proposed for computing approximately optimal values and strategies in one-sided POSGs.

However, many realistic autonomous coordination scenarios involve agents perceiving continuous environments using data-driven observation functions, typically implemented as neural networks (NNs). Such perception mechanisms bring new challenges, notably continuous environments, which are inherently tied to NN-enabled perception because of standard training regimes.

This talk will discuss progress with developing a model class and algorithms for one-sided POSGs with neural perception mechanisms that work directly with their continuous state space. Building on continuous-state POMDPs with NN perception mechanisms, where the key idea is that ReLU neural network classifiers induce a finite decomposition of the continuous environment into polyhedra for each classification label, a piecewise constant representation for the value, reward and perception functions is developed that forms the basis for a variant of HSVI, a point-based solution method that computes a lower and upper bound on the value function from a given belief to compute an (approximately) optimal strategy. We extend these ideas to zero-sum POSGs, which involves solving a normal form game at each stage and iteration, and goes significantly beyond HSVI for finite POSGs.

Based on an invited lecture at CSL 2024


09.05.2024 16:45
Aleksander Katan
Optymalizacja Kombinatoryczna
Dynamic monopolies in directed graphs: The spread of unilateral influence in social networks

Given a digraph G = (V, E), a threshold function t:V→N, and a subset D0 of V, we define the procedure of the influence spread as follows: in turn i, a vertex v joins Di if it either is in Di-1, or has at least t(v) in-neighbors in Di-1. A subset D of V is called a t-dynamic monopoly if there exists a turn j such that D= V. We will discuss the hardness of finding the smallest t-dynamic monopoly when t(v) = 2, as well as prove that every graph admits a t-dynamic monopoly of size |V|/2 when t(v) = ⌈(degin(v)+1)/2⌉.

  1. Kaveh Khoshkhah, Hossein Soltani, Manouchehr Zaker. Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks. arXiv:1212.3682. (2012).
  2. Aleksander Katan. slides. (2024).
09.05.2024 16:00
Ignacy Buczek
Optymalizacja Kombinatoryczna
Flip-width and its basic properties

Some of the recent developments in structural graph theory revolve around the idea of generalizing notions that have proven successful for sparse graphs to more general settings. In that line of work, we present a proposition of a new graph parameter, called flip-width, for which we present strong proof that it could serve as a viable generalization of several notions in the sparsity theory. Most notably, we conjecture it coincides with the class of graphs for which model checking is fixed-parameter tractable.

  1. Jacob Turner. Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited. arXiv:2004.08636. (2020).
  2. Ignacy Buczek. slides. (2024).
08.05.2024 16:15
Michał Pilipczuk
University of Warsaw
Informatyka Teoretyczna
Minor testing in almost linear time

For every fixed graph H, we give an algorithm that given a graph G with m edges, tests whether H is a minor of G in time OH(m1+o(1)). This improves the classic cubic-time algorithm of Robertson and Seymour, and its improvement to quadratic time by Kawarabayashi, Kobayashi, and Reed. By the Graph Minors Theorem, we obtain, as a corollary, an OC(m1+o(1))-time membership test for every minor-closed class of graphs C. Further, the algorithm also works for the rooted version of the problem, so it can be used to solve the Disjoint Paths problem in time Ok(m1+o(1)).

This is a joint work with Tuukka Korhonen and Giannos Stamoulis

25.04.2024 16:45
Sebastian Spyrzewski
Optymalizacja Kombinatoryczna
Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited

It is a very well-known result that the size of maximum matching is equal to the size of a minimum vertex cover. Kőnig’s proof of this fact gave an algorithm for finding a minimum vertex cover from a maximum matching. In this paper, we revisit this algorithm and see how it implies the connection between the two types of structures.

  1. Jacob Turner. Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited. arXiv:2004.08636. (2020).
  2. Sebastian Spyrzewski. slides. (2024).
25.04.2024 16:00
Katarzyna Kępińska
Optymalizacja Kombinatoryczna
Two results on layered pathwidth and linear layouts

In this paper, we study the relations of layered pathwidth to other graph parameters. In particular, we show that the stack number of G is at most 4 times the layered pathwidth of G. The Second result bounds layered pathwidth for graphs with track number at most 3.

  1. Katarzyna Kępińska. slides. (2024).
24.04.2024 16:15
Bartosz Walczak
Jagiellonian University
Informatyka Teoretyczna
Polynomial-time recognition and maximum independent set in Burling graphs
A Burling graph is an induced subgraph of some graph in Burling's construction of triangle-free high-chromatic graphs. Burling graphs can also be characterized as graphs with so-called strict frame representations, i.e., intersection models by suitably restricted rectangular frames. We provide a polynomial-time algorithm which decides whether a given graph is a Burling graph and if it is, constructs its strict frame representation. We also provide a polynomial-time algorithm for the maximum independent set problem in Burling graphs. This establishes Burling graphs as the first known hereditary class of graphs that admits such an algorithm and is not χ-bounded, answering a question of Thomassé, Trotignon, and Vušković.
Joint work with Paweł Rzążewski.
18.04.2024 16:45
Jan Klimczak
Optymalizacja Kombinatoryczna
3-Colorability of 4-Regular Hamiltonian Graphs

It is a well-known result known as the 'cycle-plus-triangles' theorem that every graph on 3n vertices consisting of a Hamiltonian cycle and n node-disjoint triangles is 3-colorable. To improve this result we search for less strict restrictions of G\H. By reduction we show that two following problems are NP-complete: (1) 3-colorability of 4-regular Hamiltonian graphs. (2) 3-colorability of 4-regular Hamiltonian graphs whose inner cycles (connected components after Hamiltonian cycle removal) are non-selfcrossing k-gons.

  1. Jan Klimczak. slides. (2024).
18.04.2024 16:00
Maksym Zub
Optymalizacja Kombinatoryczna
Recisitng Tucker's Algorithm To Color Circular Arc Graphs

The circular arc coloring problem consists of finding a minimum coloring of a circular arc family F such that no two intersecting arcs share a color. Let l be the minimum number of circular arcs in F that are needed to cover the circle. Tucker shows in [SIAM J. Appl. Math., 29 (1975), pp. 493–502], that if l ≥ 4, then ⌊3/2L⌋ colors suffice to color F, where L denotes the load of F. We extend Tucker’s result by showing that if l ≥ 5, then ⌈(L-1)/(L-2)L⌉ colors suffice to color F, and this upper bound is tight.

  1. Mario E. Valencia-Pabon. Revisiting Tucker's Algorithm to Color Circular-Arc Graphs. Electronic Notes in Discrete Mathematics. 7, 198-201. (2001).
  2. Maksym Zub. slides. (2024).
17.04.2024 16:15
Hoang La
Université Paris-Saclay
Informatyka Teoretyczna
Graph reconstruction with connectivity queries

We study a problem of reconstruction of connected graphs where the input gives all subsets of size k that induce a connected subgraph. Originally introduced by Bastide et al. (WG 2023) for triples (k=3), this problem received comprehensive attention in their work, alongside a study by Qi, who provided a complete characterization of graphs uniquely reconstructible via their connected triples, i.e. no other graphs share the same set of connected triples. Our contribution consists in output-polynomial time algorithms that enumerate every triangle-free graph (resp. every graph with bounded maximum degree) that is consistent with a specified set of connected k-sets. Notably, we prove that triangle-free graphs are uniquely reconstructible, while graphs with bounded maximum degree that are consistent with the same k-sets share a substantial common structure, differing only locally. We suspect that the problem is NP-hard in general and provide a NP-hardness proof for a variant where the connectivity is specified for only some k-sets (with k at least 4).

11.04.2024 16:45
Mateusz Hurkała
Optymalizacja Kombinatoryczna
The two possible values of the chromatic number of a random graph

Given d in range (0, ∞) let kd be the smallest integer such that d < 2k log k. We prove that the chromatic number of a random graph G(n,d/n) is either kd or kd+1 almost surely (probability thends to 1 as n approches ). And If d in range (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k+1.

  1. Dimitris Achlioptas, Assaf Naor. The two possible values of the chromatic number of a random graph. arXiv:0706.1725. (2007).
  2. Mateusz Hurkała. slides. (2024).
11.04.2024 16:00
Rafał Kajca
Optymalizacja Kombinatoryczna
Circular-arc graph coloring and unrolling

The register periodic allocation problem is viewed as unrolling and coloring the underlying structure of circular-arc graph. The problem is to find relations between the unrolling degree and the chromatic number. For this purpose we distinguish cyclic colorings that can be found by means of the meeting graph and non-cyclic ones for which we prove the asymptotic property: let r be the width of the original interval family. Then the u-unrolled graph is r or (r+1)-colorable for u large enough.

  1. Christine Eisenbeis, Sylvain Lelait , Bruno P Marmol. Circular-arc Graph Coloring and Unrolling. INRIA. RR-3336, (1998).
  2. Rafał Kajca. slides. (2024).
10.04.2024 16:15
Jean Cardinal
Université Libre de Bruxelles
Informatyka Teoretyczna
A rectangulation is a decomposition of a rectangle into finitely many rectangles

Via natural equivalence relations, rectangulations can be seen as combinatorial objects with a rich structure, with links to lattice congruences, flip graphs, polytopes, lattice paths, Hopf algebras, etc.

I will explain the structure of two equivalence classes: weak rectangulations that preserve rectangle-segment adjacencies, and strong rectangulations that preserve rectangle-rectangle adjacencies.

These equivalences classes are proved to be in correspondence with sets of linear extensions of partial orders on rectangles. This yields a uniform treatment of mappings between permutations and rectangulations, unifying results from earlier contributions. I will also touch upon geometric realizations of the rectangulation polytopes. Just like permutohedra and associahedra encode flip graphs on permutations and triangulations, the skeleta of rectangulation polytopes are flip graphs on rectangulations.

This is joint work with Andrei Asinowski, Stefan Felsner, Éric Fusy, and Vincent Pilaud.

04.04.2024 16:45
Filip Jasionowicz
Optymalizacja Kombinatoryczna
The Lefthanded Local Lemma Characterizes Chordal Dependency Graphs

Shearer characterized the family L of dependency graphs labeled with probabilities such that for every family of events that can be modeled with a graph from L there is a positive probability that none of the events from this family occur. The authors show that unlike the Lovász Local Lemma (which is less powerful than the Shearer's condition on every nonempty graph) a lefthanded variant of LLL is equivalent to Shearer's condition for all chordal graphs. This leads to simple algorithm to determine whether a given label chordal graph is in L.

  1. Wesley Pegden. The Lefthanded Local Lemma characterizes chordal dependency graphs. arXiv:1204.5922. (2012).
  2. Filip Jasionowicz. slides. (2024).
04.04.2024 16:00
Agata Margas
Optymalizacja Kombinatoryczna
Euler circuits and DNA sequencing by hybridization

In the problem of DNA sequencing by hybridization, it is useful to know the number of possible reconstructions of a long DNA string given known short substrings. This number is determined by the pattern of repeated substrings, and in the pattern considered here each substring occurs at most twice. A pairing is a sequence in which each symbol occurs exactly twice, and each pairing induces a 2-in, 2-out graph. We will count the number of pairings of given length, for which the induced graph has exactly k Euler circuits.

  1. Richard Arratia, Béla Bollobás, Don Coppersmith, and Gregory B. Sorkin. Euler circuits and DNA sequencing by hybridization. Discrete Applied Mathematics. 104(1-3), 63-96. (2000).
  2. Agata Margas. slides. (2024).
03.04.2024 16:15
David Conlon
California Institute of Technology
Informatyka Teoretyczna
Additive combinatorics without (much) addition

We describe recent progress on a number of related themes in additive combinatorics, including estimating the clique number of random Cayley graphs and showing that there are Cayley graphs which are good Ramsey graphs. Surprisingly, the proofs of these results rely only weakly on the group structure and the proofs are mainly about the structure of properly edge-coloured graphs.

Joint work with Jacob Fox, Huy Tuan Pham and Liana Yepremyan.

27.03.2024 16:15
Clément Rambaud
Université Côte d'Azur
Informatyka Teoretyczna
Inversions in oriented graphs

The inversion of a set X of vertices in an oriented graph consists in reversing the direction of all arcs of the subdigraph induced by X. This generalization of single arc reversal introduced by Belkhechine et al. yields a notion of distance between orientations of a same graph where two orientations are at distance one if and only if there is a set X whose inversion transforms one into the other. First we will discuss the minimum number of inversions required to make an oriented graph acyclic, and in particular a proof of the existence of n-vertex oriented graphs at distance n-o(n) of any acyclic orientation. We also investigate the minimum number of inversions needed to make an oriented graph k-strongly-connected, especially in the case of tournaments. Finally, we show various bounds on the maximum distance between two orientations of a same graph. This gives an undirected graph parameter that we show to be tied to several known parameters, including the star chromatic number and acyclic chromatic number. We also prove that two orientations of a same planar graph are at distance at most 12. Most of these results rely on an algebraic point of view that allows us to use linear algebra over the field with two elements.

This is joint work with Guillaume Aubian, Julien Duron, Frédéric Havet, Florian Horsch, Felix Klingelhoefer, Nicolas Nisse, and Quentin Vermande.

21.03.2024 16:45
Kamil Galewski
Optymalizacja Kombinatoryczna
Shannon Entropy of Ramsey Graphs with up to Six Vertices

The Ramsey theorem asserts that for sufficiently large complete graphs, where edges are colored with a fixed number of colors, there must exist a monochromatic clique of a predetermined size. In this presentation, I will introduce a method for computing the Shannon entropy of bi-colored Ramsey complete graphs, demonstrated through examples of graphs containing up to six vertices.

  1. Mark Frenkel, Shraga Shoval, and Edward Bormashenko. Shannon Entropy of Ramsey Graphs with up to Six Vertices. Entropy. 25(10). 1427. (2023).
  2. Kamil Galewski. slides. (2024).
21.03.2024 16:00
Piotr Kaliciak
Optymalizacja Kombinatoryczna
An algorithm for identifying cycle-plus-triangles graphs

A cycle-plus-triangle graph is a union of node-disjoint triangles and a Hamiltonian cycle. It is known that such graphs are 3-colorable, but the problem of finding any 3-coloring is still open. The authors show a polynomial time algorithm for deciding if a given graph is cycle-plus-triangle, and if this is the case, the algorithm provides the decomposition into the triangles and a cycle.

  1. Kristóf Bérczi, Yusuke Kobayashi. An algorithm for identifying cycle-plus-triangles graphs. Discrete Applied Mathematics. 226. 10-16. (2017).
  2. Piotr Kaliciak. slides. (2024).
20.03.2024 16:15
Gábor Tardos
Alfréd Rényi Institute of Mathematics
Informatyka Teoretyczna
Forbidden acyclic patterns in 0-1 matrices
A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal function of A, denoted ex(n,A), is the maximum number of 1-entries that an n×n zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Füredi and Hajnal from 1992. The field has many connections to other areas such as classical Turán type extremal graph theory and Davenport-Schinzel theory and has many applications in mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices. Füredi and Hajnal conjectured an O(n·log n) bound for them, while Pach and Tardos conjectured a weaker n·polylog n bound. Pettie refuted the stronger conjecture with an acyclic pattern whose extremal function he showed to be Ω(n·log n · loglog n).
In a recent joint work with Seth Pettie we found the extremal function ex(n,Ak) asymptotically for certain simple 2×k acyclic patterns to be Θ(n·(log n/loglog n)k−2) for k>3. This shows that the Pach-Tardos conjecture is tight if true. The conjecture itself is still wide open.
14.03.2024 16:45
Michał Mizołek
Optymalizacja Kombinatoryczna
An O(n^2) algorithm for coloring proper circular arc graphs

A graph qualifies as a circular arc graph when every node corresponds to an arc on a circle, with adjacency between any two nodes depending on the overlapping of their respective arcs. For a circular arc graph to be considered proper, it requires to be characterized by the unique property that no arc fully encloses another within its bounds. The paper introduce an efficient algorithm with a quadratic time complexity, designed to evaluate the colorability of these graphs, addressing the challenge of assigning k distinct colors to a graph with n vertices without violating adjacency constraints. The significance of this work lies in its contribution to graph theory, providing a an approach to understanding the structural properties of proper circular arc graphs and their implications for graph coloring problems.

  1. James B. Orlin, Maurizio A. Bonuccelli, and Daniel P. Bovet. An O(n2) Algorithm for Coloring Proper Circular Arc Graphs. SIAM Journal on Algebraic Discrete Methods. 2(2). 88-93. (1981).
  2. Michał Mizołek. slides. (2024).
14.03.2024 16:00
Maciej Sanocki
Optymalizacja Kombinatoryczna
Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching

The online bipartite matching problem focuses on finding a matching of the greatest cardinality for the bipartite graph, while vertices and their sets of edges from the „right side” are revealed one by one. The algorithm has to decide on, which edge to include in matching immediately upon the arrival. This paper shows, yet again, a proof for 1-1/e competitiveness of RANKING algorithm for the online bipartite matching problem. This time however, the proof is via a randomised primal-dual argument.

  1. Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for On-line Bipartite Matching. STOC 1990. 352-358. (1990).
  2. Maciej Sanocki. slides. (2024).
07.03.2024 16:00
Bartłomiej Błoniarz
Optymalizacja Kombinatoryczna
Cooperative colorings of trees and of bipartite graphs

In a system of graphs (G1, ..., Gm) sharing the same set of vertices (V), a cooperative coloring involves selecting vertex sets (I1, ..., Im) where each Ij is independent in Gj, and the union of all sets equals V. For a graph class C and integer d we are concerned with the minimum m, such that every m graphs in this class with maximum degree d, can be cooperatively colored. The paper shows bounds on the value of m for trees and bipartite graphs.

  1. Ron Aharoni, Eli Berger, Maria Chudnovsky, Frédéric Havet, Zilin Jiang. Cooperative colorings of trees and of bipartite graphs. arXiv:1806.06267. (2018).
  2. Bartłomiej Błoniarz. slides. (2024).
06.03.2024 16:15
Jacob Fox
Stanford University
Informatyka Teoretyczna
Structure theorems for intersection patterns of geometric objects

In this talk we discuss Szemerédi-type structure theorems, Ramsey-type theorems, and Turán-type theorems for intersection patterns of geometric objects and their relationships to each other. In particular, we discuss recent such results on intersection graphs of pseudo-segments and an application which gives a new upper bound on the number of edges of a simple topological graph with no k pairwise disjoint edges.

Joint work with János Pach and Andrew Suk.

29.02.2024 16:00
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Some open problems from combinatorics and algorithmics

Some open problems and the latest results regarding majority coloring are presented. In addition, hypotheses were put forward regarding the hat guessing number.

25.01.2024 17:30
Filip Jasionowicz
Optymalizacja Kombinatoryczna
Four Pages Are Indeed Necessary for Planar Graphs

An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. Accordingly, the book thickness of a class of graphs is the maximum book thickness over all its members. In this paper, we address a long-standing open problem regarding the exact book thickness of the class of planar graphs, which previously was known to be either three or four. We settle this problem by demonstrating planar graphs that require four pages in any of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.

  1. Michael A. Bekos, Michael Kaufmann, Fabian Klute, Sergey Pupyrev, Chrysanthi Raftopoulou, Torsten Ueckerdt. Four Pages Are Indeed Necessary for Planar Graphs. arXiv:2004.07630. (2020).
  2. Filip Jasionowicz. Book embeddings of graphs and why four pages are indeed necessary for planar graphs. slides. (2024).
25.01.2024 16:45
Artemy Oueiski
Optymalizacja Kombinatoryczna
A simple linear time algorithm for cograph recognition

Cographs are precisely the P4-free graphs. It is shown that a cograph can be uniquely represented by a special tree, called a cotree, where the leaves of the cotree correspond to the vertices of the cograph. An algorithm for recognizing cographs is considered, operating in linear time through two steps. In the first step partition refinement is used to create a factorizing permutation. At the second step, the permutation is tested to verify whether the graph is a cograph. Then algorithms for deriving the characteristics (pathwidth, treewidth, number of cliques) of a cograph from its cotree are explored.

  1. D.G. Corneil, H. Lerchs, L.Stewart Burlingham. Complement reducible graphs. Discrete Applied Mathematics. 3(3), 163-174. (1981).
  2. Hans L. Bodlaender and Rolf H. Möhring. The Pathwidth and Treewidth of Cographs. SIAM Journal on Discrete Mathematics. 6(2). 181-188. (1993).
  3. Artemy Oueiski. A simple linear time algorithm for cograph recognition. slides. (2024).
25.01.2024 16:00
Katzper Michno
Optymalizacja Kombinatoryczna
Another approach to non-repetitive colorings of graphs of bounded degree

A non-repetitive graph coloring (of vertices or edges) is a coloring such that all sequences of colors induced by paths in the graph are non-repetitive (square-free), which means that they do not contain any consecutive subsequence that is a square. The non-repetitive number of a graph is the minimal number of colors in a non-repetitive vertex coloring (resp. non-repetitive index for coloring edges). There are also list counterparts of these numbers. Many maximal degree related upper bounds for non-repetitive number (resp. index) have been established commonly using the Lovász Local Lemma or entropy compression method. The author of this paper introduces another method of proving these bounds, which is closely related to the entropy compression method, but generates simpler and more elementary proofs. The author provides some minor improvements to non-repetitive number in several cases and matches some of already known bounds using the new technique.

  1. Matthieu Rosenfeld. Another approach to non-repetitive colorings of graphs of bounded degree. arXiv:2006.09094. (2020).
  2. Katzper Michno. Another approach to non-repetitive colorings of graphs of bounded degree. slides. (2024).
24.01.2024 16:15
Sergio Cabello
University of Ljubljana and IMFM, Slovenia
Informatyka Teoretyczna
Packing d-dimensional balls into a (d+1)-dimensional container

We consider the problems of finding in d+1 dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of d-dimensional unit-radius balls can be packed under translations. We give a constant-factor approximation algorithm for each of these containers. We also show that for n such balls, a container of volume O(n1−1/d) is always sufficient and sometimes necessary.

Joint work with Helmut Alt, Otfried Cheong, Ji-won Park and Nadja Seiferth.

18.01.2024 16:45
Milana Kananovich
Optymalizacja Kombinatoryczna
A Linear Recognition Algorithm for Cographs. A Simple Linear Time LexBFS Cograph Recognition Algorithm.

Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are undirected graphs with no induced paths on four vertices. Cographs have a unique tree representation called a cotree. We consider two linear time algorithms for recognizing cographs and constructing their cotree representation (or the reason why it is not a cograph, the 2nd algorithm gives us P4): a step-by-step recognition algorithm (where we have a list of conditions that must not be violated for the cograph) and LexBFS recognition algorithm (it uses a LexBFS approach, and introduces a new variant of LexBFS, operating on the complement of the given graph G and breaking ties concerning an initial LexBFS).

  1. D. G. Corneil, Y. Perl, and L. K. Stewart. A Linear Recognition Algorithm for Cographs. SIAM Journal on Computing. 14(4). 926-934. (1985).
  2. Anna Bretscher, Derek Corneil, Michel Habib, and Christophe Paul. A Simple Linear Time LexBFS Cograph Recognition Algorithm. SIAM Journal on Discrete Mathematics. 22(4). 1277-1296. (2008).
  3. Milana Kananovich. Cograph Recognition. slides. (2024).
18.01.2024 16:00
Sebastian Spyrzewski
Optymalizacja Kombinatoryczna
List coloring with requests

In this paper we consider the problem of L-coloring graph G with the given list assignment L, but with additional requests giving the preferred color of some vertices. We ask a question of how many of these preferences can be respected while L-coloring G. We present a connection between weighted and unweighted requests and show that for degenerate graphs there is always a constant fraction of preferences that can be satisfied.

  1. Zdeněk Dvořák, Sergey Norin, Luke Postle. List coloring with requests. arXiv:1612.08698. (2016).
  2. Sebastian Spyrzewski. List coloring with requests. slides. (2024).
17.01.2024 16:15
Jim Geelen
University of Waterloo
Informatyka Teoretyczna
Average plane size

Consider a finite set of distinct points in d-dimensional Euclidean space. A line is said to be spanned if it contains two distinct points from the given set, and a plane is spanned if it contains three non-collinear points from the given set. In 1941, Melchior proved that the average number of given points on a spanned line is bounded above by 3, unless the given points all lie on a single line. We prove that the average number of given points on a spanned plane is bounded above by an absolute constant, unless all of the given points lie on a single plane or they lie on the union of two lines.

This is joint work with Rutger Campbell and Matthew Kroeker.

11.01.2024 16:45
Aleksander Katan
Optymalizacja Kombinatoryczna
Countable graphs are majority 3-choosable

A majority coloring of a graph is a vertex coloring in which for each vertex there are at least as many bichromatic edges containing that vertex as monochromatic ones. The Unfriendly Partition Conjecture states that every countable graph admits a majority 2-coloring. It is known that for every (not necessarily countable) graph a majority 3-coloring always exists. Anholcer, Bosek, and Grytczuk have recently proven that every countable graph is majority 4-choosable, and we will see an improvement of this result to lists of size 3, as well as a simplified version of the proof that countable graphs are 3-colorable.

  1. John Haslegrave. Countable graphs are majority 3-choosable. arXiv:2003.10408. (2020).
  2. Aleksander Katan. Countable graphs are majority 3-choosable. slides. (2024).
11.01.2024 16:00
Łukasz Gniecki
Optymalizacja Kombinatoryczna
The Alon Tarsi Number of Planar Graphs - a Simple Proof

The Alon-Tarsi number of a Graph, AT(G), is a value defined by considering eulerian subsets of edges of a chosen orientation of the graph. It has many connections to the domain of graph coloring. For example, the choice number of a graph, ch(G), is bounded by the Alon-Tarsi number, AT(G). In this paper, we will see a simple proof, in the style of Thomassen's induction, of the statement that for any planar graph G, AT(G) is at most 5. Alongside, we will see that any planar G has a matching M, such that AT(G - M) is at most 4.

  1. Yangyan Gu, Xuding Zhu. The Alon-Tarsi number of planar graphs - a simple proof. arXiv:2203.16308. (2022).
  2. Łukasz Gniecki. The Alon Tarsi Number of Planar Graphs - a Simple Proof. slides. (2024).
10.01.2024 16:15
Peter Allen
London School of Economics and Political Science
Informatyka Teoretyczna
Universality for degenerate graphs

A graph G is universal for a family of graphs if for each F in  there is a copy of F in G (not necessarily induced, and the copies are not necessarily disjoint).

Alon and Capalbo considered the case that is the family of n-vertex graphs with maximum degree k, and showed that there is a universal graph for this family with O(n2-2/k) edges, which is sharp. Alon asked what the answer is if one replaces 'maximum degree' with 'degeneracy'.

We give a probabilistic construction of a universal graph for the family of n-vertex d-degenerate graphs with Õ(n2-1/d) edges, which is optimal up to the polylog. In this talk, I will describe the construction and give most of the details of the proof of its universality.

This is joint work with Julia Boettcher and Anita Liebenau.

21.12.2023 16:45
Kamil Galewski
Optymalizacja Kombinatoryczna
On two generalizations of the Alon–Tarsi polynomial method

The Alon-Tarsi number of a graph G=([n], E) is the smallest integer k, such that there exists a monomial x1d1x2d2...xndn in the expansion of the graph polynomial of G having non-zero coefficient and satisfying d< k for all i∈[n]. Using Combinatorial Nullstellensatz, one can show that this number is an upper bound on the choice number of the graph (and thus on its chromatic number). Alon and Tarsi presented a way of checking non-zeroness of the coefficient of the monomial x1d1...xndn in case di = outdegD(i) for some orientation D of graph G - it is sufficient to check whether the difference between the number of the odd and even Eulerian suborientations of D is non-zero. In this presentation, I will show a generalization of this result - for each D, there exists an infinite family of functions f mapping suborientations of D to real numbers, such that the coefficient mentioned above is non-zero iff the sum of f(A) over all the suborientations A of D is non-zero.

  1. Dan Hefetz. On two generalizations of the Alon-Tarsi polynomial method. arXiv:0911.2099. (2009).
  2. Kamil Galewski. Generalizations of the Alon-Tarsi polynomial method. slides. (2023).
21.12.2023 16:00
Ignacy Buczek
Optymalizacja Kombinatoryczna
A note on computer-assisted proofs in flag algebras

With the help of CSDP solvers, one can use computer assistance to obtain correct proofs in flag algebras. In the most common implementations, the programs return the best possible bound on the objective function, together with some information on the extremal graphon. However, for more complicated graphons, this information is usually insufficient to fully retrieve the extremal graphon. We present how one can gather more information on the extremal graphon by adding temporary assumptions to the program, using a non-trivial example that we stumbled upon in our unpublished work on balanced bipartitions of K4-free graphs.

  1. Ignacy Buczek. A note on computer-assisted proofs in flag algebras. slides. (2023).
20.12.2023 16:15
Paweł Rzążewski
Warsaw University of Technology
Informatyka Teoretyczna
Understanding graphs with no long claws

A classic result of Alekseev asserts that for connected H the MAX INDEPENDENT SET (MIS) problem in H-free graphs in NP-hard unless H is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in Pt-free graphs. The situation for forbidden subdivided claws is, however, much less understood.

During the talk we will present some recent advances in understanding the structure of graphs with no long induced claws. We are able to use them to obtain a quasipolynomial-time algorithm for the problem.

14.12.2023 16:00
Jędrzej Hodor
Optymalizacja Kombinatoryczna
Wythoff's game

Consider an n×m chessboard with a single queen placed somewhere. There are two players and in order to win, one has to place the queen in the left-bottom corner. A player can either move the queen diagonally towards the left-bottom or vertically towards the left or bottom. It turns out that sometimes the first player has a winning strategy and sometimes the second player. The characterization is mathematically beautiful. The first player has a winning strategy if and only if there is a non-negative integer n such that the queen starts in the position (⌊nφ⌋, ⌊nφ2⌋), where φ is the golden ratio.

  1. W. A. Wythoff. A modification of the game of nim. Nieuw Archief voor Wiskunde. 2(7). 199-202. (1907).
  2. Jędrzej Hodor. Wythoff’s game. slides. (2023).
13.12.2023 00:00

Informatyka Teoretyczna
The 17th workshop on Computational Logic and Applications
07.12.2023 16:00
Piotr Kaliciak
Optymalizacja Kombinatoryczna
Hat guessing numbers of strongly degenerate graphs

Consider a game with n players, each placed on one of the vertices of graph G. Each player is given a hat, but they cannot see their hat color; they can only see the colors of the hats worn by their neighbors in G. The objective for the players is to ensure that at least one player correctly guesses the color of their hat. The hat guessing number of graph G, denoted by HG(G), is the maximum number of colors for which the players possess a winning strategy. We present an upper bound for the hat guessing number of d-degenerate and outerplanar graphs.

  1. Charlotte Knierim, Anders Martinsson, Raphael Steiner. Hat guessing numbers of strongly degenerate graphs. arXiv:2112.09619. (2021).
  2. Piotr Kaliciak. Hat guessing numbers of strongly degenerate graphs. slides. (2023).
06.12.2023 16:15
Paul Bastide
LaBRI, Bordeaux
Informatyka Teoretyczna
Skipless chain decompositions and improved poset saturation bounds

We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k (as induced subposet), but adding any set to F creates an antichain of size k. We use sat*(n,k) to denote the smallest size of such a family. With more work we pinpoint the exact value of sat*(n,k), for all k and sufficiently large n. Previously, exact values for sat*(n,k) were only known for k up to 6.

We also show that for any poset P, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: sat*(n,P)=O(nc), where c|P|2/4+1.

This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

30.11.2023 16:45
Jan Klimczak
Optymalizacja Kombinatoryczna
On the equitable distribution of points on the circle

The stick-breaking problem is equivalent to the online resource allocation problem, where we possess one unit of resource and we want to fairly distribute fractions of it between people, whose number is unknown at the beginning and upon person's arrival we are only allowed to decrease the share of resource of one person and transfer it to the newcomer. We present various solutions to this problem and analyze their efficiency.

  1. Hamza B. Habib. On the equitable distribution of points on the circle. MSc thesis. University of Wollongong. (2014).
  2. Jan Klimczak. On the equitable distribution of points on the circle. slides. (2023).
30.11.2023 16:00
Rafał Pyzik
Optymalizacja Kombinatoryczna
Online Algorithms for Maximum Cardinality Matching with Edge Arrivals

In the edge arrival model for the online maximum matching problem, edges are sequentially presented and each of them is accepted for the final matching or discarded. We present the Min-Index framework - a family of randomized algorithms for this problem. Using this framework, we show a 5/9-competitive algorithm when the graph is a tree. Moreover, we show that any algorithm in the edge arrival model is at most 0.5914 competitive.

  1. Niv Buchbinder, D. Segev, Yevgeny Tkach. Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. Algorithmica. 81, 1781-1799. (2019)
  2. Rafał Pyzik. Online Algorithms for Maximum Cardinality Matching with Edge Arrivals slides. (2023).
29.11.2023 16:15
Matthieu Rosenfeld
LIRMM, Montpellier
Informatyka Teoretyczna
A simple counting argument applied to graph colorings

The Lovász Local Lemma is one of the central tools of Erdős' probabilistic method. This rather simple lemma has been applied to SAT formulas, graph colorings, hypergraph coloring, combinatorics on words, geometry, and countless other topics. This Lemma essentially tells that given a set of "bad events", under the right conditions, the probability that no events occur is nonzero. It implies the existence of a coloring or an affection of the variables with the desired properties. There are many versions of the Lovász Local Lemma that apply to different situations. Many related techniques that apply to similar problems have emerged in the last 20 years (entropy compression, cluster expansion, local cut lemma...). Recently, I have introduced a counting argument that belongs to the same family of technique. The main interest of this counting argument is that it is really simple to use and it has already been applied to different problems by a few different authors.

In this presentation, I will present this counting argument. We will apply this technique to one or two simple examples from graph theory to illustrate how it works. I will try to give a broad intuition behind a couple of more involved results that were achieved by different authors with this technique.

23.11.2023 16:45
Izabela Tylek
Optymalizacja Kombinatoryczna
Any 7-chromatic graph has a K7 or K4,4 as a minor

One of perhaps the most important and interesting unsolved problems in the field of graph theory is the Hadwiger conjecture, which states that every k-chromatic graph has a Kk-minor. It has been proven to be true for k≤6; the cases k=5 and k=6 have been shown to be equivalent to the four-color theorem. The conjecture remains unsolved for k≥7, but some partial results are known. We will look closer at one of them, showing that any 7-chromatic graph has a K7 or K4,4 as a minor.

  1. Izabela Tylek. Any 7-chromatic graph has K7 or K4,4 as a minor. slides. (2023).
23.11.2023 16:00
Justyna Jaworska
Optymalizacja Kombinatoryczna
An O(n√n) algorithm to color proper circular arcs

A proper circular arc family F is a set of arcs on a circle such that no arc is contained within another. We consider incidence graphs for such arc families. On proper circular-arc graphs, the coloring problem is polynomially solvable, most recently, in O(n1.5 log n) time (Teng and Tucker). It's due to the fact that the (q-colorability) problem can be reduced to a shortest path problem. In this note, we improve Teng and Tucker’s algorithm obtaining O(n1.5) running time.

  1. Wei-Kuan Shih, Wen-Lian Hsu. An O(n1.5) algorithm to color proper circular arcs. Discrete Applied Mathematics. 25(3), 321-323. (1989).
  2. Justyna Jaworska. An O(n1.5) algorithm to color proper circular arcs. slides. (2023).
22.11.2023 16:15
Gábor Damásdi
Alfréd Rényi Institute of Mathematics
Informatyka Teoretyczna
Monochromatic configurations on the circle

In this lecture we will discuss a surprising combinatorial conjecture. For  k≥3 call a k-tuple (d1,d2,...,dk)  with  d1d2≥...≥dk>0  and d1+d2+...+dk=1   a Ramsey k-tuple if the following is true: in every two-colouring of the circle of unit perimeter, there is a monochromatic k-tuple of points in which the distances of cyclically consecutive points, measured along the arcs, are d1,d2,...,dk in some order. By a conjecture of Stromquist, if  di=2k-i/(2k-1),  then d1,d2,...,dk is Ramsey. Using Sat solvers we showed that the conjecture holds for k7. Our main result is a proof of the converse of this conjecture. That is, we show that if (d1,d2,...,dk) is Ramsey, then di=2k-i/(2k-1). We do this by finding connections of the problem to certain questions from number theory about partitioning N into so-called Beatty sequences.


16.11.2023 16:45
Maciej Sanocki
Optymalizacja Kombinatoryczna
Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm

In the original setting of online bipartite matching, vertices from only one side of the bipartite graph are online. This time however we will focus on generalization, in which all vertices can be online. An algorithm for it should maintain a b-matching and try to maximize its size. We show that this problem can be attacked by considering the complementary “dual” problem, a two-sided online bipartite vertex cover.

  1. Maciej Sanocki. Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm. slides. (2023).
16.11.2023 16:00
Katarzyna Kępińska
Optymalizacja Kombinatoryczna
On Two problems of Defective Choosability of Graphs

Graph G is (k,d,p)-choosable if given list assignment L where |L(v)| is at least k for each vertex v and the number of all available colors is p, there exists L-coloring such that maximum degree of monochromatic subgraph is at most d. This paper shows two constructions of graphs: 1-defective 3-choosable that are not 4-choosable and (k,d,l)-choosable that are not (k,d,l+1)-choosable.

  1. Katarzyna Kępińska. On Two problems of Defective Choosability of Graphs. slides. (2023).
15.11.2023 16:15
Piotr Micek
Informatyka Teoretyczna
Tight bound for the Erdős-Pósa property of tree minors

Let T be a tree on t vertices. We prove that for every positive integer k and every graph G, either G contains k pairwise vertex-disjoint subgraphs each having a T minor, or there exists a set X of at most t(k-1) vertices of G such that  G-X has no T minor. The bound on the size of X is best  possible and improves on an earlier f(t)k bound proved by Fiorini, Joret, and Wood (2013) with some very fast growing function f(t). Our proof is moreover very short and simple.

Joint work with Vida Dujmović, Gwenaël Joret, and Pat Morin

09.11.2023 16:00
Karolina Okrasa
Warsaw University of Technology
Optymalizacja Kombinatoryczna
Graph Homomorphisms: From Structure to Algorithms

For two graphs G and H, a homomorphism from G to H is a function that maps the vertices of G to the vertices of H in a way that edges are preserved. Graph homomorphisms are a generalization of graph colorings: if H is a complete graph on k vertices, then homomorphisms from G to H are precisely the k-colorings of G and vice versa.

It seems natural to follow the lines of research for the coloring problem to study the more general homomorphism problem. In the talk, I will focus on determining the complexity of the homomorphism problem (and its list variant) when we assume the class of input instances is somehow restricted, e.g., by bounding some structural parameter of an instance, or excluding the instances that contain some fixed graph as an induced subgraph. We examine to which extent the variety of tools developed to work on coloring problems can be applied, and show more general methods to approach these problems.

08.11.2023 16:15
Torsten Ueckerdt
Karlsruhe Institute of Technology
Informatyka Teoretyczna
When Surrounding is not Catching in Cops and Robber

After a short introduction of the classical game of Cops and Robber on graphs, we shall discuss two recently introduced variants in which the robber only loses when he is completely surrounded by the cops. In the first variant the robber is surrounded when he sits at a vertex v and there is at least one cop on each neighbor of v. In the second variant cops occupy edges of the graph and the robber (still moving on vertices) is surrounded if he sits at a vertex v and there is at least one cop on each incident edge at v. We shall compare these games with each other and also with the classical game in which the robber is already caught when one cop sits on the same vertex as the robber.

26.10.2023 16:45
Agata Margas
Optymalizacja Kombinatoryczna
Making the Rules of Sports Fairer

The rules of many sports are not fair - they do not ensure that equally skilled competitors have the same probability of winning. As an example, the penalty shootout in soccer, wherein a coin toss determines which team kicks first on all five penalty kicks, gives a substantial advantage to the first-kicking team, both in theory and in practice. We show that a so-called Catch-Up Rule for determining the order of kicking would not only make the shootout fairer but is also essentially strategyproof. By contrast, the so-called Standard Rule now used for the tiebreaker in tennis is fair.

  1. Agata Margas. Making the Rules of Sports Fairer. slides. (2023).
26.10.2023 16:00
Mikołaj Kot
Optymalizacja Kombinatoryczna
Circle graphs and monadic second-order logic

Circle graph is intersection graph of set of chords od a circle. Such set is called chord diagram. It can also be described by word with two occurrences of each letter. If given graph is prime for the split decomposition, it has unique representation as chord diagram, and this diagram can be defined by monadic second-order formulas with even cardinality set predicate. The article also states that a set of circle graphs has bounded clique-width if and only if all the associated chord diagrams have bounded tree-width.

  1. Bruno Courcelle. Circle graphs and monadic second-order logic. Journal of Applied Logic. 6(3). 416-442. (2008).
  2. Mikołaj Kot. Circle graphs and monadic second-order logic. slides. (2023).
26.10.2023 14:15
Jan Klimczak, Szymon Wojtulewicz
Approximating Knapsack and Partition via Dense Subset Sums
Kwestia złożoności (1 - ε)-aproksymacji problemu plecakowego i problemu podziału pozostaje nierozstrzygnięta. Prezentujemy algorytmy:  
- (1 - ε)-aproksymacja problemu plecakowego w złożoności O(n + (1/ε)^(2.2))  
- (1 - ε)-aproksymacja problemu podziału w złożoności O(n + (1/ε)^(1.25))
Obie techniki wykorzystują poprzednie rezultaty na temat konwolucji gęstych zbiorów. Wykorzystane zostały też nowe sposoby przyspieszenia metody 'dziel i zwyciężaj', która jest często wykorzystywana w problemach addytywnych.
25.10.2023 16:15
Torsten Mütze
University of Warwick
Informatyka Teoretyczna
A book proof of the middle levels theorem

In this lecture I present an elementary and fully self-contained proof of the middle levels conjecture (now theorem), which asserts that the subgraph of the (2n+1)-dimensional hypercube induced by all bitstrings with Hamming weight n or n+1 admits a Hamilton cycle for every n1.

19.10.2023 16:45
Maksym Zub
Optymalizacja Kombinatoryczna
A note concerning the Grundy and b-chromatic number of graphs

The Grundy number Γ(G) is the maximum number of colors used by the First-Fit coloring of G denoted by Γ(G). Similarly, the b- chromatic number b(G) of G expresses the worst-case behavior of another well-known coloring procedure i.e. color-dominating coloring of G. We obtain some families of graphs F for which there exists a function f(x) such that Γ(G) ≤ f(b(G)), for each graph G from the family. Call any such family (Γ,b)-bounded family. We conjecture that the family of b-monotone graphs is (Γ, b)-bounded and validate the conjecture for some families of graphs.

  1. Manouchehr Zaker. A note concerning the Grundy and b-chromatic number of graphs. arXiv :2003.14233. (2020).
  2. Maksym Zub. A note concerning the Grundy and b-chromatic number of graphs. slides. (2023).
19.10.2023 16:00
Jakub Fedak
Optymalizacja Kombinatoryczna
The complexity of coloring circular arcs and chords

Numerous graph problems, known to be NP-complete, become polynomial when restricted to specific graph types, such as planar graphs or comparability graphs. The article shows the NP-completeness of graph coloring for circular-arc graphs and circle graphs, as well as a polynomial algorithm for producing a K-coloring for circular-arc graphs if one exists. To prove the NP-completeness of graph coloring, we use a polynomial reduction from another NP-complete problem known as the word problem for products of symmetric groups (WPPSG).

  1. M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou. SIAM Journal on Algebraic Discrete Methods. 1(2). 216-227. (1980).
  2. Jakub Fedak. The Complexity of Coloring Circular Arcs and Chords. slides. (2023).
18.10.2023 16:15
Marcelo Campos
University of Oxford
Informatyka Teoretyczna
An exponential improvement for diagonal Ramsey

The Ramsey number R(k) is the minimum n such that every red-blue colouring of the edges of the complete graph Kn on n vertices contains a monochromatic copy of Kk. We prove that R(k)≤3.99k. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.

This is joint work with Simon Griffiths, Robert Morris, Julian Sahasrabudhe.

12.10.2023 16:00
Bartłomiej Błoniarz
Optymalizacja Kombinatoryczna
(Some of) the many uses of Eulerian graphs in graph theory (plus some applications)

The article showcases diverse associations between Eulerian graphs and other attributes of graphs such as being Hamiltonian, nowhere-zero flows, the cycle-plus-triangles problem, and issues emanating from it. It shows the application of compatible cycle decompositions in creating loopless 4-regular graphs with exactly one Hamiltonian cycle, or in establishing the equivalence between the Chinese Postman Problem and the Planar Bridgeless Minimum Cycle Covering Problem.

  1. Bartłomiej Błoniarz. (Some of) the many uses of Eulerian graphs in graph theory (plus some applications). slides. (2023).
  2. H. Fleischner. (Some of) the many uses of Eulerian graphs in graph theory (plus some applications) Discrete Mathematics 230(1-3). 23-43. (2001).
12.10.2023 14:15
Kacper Topolski, Jakub Wąs
Simple and Faster Algorithms for Knapsack
Na tym seminarium zdefiniujemy problem plecakowy oraz jego wariacje - wersję 0-1, ograniczoną oraz DiffKnapsack. Przybliżymy najnowsze rezultaty związane z tym problemem. W szczególności zaprezentujemy prosty algorytm randomizowany rozwiązujący dyskretny wariant problemu plecakowego oraz oparty na nim algorytm rozwiązujący wersję ograniczoną. Jest on rozwinięciem pierwszego algorytmu o liniowej zależności względem liczby elementów, zaprezentowanego przez Adama Polaka.
12.10.2023 14:15
Kacper Topolski, Jakub Wąs
Simple and Faster Algorithms for Knapsack
Na tym seminarium zdefiniujemy problem plecakowy oraz jego wariacje - wersję 0-1, ograniczoną oraz DiffKnapsack. Przybliżymy najnowsze rezultaty związane z tym problemem. W szczególności zaprezentujemy prosty algorytm randomizowany rozwiązujący dyskretny wariant problemu plecakowego oraz oparty na nim algorytm rozwiązujący wersję ograniczoną. Jest on rozwinięciem pierwszego algorytmu o liniowej zależności względem liczby elementów, zaprezentowanego przez Adama Polaka.
11.10.2023 16:15
Krzysztof Potępa
Jagiellonian University
Informatyka Teoretyczna
Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs

We develop a framework for algorithms finding diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) sub-quadratic time complexity. The class of bounded distance VC-dimension graphs is wide, including, e.g. all minor-free graphs.

We build on the work of Ducoffe et al., improving their technique. With our approach the algorithms become simpler and faster, working in Õ(k·V1-1/d·E) time complexity, where k is the diameter, d is the VC-dimension. Furthermore, it allows us to use the technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we answer a question posed by Bringmann et al., finding a Õ(n7/4) parameterized diameter algorithm for unit square intersection graph of size n, as well as a more general algorithm for convex polygon intersection graphs.

This is joint work with Lech Duraj and Filip Konieczny.

05.10.2023 16:00
Bartłomiej Bosek
Optymalizacja Kombinatoryczna
Some open problems from combinatorics and algorithmics

The first presented problem concerns the majority coloring of graphs in the undirected and directed cases. A surprising connection with the problem of spreading epidemics in graphs will be shown. The second presented problem concerns the hat guessing game. The most classic results as well as the most interesting unresolved hypotheses will be shown. The last presented problem will concern randomized online algorithms for finding matching in bipartite graphs. Classic algorithms and research directions worth pursuing will be presented.

04.10.2023 16:15
Avi Wigderson
Institute for Advanced Study, Princeton
Informatyka Teoretyczna
The Value of Errors in Proofs

Recently, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title "MIP* = RE", surprising and impacting not only complexity theory but also some areas of math and physics. Specifically,  it resolved, in the negative, the "Connes' embedding conjecture" in the area of von-Neumann algebras, and the "Tsirelson problem" in quantum information theory. It further connects Turing's seminal 1936 paper which defined algorithms to Einstein's 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here

As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we'll take a meandering jurney through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (of both problems and proofs) by algorithmic efficiency, naturally leads to the genaration of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.

The talk does not require special mathematical background.

15.06.2023 16:45
Julia Biały
Optymalizacja Kombinatoryczna
A game generalizing Hall's Theorem

Authors investigate starting positions in a particular two-player game, considering scenarios where the first player can have a winning strategy. This work offers a broader interpretation of Hall's Theorem using Vizing's Theorem on edge-coloring in a specialized setting.

  1. Julia Biały. A game generalizing Hall's Theorem. slides. (2023).
  2. Landon Rabern. A game generalizing Hall's theorem. arXiv:1204.0139. (2012).
15.06.2023 16:00
Łukasz Selwa
Optymalizacja Kombinatoryczna
Orientations of Graphs with Prescribed Weighted Out-Degrees

We study the complexity of the orientation problem where the out-neighborhood of every vertex is bounded by some function. This problem can be used to apply Galvin’s kernel method to show that graph G satisfies a certain coloring property. We show that the problem is NP-complete in the case of graphs that are bipartite, planar, and of maximum degree at most 3. We also prove some results on the (f,g)-choosability problem for weighted graphs, including a generalization of Brooks's theorem for weighted graphs.

  1. Michael Stiebitz, Zsolt Tuza, Margit Voigt. Orientations of Graphs with Prescribed Weighted Out-Degrees. Graphs and Combinatorics 31, 265-280. (2015).
14.06.2023 16:15
Fabrizio Frati
Università Roma Tre
Informatyka Teoretyczna
Currents Trends and Hot Problems in Graph Drawing

In this expository talk, I will discuss the topics that have attracted the most attention in the graph drawing community in recent years. The talk will try to convey the direction where the research in graph drawing is going, with a focus on the most intriguing open problems in the field.

07.06.2023 16:15
Michał Seweryn
Université Libre de Bruxelles
Informatyka Teoretyczna
Recent results in graph product structure theory

Graph product structure theory describes complicated graphs as subgraphs of strong products of simpler building blocks. Usually, the strong product involves three graphs: a graph of bounded treewidth, a small complete graph, and a path. For example, Dujmović et al. showed that every planar graph is a subgraph of the strong product of a treewidth-3 graph, a complete graph on three vertices, and a path. This theorem has been the key to solving many long-standing problems about planar graphs, and is arguably the most important result of the graph product structure theory.

In my talk I will discuss some of the recent results in this field. First I will discuss two generalizations of the product structure theorem for planar graphs to k-planar graphs and k-powers of planar graphs with bounded degree. The distinguishing property of these theorems is that the bound on the treewidth in the product is an absolute constant independent of k and the maximum degree. Then, I will discuss some product structure theorems, where an n-vertex graph is a subgraph of the strong product of two graphs: a graph of constant treewidth, and a complete graph on O(n) vertices. These theorems are qualitative strengthenings of √n-separator theorems by Lipton-Tarjan and Alon-Seymour-Thomas.  

Joint works with Marc Distel, Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David Wood