Seminars
02.10.2024 16:15 TBA 
Theoretical computer science TBA  2024.10.02 
09.10.2024 16:15 TBA 
Theoretical computer science TBA  2024.10.09 
16.10.2024 16:15 TBA 
Theoretical computer science TBA  2024.10.16 
Poprzednie referaty
13.06.2024 16:00 Łukasz Gniecki 
Combinatorial Optimization TBA Łukasz Gniecki 
...

12.06.2024 16:15 António Girão University of Oxford 
Theoretical computer science Induced C_4free 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 nontrivial 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 C_{4}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 K_{s,s}free graph with average degree at least C_{k}·s^{Ck^4} contains an induced subgraph which is C_{4}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 C_{H}·s^{CH^4} either contains a K_{s,s} or an induced subdivision of H.
summer break 
06.06.2024 16:45 Jędrzej Hodor 
Combinatorial Optimization TBA Jędrzej Hodor 
...

06.06.2024 16:00 Jakub Fedak 
Combinatorial Optimization TBA Jakub Fedak 
...

05.06.2024 16:15 Maria Chudnovsky Princeton University 
Theoretical computer science Anticomplete subgraphs of large treewidth 
We will discuss recent progress on the topic of induced subgraphs and treedecompositions. 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 
Theoretical computer science 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 bookembedding 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 (fixedvertexorder) page number. We show that the page number of an ordered graph with n vertices and m edges can be computed in 2^{m}⋅poly(n) time. An O(log n)approximation of this number can be computed efficiently. We can decide in 2^{O(d√k⋅log(d+k))}⋅poly(n) time whether it suffices to delete k edges of an ordered graph to obtain a dplanar 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 fixedvertexorder page number p. For h>1, we give an XP algorithm with respect to h+p. Finally, we consider spine+ttrack 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 
Combinatorial Optimization The AlonTarsi number of K3,3minorfree graphs 
For a graph G, denote AT(G) as the AlonTarsi 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 K_{5} and K_{3,3} as a minor. We prove these three AlonTarsi number bounds for G that is only K_{3,3}minorfree, strengthening the result for planar graphs.

16.05.2024 16:00 Filip Konieczny 
Combinatorial Optimization 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.

15.05.2024 16:15 Marta Kwiatkowska University of Oxford 
Theoretical computer science Strategy synthesis for partially observable stochastic games with neural perception mechanisms 
Strategic reasoning is essential to ensure stable multiagent coordination in complex environments, as it enables synthesis of optimal (or nearoptimal) agent strategies and equilibria that guarantee expected outcomes, even in adversarial scenarios. Partiallyobservable stochastic games (POSGs) are a natural model for realworld 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 onesided POSGs, a subclass of twoagent, zerosum 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 onesided POSGs.

09.05.2024 16:45 Aleksander Katan 
Combinatorial Optimization 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 D_{0} of V, we define the procedure of the influence spread as follows: in turn i, a vertex v joins D_{i} if it either is in D_{i1}, or has at least t(v) inneighbors in D_{i1}. A subset D of V is called a tdynamic monopoly if there exists a turn j such that D_{j }= V. We will discuss the hardness of finding the smallest tdynamic monopoly when t(v) = 2, as well as prove that every graph admits a tdynamic monopoly of size V/2 when t(v) = ⌈(deg_{in}(v)+1)/2⌉. 
09.05.2024 16:00 Ignacy Buczek 
Combinatorial Optimization Flipwidth 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 flipwidth, 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 fixedparameter tractable.

08.05.2024 16:15 Michał Pilipczuk University of Warsaw 
Theoretical computer science 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 O_{H}(m^{1+o(1)}). This improves the classic cubictime 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 O_{C}(m^{1+o(1)})time membership test for every minorclosed 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 O_{k}(m^{1+o(1)}). This is a joint work with Tuukka Korhonen and Giannos Stamoulis 
25.04.2024 16:45 Sebastian Spyrzewski 
Combinatorial Optimization Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited 
It is a very wellknown 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.

25.04.2024 16:00 Katarzyna Kępińska 
Combinatorial Optimization 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.

24.04.2024 16:15 Bartosz Walczak Jagiellonian University 
Theoretical computer science Polynomialtime recognition and maximum independent set in Burling graphs 
A Burling graph is an induced subgraph of some graph in Burling's construction of trianglefree highchromatic graphs. Burling graphs can also be characterized as graphs with socalled strict frame representations, i.e., intersection models by suitably restricted rectangular frames. We provide a polynomialtime algorithm which decides whether a given graph is a Burling graph and if it is, constructs its strict frame representation. We also provide a polynomialtime 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 
Combinatorial Optimization 3Colorability of 4Regular Hamiltonian Graphs 
It is a wellknown result known as the 'cycleplustriangles' theorem that every graph on 3n vertices consisting of a Hamiltonian cycle and n nodedisjoint triangles is 3colorable. To improve this result we search for less strict restrictions of G\H. By reduction we show that two following problems are NPcomplete: (1) 3colorability of 4regular Hamiltonian graphs. (2) 3colorability of 4regular Hamiltonian graphs whose inner cycles (connected components after Hamiltonian cycle removal) are nonselfcrossing kgons.

18.04.2024 16:00 Maksym Zub 
Combinatorial Optimization 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 ⌈(L1)/(L2)L⌉ colors suffice to color F, and this upper bound is tight. 
17.04.2024 16:15 Hoang La Université ParisSaclay 
Theoretical computer science 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 outputpolynomial time algorithms that enumerate every trianglefree graph (resp. every graph with bounded maximum degree) that is consistent with a specified set of connected ksets. Notably, we prove that trianglefree graphs are uniquely reconstructible, while graphs with bounded maximum degree that are consistent with the same ksets share a substantial common structure, differing only locally. We suspect that the problem is NPhard in general and provide a NPhardness proof for a variant where the connectivity is specified for only some ksets (with k at least 4). 
11.04.2024 16:45 Mateusz Hurkała 
Combinatorial Optimization The two possible values of the chromatic number of a random graph 
Given d in range (0, ∞) let k_{d} 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 k_{d} or k_{d+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.

11.04.2024 16:00 Rafał Kajca 
Combinatorial Optimization Circulararc graph coloring and unrolling 
The register periodic allocation problem is viewed as unrolling and coloring the underlying structure of circulararc 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 noncyclic ones for which we prove the asymptotic property: let r be the width of the original interval family. Then the uunrolled graph is r or (r+1)colorable for u large enough. 
10.04.2024 16:15 Jean Cardinal Université Libre de Bruxelles 
Theoretical computer science 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. 
04.04.2024 16:45 Filip Jasionowicz 
Combinatorial Optimization 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.

04.04.2024 16:00 Agata Margas 
Combinatorial Optimization 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 2in, 2out graph. We will count the number of pairings of given length, for which the induced graph has exactly k Euler circuits. 
03.04.2024 16:15 David Conlon California Institute of Technology 
Theoretical computer science 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 edgecoloured 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 
Theoretical computer science 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 nvertex oriented graphs at distance no(n) of any acyclic orientation. We also investigate the minimum number of inversions needed to make an oriented graph kstronglyconnected, 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 
Combinatorial Optimization 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 bicolored Ramsey complete graphs, demonstrated through examples of graphs containing up to six vertices. 
21.03.2024 16:00 Piotr Kaliciak 
Combinatorial Optimization An algorithm for identifying cycleplustriangles graphs 
A cycleplustriangle graph is a union of nodedisjoint triangles and a Hamiltonian cycle. It is known that such graphs are 3colorable, but the problem of finding any 3coloring is still open. The authors show a polynomial time algorithm for deciding if a given graph is cycleplustriangle, and if this is the case, the algorithm provides the decomposition into the triangles and a cycle. 
20.03.2024 16:15 Gábor Tardos Alfréd Rényi Institute of Mathematics 
Theoretical computer science Forbidden acyclic patterns in 01 matrices 
A zeroone matrix M is said to contain another zeroone matrix A if we can delete some rows and columns of M and replace some 1entries with 0entries such that the resulting matrix is A. The extremal function of A, denoted ex(n,A), is the maximum number of 1entries that an n×n zeroone 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 DavenportSchinzel theory and has many applications in mathematics and theoretical computer science. The problem has been particularly extensively studied for socalled 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,A_{k}) asymptotically for certain simple 2×k acyclic patterns to be Θ(n·(log n/loglog n)^{k−2}) for k>3. This shows that the PachTardos conjecture is tight if true. The conjecture itself is still wide open. 
14.03.2024 16:45 Michał Mizołek 
Combinatorial Optimization 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. 
14.03.2024 16:00 Maciej Sanocki 
Combinatorial Optimization Randomized PrimalDual 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 11/e competitiveness of RANKING algorithm for the online bipartite matching problem. This time however, the proof is via a randomised primaldual argument. 
07.03.2024 16:00 Bartłomiej Błoniarz 
Combinatorial Optimization Cooperative colorings of trees and of bipartite graphs 
In a system of graphs (G_{1}, ..., G_{m}) sharing the same set of vertices (V), a cooperative coloring involves selecting vertex sets (I_{1}, ..., I_{m}) where each I_{j} is independent in G_{j}, 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. 
06.03.2024 16:15 Jacob Fox Stanford University 
Theoretical computer science Structure theorems for intersection patterns of geometric objects 
In this talk we discuss Szemeréditype structure theorems, Ramseytype theorems, and Turántype theorems for intersection patterns of geometric objects and their relationships to each other. In particular, we discuss recent such results on intersection graphs of pseudosegments 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 
Combinatorial Optimization 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 
Combinatorial Optimization 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 longstanding 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.

25.01.2024 16:45 Artemy Oueiski 
Combinatorial Optimization A simple linear time algorithm for cograph recognition 
Cographs are precisely the P_{4}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.

25.01.2024 16:00 Katzper Michno 
Combinatorial Optimization Another approach to nonrepetitive colorings of graphs of bounded degree 
A nonrepetitive graph coloring (of vertices or edges) is a coloring such that all sequences of colors induced by paths in the graph are nonrepetitive (squarefree), which means that they do not contain any consecutive subsequence that is a square. The nonrepetitive number of a graph is the minimal number of colors in a nonrepetitive vertex coloring (resp. nonrepetitive index for coloring edges). There are also list counterparts of these numbers. Many maximal degree related upper bounds for nonrepetitive 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 nonrepetitive number in several cases and matches some of already known bounds using the new technique. 
24.01.2024 16:15 Sergio Cabello University of Ljubljana and IMFM, Slovenia 
Theoretical computer science Packing ddimensional balls into a (d+1)dimensional container 
We consider the problems of finding in d+1 dimensions a minimumvolume axisparallel box, a minimumvolume arbitrarilyoriented box and a minimumvolume convex body into which a given set of ddimensional unitradius balls can be packed under translations. We give a constantfactor approximation algorithm for each of these containers. We also show that for n such balls, a container of volume O(n^{1−1/d}) is always sufficient and sometimes necessary. Joint work with Helmut Alt, Otfried Cheong, Jiwon Park and Nadja Seiferth. 
18.01.2024 16:45 Milana Kananovich 
Combinatorial Optimization 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 P_{4}): a stepbystep 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).

18.01.2024 16:00 Sebastian Spyrzewski 
Combinatorial Optimization List coloring with requests 
In this paper we consider the problem of Lcoloring 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 Lcoloring 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. 
17.01.2024 16:15 Jim Geelen University of Waterloo 
Theoretical computer science Average plane size 
Consider a finite set of distinct points in ddimensional 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 noncollinear 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 
Combinatorial Optimization Countable graphs are majority 3choosable 
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 2coloring. It is known that for every (not necessarily countable) graph a majority 3coloring always exists. Anholcer, Bosek, and Grytczuk have recently proven that every countable graph is majority 4choosable, 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 3colorable. 
11.01.2024 16:00 Łukasz Gniecki 
Combinatorial Optimization The Alon Tarsi Number of Planar Graphs  a Simple Proof 
The AlonTarsi 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 AlonTarsi 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. 
10.01.2024 16:15 Peter Allen London School of Economics and Political Science 
Theoretical computer science 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 nvertex graphs with maximum degree k, and showed that there is a universal graph for this family with O(n^{22/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 nvertex ddegenerate graphs with Õ(n^{21/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 
Combinatorial Optimization On two generalizations of the Alon–Tarsi polynomial method 
The AlonTarsi number of a graph G=([n], E) is the smallest integer k, such that there exists a monomial x_{1}^{d1}x_{2}^{d2}...x_{n}^{dn} in the expansion of the graph polynomial of G having nonzero coefficient and satisfying d_{i }< 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 nonzeroness of the coefficient of the monomial x_{1}^{d1}...x_{n}^{dn} in case d_{i} = outdeg_{D}(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 nonzero. 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 nonzero iff the sum of f(A) over all the suborientations A of D is nonzero. 
21.12.2023 16:00 Ignacy Buczek 
Combinatorial Optimization A note on computerassisted 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 nontrivial example that we stumbled upon in our unpublished work on balanced bipartitions of K_{4}free graphs. 
20.12.2023 16:15 Paweł Rzążewski Warsaw University of Technology 
Theoretical computer science Understanding graphs with no long claws 
A classic result of Alekseev asserts that for connected H the MAX INDEPENDENT SET (MIS) problem in Hfree graphs in NPhard unless H is a path or a subdivided claw. Recently we have witnessed some great progress in understanding the complexity of MIS in P_{t}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 quasipolynomialtime algorithm for the problem. 
14.12.2023 16:00 Jędrzej Hodor 
Combinatorial Optimization 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 leftbottom corner. A player can either move the queen diagonally towards the leftbottom 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 nonnegative integer n such that the queen starts in the position (⌊nφ⌋, ⌊nφ^{2}⌋), where φ is the golden ratio. 
13.12.2023 00:00 
Theoretical computer science The 17th workshop on Computational Logic and Applications 
07.12.2023 16:00 Piotr Kaliciak 
Combinatorial Optimization 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 ddegenerate and outerplanar graphs. 
06.12.2023 16:15 Paul Bastide LaBRI, Bordeaux 
Theoretical computer science 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 kantichain 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(n^{c}), where c≤P^{2}/4+1. This is based on joint works with Carla Groenland, MariaRomina Ivan, Hugo Jacob and Tom Johnston. 
30.11.2023 16:45 Jan Klimczak 
Combinatorial Optimization On the equitable distribution of points on the circle 
The stickbreaking 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. 
30.11.2023 16:00 Rafał Pyzik 
Combinatorial Optimization 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 MinIndex framework  a family of randomized algorithms for this problem. Using this framework, we show a 5/9competitive algorithm when the graph is a tree. Moreover, we show that any algorithm in the edge arrival model is at most 0.5914 competitive. 
29.11.2023 16:15 Matthieu Rosenfeld LIRMM, Montpellier 
Theoretical computer science 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. 
23.11.2023 16:45 Izabela Tylek 
Combinatorial Optimization Any 7chromatic 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 kchromatic graph has a K_{k}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 fourcolor 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 7chromatic graph has a K_{7} or K_{4,4} as a minor. 
23.11.2023 16:00 Justyna Jaworska 
Combinatorial Optimization 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 circulararc graphs, the coloring problem is polynomially solvable, most recently, in O(n^{1.5} log n) time (Teng and Tucker). It's due to the fact that the (qcolorability) problem can be reduced to a shortest path problem. In this note, we improve Teng and Tucker’s algorithm obtaining O(n^{1.5}) running time. 
22.11.2023 16:15 Gábor Damásdi Alfréd Rényi Institute of Mathematics 
Theoretical computer science Monochromatic configurations on the circle 
In this lecture we will discuss a surprising combinatorial conjecture. For k≥3 call a ktuple (d_{1},d_{2},...,d_{k}) with d_{1}≥d_{2}≥...≥d_{k}>0 and d_{1}+d_{2}+...+d_{k}=1 a Ramsey ktuple if the following is true: in every twocolouring of the circle of unit perimeter, there is a monochromatic ktuple of points in which the distances of cyclically consecutive points, measured along the arcs, are d_{1},d_{2},...,d_{k} in some order. By a conjecture of Stromquist, if d_{i}=2^{ki}/(2^{k}1), then d_{1},d_{2},...,d_{k} is Ramsey. Using Sat solvers we showed that the conjecture holds for k≤7. Our main result is a proof of the converse of this conjecture. That is, we show that if (d_{1},d_{2},...,d_{k}) is Ramsey, then d_{i}=2^{ki}/(2^{k}1). We do this by finding connections of the problem to certain questions from number theory about partitioning N into socalled Beatty sequences.

16.11.2023 16:45 Maciej Sanocki 
Combinatorial Optimization Twosided 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 bmatching and try to maximize its size. We show that this problem can be attacked by considering the complementary “dual” problem, a twosided online bipartite vertex cover. 
16.11.2023 16:00 Katarzyna Kępińska 
Combinatorial Optimization 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 Lcoloring such that maximum degree of monochromatic subgraph is at most d. This paper shows two constructions of graphs: 1defective 3choosable that are not 4choosable and (k,d,l)choosable that are not (k,d,l+1)choosable. 
15.11.2023 16:15 Piotr Micek Jagiellonian 
Theoretical computer science Tight bound for the ErdősPó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 vertexdisjoint subgraphs each having a T minor, or there exists a set X of at most t(k1) vertices of G such that GX 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 
Combinatorial Optimization 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 kcolorings 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 
Theoretical computer science 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 
Combinatorial Optimization 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 firstkicking team, both in theory and in practice. We show that a socalled CatchUp Rule for determining the order of kicking would not only make the shootout fairer but is also essentially strategyproof. By contrast, the socalled Standard Rule now used for the tiebreaker in tennis is fair. 
26.10.2023 16:00 Mikołaj Kot 
Combinatorial Optimization Circle graphs and monadic secondorder 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 secondorder formulas with even cardinality set predicate. The article also states that a set of circle graphs has bounded cliquewidth if and only if all the associated chord diagrams have bounded treewidth. 
26.10.2023 14:15 Jan Klimczak, Szymon Wojtulewicz 
Algorytmika 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 
Theoretical computer science A book proof of the middle levels theorem 
In this lecture I present an elementary and fully selfcontained 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 n≥1. 
19.10.2023 16:45 Maksym Zub 
Combinatorial Optimization A note concerning the Grundy and bchromatic number of graphs 
The Grundy number Γ(G) is the maximum number of colors used by the FirstFit coloring of G denoted by Γ(G). Similarly, the b chromatic number b(G) of G expresses the worstcase behavior of another wellknown coloring procedure i.e. colordominating 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 bmonotone graphs is (Γ, b)bounded and validate the conjecture for some families of graphs. 
19.10.2023 16:00 Jakub Fedak 
Combinatorial Optimization The complexity of coloring circular arcs and chords 
Numerous graph problems, known to be NPcomplete, become polynomial when restricted to specific graph types, such as planar graphs or comparability graphs. The article shows the NPcompleteness of graph coloring for circulararc graphs and circle graphs, as well as a polynomial algorithm for producing a Kcoloring for circulararc graphs if one exists. To prove the NPcompleteness of graph coloring, we use a polynomial reduction from another NPcomplete problem known as the word problem for products of symmetric groups (WPPSG). 
18.10.2023 16:15 Marcelo Campos University of Oxford 
Theoretical computer science An exponential improvement for diagonal Ramsey 
The Ramsey number R(k) is the minimum n such that every redblue colouring of the edges of the complete graph K_{n} on n vertices contains a monochromatic copy of K_{k}. We prove that R(k)≤3.99^{k}. This is the first exponential improvement over the upper bound of Erdős and Szekeres, proved in 1935.

12.10.2023 16:00 Bartłomiej Błoniarz 
Combinatorial Optimization (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, nowherezero flows, the cycleplustriangles problem, and issues emanating from it. It shows the application of compatible cycle decompositions in creating loopless 4regular graphs with exactly one Hamiltonian cycle, or in establishing the equivalence between the Chinese Postman Problem and the Planar Bridgeless Minimum Cycle Covering Problem. 
12.10.2023 14:15 Kacper Topolski, Jakub Wąs 
Algorytmika Simple and Faster Algorithms for Knapsack 
Na tym seminarium zdefiniujemy problem plecakowy oraz jego wariacje  wersję 01, 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 m.in. przez Adama Polaka. 
12.10.2023 14:15 Kacper Topolski, Jakub Wąs 
Algorytmika Simple and Faster Algorithms for Knapsack 
Na tym seminarium zdefiniujemy problem plecakowy oraz jego wariacje  wersję 01, 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 m.in. przez Adama Polaka. 
11.10.2023 16:15 Krzysztof Potępa Jagiellonian University 
Theoretical computer science Better Diameter Algorithms for Bounded VCdimension Graphs and Geometric Intersection Graphs 
We develop a framework for algorithms finding diameter in graphs of bounded distance VapnikChervonenkis dimension, in (parameterized) subquadratic time complexity. The class of bounded distance VCdimension graphs is wide, including, e.g. all minorfree 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·V^{11/d}·E) time complexity, where k is the diameter, d is the VCdimension. 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 Õ(n^{7/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 
Combinatorial Optimization 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 
Theoretical computer science The Value of Errors in Proofs 
Recently, a group of theoretical computer scientists posted a paper on the Arxiv with the strangelooking 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 vonNeumann 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 https://arxiv.org/abs/2001.043 
15.06.2023 16:45 Julia Biały 
Combinatorial Optimization A game generalizing Hall's Theorem 
Authors investigate starting positions in a particular twoplayer 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 edgecoloring in a specialized setting. 
15.06.2023 16:00 Łukasz Selwa 
Combinatorial Optimization Orientations of Graphs with Prescribed Weighted OutDegrees 
We study the complexity of the orientation problem where the outneighborhood 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 NPcomplete 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. 
14.06.2023 16:15 Fabrizio Frati Università Roma Tre 
Theoretical computer science 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. 
 Home
 Algorithmics Research Group
 Foundations of Computer Science
 Faculty of Mathematics and Computer Science
 Contact
 Satori
 Reports on Mathematical Logic
 Forum TCS
 UsosWeb
 Informatyka na szlaku
 Photos
 People
 Demian Banakh
 Bartłomiej Bosek
 Marcin Briański
 Iwona Cieślik
 Jan Derbisz
 Andrzej Dorobisz
 Lech Duraj
 Monika Gillert
 Katarzyna Grygiel
 Grzegorz Gutowski
 Grzegorz Herman
 Jędrzej Hodor
 Pawel M. Idziak
 Marcin Kozik
 Jakub Kozik
 Jacek Krzaczkowski
 Agnieszka Łupińska
 Piotr Micek
 Piotr Mikołajczyk
 Jonathan Narboni
 Andrzej Pezarski
 Bartosz Podkanowicz
 Adam Polak
 Krzysztof Potępa
 Wojciech Szpankowski
 Maciej Ślusarek
 Jan Tułowiecki
 Krzysztof Turowski
 Bartosz Walczak
 Michał Wrona
 Marek Zaionc
 Former colleagues