Seminars
28.02.2024 16:15 TBA 
Theoretical computer science TBA  2024.02.28 
06.03.2024 16:15 TBA 
Theoretical computer science TBA  2024.03.06 
13.03.2024 16:15 TBA 
Theoretical computer science TBA  2024.03.13 
20.03.2024 16:15 TBA 
Theoretical computer science TBA  2024.03.20 
Poprzednie referaty
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. 
07.06.2023 16:15 Michał Seweryn Université Libre de Bruxelles 
Theoretical computer science 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 treewidth3 graph, a complete graph on three vertices, and a path. This theorem has been the key to solving many longstanding 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 kplanar graphs and kpowers 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 nvertex 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 √nseparator theorems by LiptonTarjan and AlonSeymourThomas. Joint works with Marc Distel, Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David Wood 
31.05.2023 16:15 Ola Svensson École Polytechnique Fédérale de Lausanne 
Theoretical computer science The Price of Explainability for Clustering 
Given a set of points in ddimensional space, an explainable clustering is one where the clusters are specified by a tree of axisaligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worstcase ratio between the cost of the best explainable clusterings to that of the best clusterings.
We show that the price of explainability for kmedians is at most 1+H_{k−1}; in fact, we show that the popular Random Thresholds algorithm has exactly this price of explainability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explainability (using any algorithm) is at least (1−o(1))·ln k, showing that our result is best possible, up to lowerorder terms. We also improve the price of explainability for the kmeans problem to O(k·lnln k) from the previous O(k·ln k), considerably closing the gap to the lower bounds of Ω(k).
Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable kmedians and kmeans cannot be approximated better than O(ln k), under standard complexitytheoretic conjectures. This essentially settles the approximability of explainable kmedians and leaves open the intriguing possibility to get significantly better approximation algorithms for kmeans than its price of explainability.
This is joint work with Anupam Gupta, Madhusudhan Reddy Pittu, and Rachel Yuan 
25.05.2023 16:45 Katarzyna Król 
Combinatorial Optimization Ball Packings and Lorentzian Discrete Geometry 
The problem of packing balls is to find an arrangement of spheres in space so that no spheres overlap. It is popular in the literature to consider packing disks  i.e. twodimensional spheres. A tangency graph is a graph whose vertices are balls and whose edge is between vertices u and v if ball u and ball v touch each other. We study ball packings whose tangency graph is a higher dimensional grid graph. We give a loose bound on the size of such grid graphs that admit a ball packing. 
25.05.2023 16:00 Jędrzej Kula 
Combinatorial Optimization Playing cards with Vizing's demon 
The paper's authors present a parametrized version of the solitaire game. In this version, players play against a demon whose task is to rearrange cards after each move in a way that the player will not be able to win the game. By defining a specific demon strategy and finding the winning strategy against it, one may prove König and Vizing theorems. 
24.05.2023 16:15 Csaba Tóth California State University, Northridge 
Theoretical computer science Optimal spanners in Euclidean spaces 
For a set S of n points in a metric space (X,d) and a parameter t>1, a tspanner is a weighted graph G=(S,E) such that the shortest path distance in G approximates the pairwise distances in the metric space up to a factor of at most t (stretch factor). This talk focuses on the ddimensional Euclidean space in the regime where t is close to 1. Recent research uncovered tight tradeoffs for two important quality measures for tspanners: the sparsity E(G)/n and the lightness w(G)/w(MST(S)). We present an algorithm that constructs a tspanner for a given set of n points in Euclidean dspace, by sparsifying classical Yaographs, that attains a worstcase optimal bound on the weight of the spanner. In the online model, a sequence of points arrive onebyone, and we need to maintain a tspanner for the first n points for all n. By combining sparse Yaographs and hierarchical clustering, we obtain an online algorithm that maintains a light spanner and achieves logarithmic competitive ratio compared to the offline optimum. 
18.05.2023 16:45 Krzysztof Barański 
Combinatorial Optimization A note on degreeconstrained subgraphs 
Last semester I presented a paper “A note on polynomials and ffactors of graphs” by Hamed Shirazi and Jacques Verstraëte, who proved two ffactor theorems using the Combinatorial Nullstellensatz. In this work, authors take a closer look at the same theorems and prove them in a different way. 
18.05.2023 16:00 Filip Konieczny 
Combinatorial Optimization On constructive methods in the theory of colourcritical graphs 
kcritical graph is not (k1)colorable but every proper subgraph is. The authors take a constructive approach to the theory of critical graphs and show methods of how such graphs can be constructed, composed, and augmented, additionally discussing the advantages and drawbacks of these methods. 
17.05.2023 16:15 John Iacono Université Libre de Bruxelles 
Theoretical computer science The pursuit of the dynamic optimality conjecture via the geometry of binary search trees 
In 1983, Sleator and Tarjan introduced the splay tree, a selfadjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotationbased search tree algorithm on every sufficiently long sequence — any binary search tree algorithm that has this property is said to be dynamically optimal. However, currently neither splay trees nor any other tree algorithm is known to be dynamically optimal. In doing so we will present the geometric view of binary search trees, introduced in 2009, where we (with Erik D. Demaine, Dion Harmon, Daniel M. Kane and Mihai Pătraşcu) showed an equivalence between binary search tree algorithms and a simple combinatorial property of points in the plane. Almost all recent progress, which we will survey, towards the fortyyearold dynamic optimality conjecture since then has used this view, as it greatly simplifies reasoning about binary search trees. 
11.05.2023 16:45 Rafał Pyzik 
Combinatorial Optimization Improved lower bounds on the number of edges in list critical and online list critical graphs 
A graph G is kcritical if it is not (k1)colorable, but every proper subgraph of G is. Authors improve the bound by Kostochka and Stiebitz for a number of edges in kcritical graphs. The same bound holds for klistcritical and online klistcritical graphs improving the bound established by Riasat and Schauz. This result follows from analyzing AlonTarsi orientable induced subgraphs satisfying certain conditions.

11.05.2023 16:00 Aleksander Katan 
Combinatorial Optimization A not 3choosable planar graph without 3cycles 
An Llist coloring of graph G is a proper vertex coloring in which every vertex receives a color from a prescribed list L(v). G is said to be kchoosable, if all lists L(v) have cardinality k, and G is Lcolorable for any assignment of those lists. The author presents a planar graph without 3cycles that is not 3choosable. We will also discuss other topics related to list colorings, such as the fact that every planar graph is 5choosable.

10.05.2023 16:15 Clément Rambaud École Normale Supérieure, PSL Paris 
Theoretical computer science Neighborhood complexity of planar graphs 
In a class of graphs of bounded expansion, for every graph in the class, for every nonempty set A of vertices, for every radius r, the number of distinct intersections between A and a ball of radius r is at most f(r)·A for some function f depending only on the considered class [Reidl, Sánchez Villaamil and Stravopoulos, 2019]. The function f coming from existing proofs is typically exponential. We prove that in the special case of planar graphs, f can be taken to be a polynomial, and more precisely in O(r^{4}). We also show that a polynomial bound holds more generally for every proper minorclosed class of graphs. This is joint work with Gwenaël Joret. 
04.05.2023 16:45 Rafał Kilar 
Combinatorial Optimization On the structure of kconnected graphs without K_kminor 
The famous Hadwiger's Conjecture states that every kchromatic graph must contain the clique K_{k} as a minor. It remains unproven for k>6. Motivated by this conjecture we can ask about the structure of kconnected graphs without K_{k} as a minor. We show that any such graph can't have three (k2)cliques that share at most three vertices, which is a generalization of previous results in the area. 
04.05.2023 16:00 Bartłomiej Błoniarz 
Combinatorial Optimization Pólya's Permanent Problem 
The permanent of a square matrix is a function very similar to the determinant. It has important applications in counting problems, but computing it is a #Pcomplete problem. In 1913, Pólya proposed a method to calculate permanents using determinants, which was soon proven to be faulty in certain cases. This led to the question of when Pólya's method can be used, known as Pólya's Permanent Problem. The article provides an overview of the problem, including equivalent versions and a solution to one of the formulations. 
27.04.2023 16:45 Demian Banakh 
Combinatorial Optimization Flip distance to a noncrossing perfect matching 
A noncrossing perfect matching is Euclidean matching on 2n points so that no 2 segments cross. Given some crossing matching, we can iteratively apply the flip operation (fix any 2 crossing segments, and swap the endpoints so that they don't cross) to eventually arrive at a noncrossing matching. We will investigate the upper and lower bounds for the number of flips sufficient and necessary to eliminate all crossings. It is conjectured that θ(n^{2}) flips are always sufficient.

27.04.2023 16:00 Szymon Salabura 
Combinatorial Optimization Edge lower bounds for list critical graphs, via discharging 
We say that a graph G is kchoosable if G has a proper coloring from every list assignment L with L(v)=k for every vertex v. A graph G is klistcritical if it's not kchoosable, but every proper subgraph of G is. The problem of bounding the number of edges from below in such graphs has been widely studied, starting with the work of Gallai. The authors present a rephrased version of his proof using the discharging method and improve the original result by presenting additional properties of such graphs, enabling a different set of discharging rules. 
27.04.2023 14:15 Justyna Jaworska, Jakub Siuta 
Algorytmika Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance 
Dla problemów znjadowania odległości edycyjnej i odległości edycyjnej Dycka chcemy znaleść szybkie, deterministyczne i proste aproksymacje, z być może dużym współczynnikiem aproksymacji. Dla klasycznej odległości edycyjnej wprowadzimy klasę szybkich i prostych algorytmów nazywanych "algorytmami pojdedycznego skanowania". Saha, w 2014. roku, podał randomizowany algorytm z tej klasy osiągający aproksymację O(d) dla słow x, y takich że ich ogległość edycyjna jest rzędu O(d). W tej pracy prezentujemy: (1) deterministyczny algorytm z wymienionej klasy osiągający podobne rezultaty oraz (2) dowodzimy, że nie istnieje (nawet randomizowany) algorytm z tej klasy, który dawałby lepszą aproksymację. Dla odległości edycyjnej Dycka, Saha zaproponował randomizowaną redukcję z odległości edycyjnej Dycka do klasycznej odległości edycyjnej o koszcie O(log d), gdzie d to odległość edycyjna Dycka. Podamy redukcję deterministyczną której zarówno sfromułowanie jak i udowodnienie poprawności jest prostsze. 
26.04.2023 16:15 David Eppstein University of California, Irvine 
Theoretical computer science The Complexity of Iterated Reversible Computation 
Reversible computation has been studied for over 60 years as a way to evade fundamental physical limits on the power needed for irreversible computational steps, and because quantum computing circuits are necessarily reversible. We study a class of problems based on computing the iterated values of a reversible function. The story leads through Thomason's lollipop algorithm in graph theory, circuit complexity, and reversible cellular automata, to card shuffling, the reflections of light in jewels, and curves on topological surfaces, and involves both PSPACEhard problems and problems with unexpected polynomialtime algorithms. 
20.04.2023 16:45 Piotr Kaliciak 
Combinatorial Optimization Decomposing 4connected planar triangulations into two trees and one path 
A graph is 4connected if no matter which 4 vertices we remove from it, it remains connected. We can decompose every 4connected planar triangulation into a Hamiltonian path and two trees. Moreover, we can decompose any Hamiltonian planar triangulation into two trees and one spanning tree of degree at most 3. These results are bestpossible, this means that we cannot decrease the maximum degree of the first tree. 
20.04.2023 16:00 Kamil Galewski 
Combinatorial Optimization On the discrepancy of circular sequences of reals 
The discrepancy is a function that measures the irregularity of the distribution of a given sequence of real numbers. The authors present a new method to measure discrepancy for sequences of reals lying on a circle of circumference 1, as a more sensitive alternative to the previously known functions. They also show a tight upper bound for this function. 
19.04.2023 16:15 Pat Morin Carleton University 
Theoretical computer science Proof of the Clustered Hadwiger Conjecture 
Hadwiger's Conjecture asserts that every K_{h}minorfree graph is properly (h1)colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every K_{h}minorfree graph is (h1)colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed t≥s, we show that every K_{s,t}minorfree graph is (s+1)colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries. This joint work with Vida Dujmović, Louis Esperet, and David R. Wood. 
13.04.2023 16:45 Łukasz Gniecki 
Combinatorial Optimization Sequences of points on a circle 
Consider a sequence of points a_{1}, a_{2}, a_{3}, ... on a circle with radius 1/(2π), in other words, numbers mod 1. The numbers a_{1}, a_{2}, ..., a_{n} define n intervals with a total length of 1. Denote by M[n,r](a) and m[n,r](a) the largest and the smallest length of consecutive r intervals. We can think of how the values n·M[n, r](a) and n·m[n, r](a) will behave if we go with n to infinity. In particular, for a given sequence a we can find the upper limit of n·M: L[r](a) = limsup n·M[n,r](a) and the lower limit of n·m: l[r](a) = liminf n·m[n,r](a). We can go further and consider the greatest lower bound on L[r](a) (g.l.b. in short) and the lowest upper bound on l[r](a) (l.u.b. in short), overall sequences a. The authors derive bounds on this g.l.b. and l.u.b. and in the case of r = 1, they prove these bounds are tight by giving an example of a sequence a which satisfies these bounds. 
13.04.2023 16:00 Ignacy Buczek 
Combinatorial Optimization 10 Problems for Partitions of Trianglefree Graphs 
The original sparse halves conjecture of Erdos, formed in 1976, states that every trianglefree graph has a subset of n/2 vertices with at most n^{2}/50 edges. As it still remains unsolved, a number of related problems have been stated in order to better understand the problems of partitioning graphs into sparse subsets. In our work, we present and improve the results of some of the existing problems of this kind, and in addition, we state multiple new ones and provide initial results. 
13.04.2023 14:15 Rafał Pyzik, Sebastian Spyrzewski 
Algorytmika Treewidth is NPComplete on Cubic Graphs (and related results) 
Autorzy pracy podają prosty dowód NPzupełności problemu Treewidth, udowadniając jego NPzupełność w klasie dopełnień grafów dwudzielnych. Praca poprawia też rezultat Bodlaedera i Thilikosa z roku 1997 mówiący, że Treewidth jest NPzupełne w grafach o maksymalnym stopniu co najwyżej 9, pokazując NPzupełność w grafach regularnych stopniu 3. 
12.04.2023 16:15 Ruta Mehta University of Illinois at UrbanaChampaign 
Theoretical computer science Competitive division of goods, bads, and mixed: existence, computation, and complexity 
Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This ageold problem, mentioned even in the Bible, arises naturally in a wide range of reallife settings, for example, school seat assignments, partnership dissolution, sharing of satellites, and dividing costs for climate resilience. Division based on competitive equilibrium (CE) has emerged as one of the best mechanisms for this problem. The existence and computability of CE have been extensively studied when all items are disposable goods, while the problem is less explored when some of them are nondisposable chores (bads). In this talk, I will discuss recent algorithmic advances on the computation of CE when each item may be a good, a chore, or both (mixed). I will first consider the case of additive valuations, where when all items are goods, the CE set is wellknown to be captured by convex programming formulations and thereby forms a convex set. In sharp contrast, with chores, the CE set may be nonconvex and disconnected. I will discuss how to handle this nonconvexity through a new exteriorpoint method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinatewise monotone function over linear constraints. Finally, I will discuss recent developments on the exchange setting (barter system) on existence and computational complexity. Based on joint works with Shant Boodaghians, Bhaskar Ray Chaudhury, Jugal Garg, and Peter McGlaughlin. 
05.04.2023 16:15 Ralph Keusch Siemens Mobility CH 
Theoretical computer science A Solution to the 123 Conjecture 
In 2004, Karoński, Łuczak and Thomason conjectured that for each connected graph on at least 3 vertices, it is possible to assign weights from {1,2,3} to the edges such that neighboring vertices always obtain different weighted degrees. Recently, Przybyło verified the conjecture for all graphs G where the minimum degree is sufficiently large, compared to the maximum degree and to an absolute constant. In general, the bestknown bound was by Kalkowski, Karoński, and Pfender from 2011. They proved that such an assignment is always possible with the weight set {1,2,3,4,5}. We present a flowbased strategy to construct vertexcoloring edgeweightings and show how it was first used to shrink the general bound to the set {1,2,3,4} and now led to the confirmation of the conjecture. 
30.03.2023 16:45 Jakub Siuta 
Combinatorial Optimization Listavoiding orientations 
Given a graph G with a set F(v) of forbidden values at each v∈V(G), an Favoiding orientation of G is an orientation in which deg_{+}(v)∉F(v) for each vertex v. Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if F(v)<12deg(v) for each v∈V(G), then G has an Favoiding orientation, and they showed that this statement is true when 12 is replaced by 14. In this paper, we take a step toward this conjecture by proving that if F(v)<⌊13deg(v)⌋ for each vertex v, then G has an Favoiding orientation. Furthermore, we show that if the maximum degree of G is subexponential in terms of the minimum degree, then this coefficient of 13 can be increased to 2^{1/2}−1−o(1) ≈ 0.414. Our main tool is a new sufficient condition for the existence of an Favoiding orientation based on the Combinatorial Nullstellensatz of Alon and Tarsi. 
30.03.2023 16:00 Grzegorz Gawryał 
Combinatorial Optimization Critically paintable, choosable or colorable graphs 
The concept of criticality in graphs was introduced around 1950 to capture the essence of a graph that is not colorable with k colors. Since then, the idea became more and more popular in the literature. We will generalize the results about criticality to list and online list coloring of graphs, using a stronger version of Brooks and Gallai's theorems and prove their implications for graphs drawn on different surfaces, basically showing, that for any surface and k ≥ 5, there are always only finitely many critical graphs for both paintability and choosability. 
30.03.2023 14:15 Łukasz Grobelczyk, Rafał Loska 
Algorytmika This Game is Not Going to Analyze Itself 
Praca analizuje kilka problemów powiązanych z grą przeglądarkową "This Game Is Not Going To Load Itself", w której gracz ma za zadanie przekierować poruszające się kolorowe kwadraty do odpowiedniego ujścia na planszy poprzez ustawianie na niej kolorowych strzałek. Problem decyzyjny czy można wygrać grę jest w klasie $\Sigma_2^P$, jest NPtrudny w wersji offline, a nawet bez możliwości układania strzałek przez gracza jest zarówno NP jak i coNPtrudny. Praca analizuje również problem istnienia strategii wygrywającej. 
29.03.2023 16:15 Alex Scott University of Oxford 
Theoretical computer science On a problem of ElZahar and Erdős 
Two subgraphs A,B of a graph G are anticomplete if they are vertexdisjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by ElZahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number. Second, we look at what happens if we replace the hypothesis that G has large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding K_{t}, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding a complete graph we exclude a complete bipartite graph. Finally, we discuss analogous problems for tournaments. This is joint work with Tung Nguyen and Paul Seymour. 
23.03.2023 16:45 Tomasz Mazur 
Combinatorial Optimization A note on large induced subgraphs with prescribed residues in bipartite graphs 
A known result of Scott is that for every k ≥ 2, there exists a constant c(k) > 0 such that every bipartite nvertex graph G without isolated vertices has an induced subgraph H on at least c(k)·n vertices such that deg_{H}(v) = 1 (mod k) for every vertex v in H. Scott conjectured that c(k) = Ω(1/k). A confirmation of this conjecture is supplied in this paper. 
23.03.2023 16:00 Katzper Michno 
Combinatorial Optimization Dimension and cut vertices: an application of Ramsey theory 
Dimension of a poset P (denoted dim(P)), is the smallest natural number d, such that there are d linear extensions of P s.t. their intersection is exactly P. Among many results regarding the poset dimension, there are quite a few that find relationships between the dimension and some properties of its cover graph. We will discuss one such result, that if for every block B in the cover graph of P, the induced subposet of P with ground set B has dimension at most d, then dim(P) ≤ d+2. We will also show constructions of examples proving that this bound is tight using Product Ramsey Theorem. 
22.03.2023 16:15 Martin Grohe RWTH Aachen 
Theoretical computer science A Deep Dive into the WeisfeilerLeman Algorithm 
The WeisfeilerLeman algorithm is a wellknown combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semidefinite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the WeisfeilerLeman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications. 
 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