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

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

The talk does not require special mathematical background.

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

We build on the work of Ducoffe et al., improving their technique. With our approach the algorithms become simpler and faster, working in Õ(k·V^1-1/d·E) time complexity, where k is the diameter, d is the VC-dimension. Furthermore, it allows us to use the technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we answer a question posed by Bringmann et al., finding a Õ(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.

The Ramsey number R(k) is the minimum n such that every red-blue 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.

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

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

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

1. Julia Biały. slides. (2023).
2. Landon Rabern. A game generalizing Hall's theorem. arXiv:1204.0139. (2012).

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

1. Łukasz Selwa. slides. (2023).
2. Michael Stiebitz, Zsolt Tuza, Margit Voigt. Orientations of Graphs with Prescribed Weighted Out-Degrees. Graphs and Combinatorics 31, 265-280. (2015).

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.

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

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

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

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. two-dimensional 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.

1. Katarzyna Król. slides. (2023).
2. Hao Chen, Jean-Philippe Labbé. Lorentzian Coxeter systems and Boyd-Maxwell ball packings. arXiv:1310.8608. (2012).

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.

1. Jędrzej Kula. slides. (2023).
2. Brian Rabern, Landon Rabern. Playing cards with Vizing's demon. arXiv:2104.04624. (2021).

For a set S of n points in a metric space (X,d) and a parameter t>1, a t-spanner 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 d-dimensional Euclidean space in the regime where t is close to 1. Recent research uncovered tight trade-offs for two important quality measures for t-spanners: the sparsity |E(G)|/n and the lightness w(G)/w(MST(S)). We present an algorithm that constructs a t-spanner for a given set of n points in Euclidean d-space, by sparsifying classical Yao-graphs, that attains a worst-case optimal bound on the weight of the spanner.

In the online model, a sequence of points arrive one-by-one, and we need to maintain a t-spanner for the first n points for all n. By combining sparse Yao-graphs and hierarchical clustering, we obtain an online algorithm that maintains a light spanner and achieves logarithmic competitive ratio compared to the offline optimum.

Last semester I presented a paper “A note on polynomials and f-factors of graphs” by Hamed Shirazi and Jacques Verstraëte, who proved two f-factor theorems using the Combinatorial Nullstellensatz. In this work, authors take a closer look at the same theorems and prove them in a different way.

1. Krzysztof Barański. slides. (2023).
2. András Frank, Lap Chi Lau, Jácint Szabó. A note on degree-constrained subgraphs. Discrete Mathematics. 308(12) 2647-2648. (2008).

k-critical graph is not (k-1)-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.

1. Filip Konieczny. slides. (2023).
2. Horst Sachs, Michael Stiebitz. On constructive methods in the theory of colour-critical graphs. Discrete Mathematics. 74(1-2), 201-226. (1989).

In 1983, Sleator and Tarjan introduced the splay tree, a self-adjusting binary search tree algorithm. Splay trees were conjectured to perform within a constant factor as any offline rotation-based 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 forty-year-old dynamic optimality conjecture since then has used this view, as it greatly simplifies reasoning about binary search trees.

A graph G is k-critical if it is not (k-1)-colorable, but every proper subgraph of G is. Authors improve the bound by Kostochka and Stiebitz for a number of edges in k-critical graphs. The same bound holds for k-list-critical and online k-list-critical graphs improving the bound established by Riasat and Schauz. This result follows from analyzing Alon-Tarsi orientable induced subgraphs satisfying certain conditions.

1. Rafał Pyzik. slides. (2023).
2. H.A. Kierstead, Landon Rabern. Improved lower bounds on the number of edges in list critical and online list critical graphs. Journal of Combinatorial Theory, Series B. 140, 147-170. (2020).

An L-list 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 k-choosable, if all lists L(v) have cardinality k, and G is L-colorable for any assignment of those lists. The author presents a planar graph without 3-cycles that is not 3-choosable. We will also discuss other topics related to list colorings, such as the fact that every planar graph is 5-choosable.

1. Aleksander Katan. slides. (2023).
2. Margit Voigt. A not 3-choosable planar graph without 3-cycles. Discrete Mathematics. 146(1-3), 325-328. (1995).
3. C. Thomassen. Every Planar Graph Is 5-Choosable. Journal of Combinatorial Theory, Series B. 62(1), 180-181. (1994).

In a class of graphs of bounded expansion, for every graph in the class, for every non-empty 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⁴). We also show that a polynomial bound holds more generally for every proper minor-closed class of graphs.

This is joint work with Gwenaël Joret.

The famous Hadwiger's Conjecture states that every k-chromatic 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 k-connected graphs without K_k as a minor. We show that any such graph can't have three (k-2)-cliques that share at most three vertices, which is a generalization of previous results in the area.

1. Rafał Kilar. slides. (2023).
2. Ken-ichi Kawarabayashi, Rong Luo, Jianbing Niu, Cun-Quan Zhang. On the structure of k-connected graphs without Kk-minor. European Journal of Combinatorics. 26(3-4), 293-308. (2005).

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 #P-complete 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.

1. Bartłomiej Błoniarz. slides. (2023).
2. William McCuaig. Pólya's Permanent Problem. Electronic Journal of Combinatorics. 11(1), R79. (2004).

A non-crossing 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 non-crossing 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²) flips are always sufficient.

1. Demian Banakh. slides. (2023).
2. Édouard Bonnet, Tillmann Miltzow. Flip Distance to a Non-crossing Perfect Matching. arXiv:1601.05989. (2016).
3. Guilherme D. da Fonseca, Yan Gerard, Bastien Rivier. On the Longest Flip Sequence to Untangle Segments in the Plane. arXiv:2210.12036. (2022).

We say that a graph G is k-choosable if G has a proper coloring from every list assignment L with |L(v)|=k for every vertex v. A graph G is k-list-critical if it's not k-choosable, 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.

1. Szymon Salabura. slides. (2023).
2. Daniel W. Cranston, Landon Rabern. Edge Lower Bounds for List Critical Graphs, via Discharging. arXiv:1602.02589. (2016).

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 PSPACE-hard problems and problems with unexpected polynomial-time algorithms.

A graph is 4-connected if no matter which 4 vertices we remove from it, it remains connected. We can decompose every 4-connected 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 best-possible, this means that we cannot decrease the maximum degree of the first tree.

1. Piotr Kaliciak. slides. (2023).
2. Kolja Knauer, Torsten Ueckerdt. Decomposing 4-connected planar triangulations into two trees and one path. Journal of Combinatorial Theory, Series B. 134, 88-109. (2019).

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.

1. Kamil Galewski. slides. (2023).
2. Fan Chung, Ron Graham. On the discrepancy of circular sequences of reals. Journal of Number Theory. 164, 52-65. (2016).

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every K_h-minor-free graph is (h-1)-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-minor-free 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.

Consider a sequence of points a₁, a₂, a₃, ... on a circle with radius 1/(2π), in other words, numbers mod 1. The numbers a₁, a₂, ..., 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.

1. Łukasz Gniecki. slides. (2023).
2. N.G. de Bruijn, P. Erdös. Sequences of points on a circle. Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam. 52(1):14-17. (1949).

The original sparse halves conjecture of Erdos, formed in 1976, states that every triangle-free graph has a subset of n/2 vertices with at most n²/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.

1. Ignacy Buczek. slides. (2023).
2. József Balogh, Felix Christian Clemen, Bernard Lidický. 10 Problems for Partitions of Triangle-free Graphs. arXiv:2203.15764. (2022).

Fair division is the problem of allocating a set of items among agents in a fair and efficient manner. This age-old problem, mentioned even in the Bible, arises naturally in a wide range of real-life 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 non-disposable 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 well-known 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 non-convexity through a new exterior-point method to find an approximate CE in polynomial time (FPTAS). This method seems general enough to work with any mathematical formulation that optimizes a coordinate-wise 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.

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 best-known 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 flow-based strategy to construct vertex-coloring edge-weightings 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.

Given a graph G with a set F(v) of forbidden values at each v∈V(G), an F-avoiding 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 F-avoiding 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 F-avoiding 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 F-avoiding orientation based on the Combinatorial Nullstellensatz of Alon and Tarsi.

1. Jakub Siuta. slides. (2023).
2. Peter Bradshaw, Yaobin Chen, Hao Ma, Bojan Mohar, Hehui Wu. List-avoiding orientations. arXiv:2209.09107. (2022).

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.

1. Grzegorz Gawryał. slides. (2023).
2. Ayesha Riasat, Uwe Schauz. Critically paintable, choosable or colorable graphs. Discrete Mathematics. 312 (22), 3373-3383. (2012).

Two subgraphs A,B of a graph G are anticomplete if they are vertex-disjoint 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 El-Zahar 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.

A known result of Scott is that for every k ≥ 2, there exists a constant c(k) > 0 such that every bipartite n-vertex 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.

1. Tomasz Mazur. slides. (2023).
2. Zach Hunter. A note on large induced subgraphs with prescribed residues in bipartite graphs. arXiv:2201.00296. (2022).

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.

1. Katzper Michno. slides. (2023).
2. William T. Trotter, Bartosz Walczak, Ruidong Wang. Dimension and cut vertices: an application of Ramsey theory. arXiv:1505.08162. (2015).

The Weisfeiler-Leman algorithm is a well-known 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 semi-definite 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 Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.

We will discuss selected open problems in discrete mathematics. Two of them are connected to discrete geometry: Piercing families of planar convex sets - finding the minimum number of points needed to pierce a collection of convex sets in the plane, Splitting lines for planar point sets - splitting set of points equally by line through points of this set. Other are graph theory problems: Acyclic edge-coloring of graphs, Two questions on long cycles, and Representations of graphs modulo n.

1. Jakub Dziarkowski. slides. (2022).
2. Research problems. Discrete Mathematics. 257 (2-3), 599-624. (2002).

Algorithmic meta-theorems provide general explanations when and why certain algorithmic problems can be solved efficiently. They are typically formulated in terms of logic (defining the descriptive complexity of the problems) and structural properties of their inputs. A prototypical algorithmic meta-theorem is Courcelle’s Theorem, stating that every graph property definable in monadic second-order logic (MSO) can be decided in linear time on every graph class of bounded treewidth. Similarly, every graph property definable in first-order logic (FO) can be tested efficiently on every nowhere dense graph class.

In this talk I will present recent progress on algorithmic meta-theorems for FO on dense graph classes as well as for logics whose expressive power lies between MSO and FO. The presented results reveal beautiful connections between structural graph theory, classical model theory and algorithmics.

An obstacle is a connected shape on the plane. Given a set of obstacles and a set of points on the plane, we can define a visibility graph on the set of points. Two points are connected by an edge if a straight line between them is disjoint from all the obstacles. We say that the set of points and obstacles is an obstacle representation of the resulting graph. We define the obstacle number of a graph as the minimum number of obstacles needed to represent the graph in an obstacle representation. This parameter was introduced by Alpert, Koch, and Laison in 2011. I will discuss many examples of graphs and their obstacle numbers. I will also present a related notion of convex obstacle number. Moreover, during the presentation, I will state many interesting open problems.

1. Jędrzej Hodori. slides. (2022).
2. Hannah Alpert, Christina Koch, Joshua D. Laison. Obstacle Numbers of Graphs. Discrete & Computational Geometry. 44, 223-244 (2010).

In the classic Euclidean traveling salesman problem, we are given n points in the Euclidean plane, and the goal is to find the shortest round trip that visits all the points. We will discuss some of the key techniques that allowed us to find (conditionally) optimal exact and approximation algorithms for this problem, while the closely related Steiner tree problem seems to resist many similar attempts. We will then turn to the traveling salesman or Steiner tree with "neighborhoods". Here instead of points, we are given a set of affine subspaces, and the goal is to find the shortest round trip or tree that intersects each subspace. It turns out that these problems have a different computational complexity than the classic problems with points: they require a completely novel approach for the hyperplane case, while the other cases remain largely unresolved.

We consider the numerical taxonomy problem of fitting an SxS distance matrix D with a tree metric T. Here T is a weighted tree spanning S where the path lengths in T induce a metric on S. If there is a tree metric matching D exactly, then it is easily found. If there is no exact match, then for some k, we want to minimize the L_k norm of the errors, that is, pick T so as to minimize ||D-T||_k = (Σ_i,jϵS |D(i,j)-T(i,j)|^k) ^1/k.

An evolutionary tree induces a hierarchical classification of species and this is not just tied to biology. Medicine, ecology and linguistics are just some of the fields where this concept appears, and it is even an integral part of machine learning and data science. Fundamentally, if we can approximate distances with a tree, then they are much easier to reason about: many questions that are NP-hard for general metrics can be answered in linear time on tree metrics. In fact, humans have appreciated hierarchical classifications at least since Plato and Aristotle (350 BC).

The numerical taxonomy problem is important in practice and many heuristics have been proposed. In this talk we will review the basic algorithmic theory, results and techniques, for the problem, including the most recent result from FOCS'21 [Vincent Cohen-Addad et al., 2021]. They paint a varied landscape with big differences between different moments, and with some very nice open problems remaining.

- At STOC'93, Farach, Kannan, and Warnow [Martin Farach et al., 1995] proved that under L_∞, we can find the optimal ultrametric. Almost all other variants of the problem are APX-hard

- At SODA'96, Agarwala, Bafna, Farach, Paterson, and Thorup [Richa Agarwala et al., 1999] showed that for any norm L_k, k≥1, if the best ultrametric can be α-approximated, then the best tree metric can be 3α-approximated. In particular, this implied a 3-approximation for tree metrics under L_∞.

- At FOCS'05, Ailon and Charikar [Nir Ailon and Moses Charikar, 2011] showed that for any L_k, k≥1, we can get an approximation factor of O(((log n)(log log n))^1/k) for both tree and ultrametrics. Their paper was focused on the L₁ norm, and they wrote "Determining whether an O(1) approximation can be obtained is a fascinating question".

- At FOCS'21, Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [Vincent Cohen-Addad et al., 2021] showed that indeed a constant factor is possible for L₁ for both tree and ultrametrics. This uses the special structure of L₁ in relation to hierarchies.

- The status of L_k is wide open for 1<k<∞. All we know is that the approximation factor is between Ω(1) and O((log n)(log log n)).

A k-factor of a graph is a spanning k-regular subgraph. Here, we will focus on a more general term: f-factors of graphs, where f is a function assigning to each vertex of the graph a set of integers from 0 to the degree of that vertex, and f-factor is a spanning subgraph of the graph, where for every vertex v, degree of v is an element of f(v). Authors show a necessary condition for such f-factors.

1. Krzysztof Barański. slides. (2022).
2. Hamed Shirazi, Jacques Verstraëte. A Note on Polynomials and f-Factors of Graphs. Electronic Journal of Combinatorics. 15, N22. (2008).

In the Token sliding problem, one starts with a graph and independent sets I_s, I_t. We put k tokens on vertices of I_s and ask whether it's possible to reach I_t after a finite sequence of moves, where 1 move is sliding 1 token along the edge so that no 2 tokens are adjacent at any point. It was shown in 2021 that this problem is W[1]-hard for graphs of girth 4 or less. In this presentation, we will see how the problem becomes Fixed-parameter tractable for the other graphs (girth 5 or more).

1. Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, Sebastian Siebertz. Token sliding on graphs of girth five. arXiv:2205.01009. (2022).
2. Demian Banakh. Token sliding on graphs of girth five. slides. (2022).

A standard Turán problem for a graph F is to determine the maximal number of edges in a graph not containing F as a subgraph. This problem for directed cycles in oriented graphs is trivial, but its various generalizations, when one asks for minimum outdegree or number of other subgraphs, occurred to be hard problems. In particular, finding minimum outdegree (or semidegree) forcing an oriented graph to contain a directed triangle is a Caccetta-Häggkvist conjecture, which is open for 45 years despite numerous partial results. During the talk we will present a solution (obtained with Jan Volec) to a conjecture of Kelly, Kühn and Osthus on the minimum semidegree forcing an oriented graph to contain a directed cycle of any given length at least four. We will also discuss results (obtained jointly with Justyna Jaworska, Bartłomiej Kielak and Tomasz Ślusarczyk) for the generalized Turán problem for directed cycles when one maximizes the number of directed cycles of some other length.

In the most common version of the Lights Out problem, we have an undirected graph G, in which every vertex represents a light either on or off. We can toggle any light, but such action is always followed by all the neighboring lights also switching. The goal is to decide whether it is possible to turn all the lights off. The authors collected many results regarding this problem to present them in a unified framework. For example, they show proof that for any graph with all the lights initially on, it is possible to turn them off. They also study the optimization variants of the problem, such as finding the minimum number of lights we need to toggle, which they show to be NP-hard.

1. Rudolf Fleischer, Jiajin Yu. A Survey of the Game “Lights Out!” In: Brodnik, A., López-Ortiz, A., Raman, V., Viola, A. (eds) Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science, vol 8066. Springer, Berlin, Heidelberg. (2013).
2. Bartłomiej Błoniarz. slides. (2022).

A spanning forest F of a graph G is called a perfect forest if all its components are induced subgraphs of G and the degree of each vertex x in F is odd. It is easy to see that if a connected graph G has a perfect forest, then G is of even order. Interestingly, the opposite implication is also true (A.D. Scott was the first to prove it). Gregory Gutin gave a short proof of this theorem using linear algebra.

1. Gregory Gutin. Note on Perfect Forests. arXiv:1501.01079. (2015).
2. Jakub Dziarkowski. slides. (2022).

Treewidth is a fundamental graph parameter that, informally, characterizes how tree-like a graph is. We give a 2^{O(k^2)}·n^O(1) time algorithm for determining if the treewidth of a given n-vertex graph is at most k and outputting the corresponding tree decomposition. This resolves the long-standing open problem of whether there is a 2^{o(k^3)}·n^O(1) time algorithm for treewidth. In particular, this is the first improvement on the dependency on k in fixed-parameter algorithms for treewidth since the 2^{O(k^3)}·n^O(1) time algorithm given in 1991 by Bodlaender and Kloks, and independently, by Lagergren and Arnborg. We also give a k^O(k/ε)·n^O(1) time (1+ε)-approximation algorithm for treewidth.

Joint work with Daniel Lokshtanov.

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

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

The paper focuses on the representation problem in political elections, using a theorem from number theory. A. Katz's work gives an answer to the question - of whether there exists a way to construct the election list so that it does not matter how many politicians are selected and the politically different groups of the party will be represented?

1. Amoz Kats. Can a party represent its constituency? Public Choice. 44, 453-456. (1984).
2. Julia Biały. slides. (2022).

We consider internal partitions of graphs, which is a partition of V into two sets, such that every vertex has at least half of its neighbors in its own set. Several investigators have raised the conjecture that d-regular graphs always have an internal partition, assuming their set of vertices is big enough. Here we prove this conjecture for d=6. We also investigate the case when |V|=d+4, which leads to some new problems on cubic graphs, and find new families of graphs that don't have an internal partition.

1. Amir Ban, Nati Linial. Internal Partitions of Regular Graphs. arXiv:1307.5246. (2013).
2. Katzper Michno. slides. (2022).

In 1964 Vizing proved that to properly color the edges of a graph G, one need at most ∆+1 colors, where ∆ is the maximum degree of G. In his paper, Vizing actually proves that one can transform any proper edge coloring into a (∆+1)-edge-coloring using only Kempe changes. Soon after his paper, he asked the following question: is an optimal edge-coloring always reachable from any proper edge-coloring using only Kempe changes? Bonamy & al. proved that the conjecture holds for triangle free graphs, following their work, we prove that it holds for all graphs.

Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We prove that every connected graph of even order has a vertex partition into sets inducing subgraphs with all degrees odd, and give bounds for the number of sets of this type required for vertex partitions and vertex covers. We also give results on the partitioning and covering problems for random graphs.

1. A.D. Scott. On Induced Subgraphs with All Degrees Odd. Graphs and Combinatorics. 17, 539-553. (2001).
2. Jakub Siuta. On Induced Subgraphs with All Degrees Odd. slides. (2023).

König's theorem lets us determine the maximum number of pairwise independent edges in a bipartite graph. In the paper, L. Lovász focuses on critical graphs, meaning that if any of their edges are removed, the size of maximum matching diminishes. Considering a certain generalization of the above-mentioned concept, Lovász gives a simple condition that is necessary and sufficient for a graph to be critical. The result is used to solve a conjecture by Erdős regarding strict hypergraph coloring.

1. L. Lovász. A generalization of Kónig's theorem. Acta Mathematica Academiae Scientiarum Hungaricae. 21, 443-446. (1970).
2. Aleksander Katan. A generalization of Konig's theorem. slides. (2023).

We will provide a gentle introduction to the on-going work on constructing a structural theory for graph classes defined by forbidding obstructions definable in logic. The focus will be on monadically stable classes of graphs: classes where one cannot define arbitrary long total orders using a fixed first-order formula. We will review recent advances on characterizing these classes in a purely combinatorial manner, in particular through a game model: the Flipper game.

In the extremal graph theory, there are many unsolved problems related to the finding of sparse subsets in graphs. The most famous one, stated by Erdos in 1976, asks whether every triangle-free graph contains n/2 vertices that span at most 1/50 n² edges. In our work we consider, and successfully prove, a modified version of this theorem which conjectures that every K₄-free graph has n/2 vertices spanning at most 1/18 n² edges. This bound is tight, as the balanced blow-up of a triangle is an extreme example. We achieve the proof by strengthening some of the previous results and by stating some new arguments which show that the only K₄-free graph which has at least 1/18 n² edges in every half is the blow-up of a triangle.

1. Christian Reiher. K₄-free graphs have sparse halves. arXiv:2108.07297. (2021).
2. Hubert Zięba. K₄-free graphs have sparse halves. slides. (2022).

Ando conjecture states that we can partition vertices of any cubic graph into two parts that induce isomorphic subgraphs. We show that this conjecture is true for sufficiently large connected cubic graphs. In the proof, we use probabilistic methods with recoloring arguments.

1. S. Das, A. Pokrovskiy, B. Sudakov. Isomorphic bisections of cubic graphs. Journal of Combinatorial Theory, Series B. 51, 465-481. (2021).
2. Łukasz Selwa. Isomorphic bisections of cubic graphs. slides. (2022).