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

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

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

The talk does not require special mathematical background.

11.10.2023 16:15
Krzysztof Potępa
Jagiellonian University
Informatyka Teoretyczna
Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs

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

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

This is joint work with Lech Duraj and Filip Konieczny.

18.10.2023 16:15
Marcelo Campos
University of Oxford
Informatyka Teoretyczna
An exponential improvement for diagonal Ramsey

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

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

25.10.2023 16:15
Torsten Mütze
University of Warwick
Informatyka Teoretyczna
A book proof of the middle levels theorem

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

08.11.2023 16:15
Informatyka Teoretyczna
TBA - 2023.11.08
15.11.2023 16:15
Informatyka Teoretyczna
TBA - 2023.11.15
22.11.2023 16:15
Informatyka Teoretyczna
TBA - 2023.11.22
29.11.2023 16:15
Informatyka Teoretyczna
TBA - 2023.11.29
06.12.2023 16:15
Informatyka Teoretyczna
TBA - 2023.12.06
13.12.2023 16:15
Informatyka Teoretyczna
TBA - 2023.12.13
20.12.2023 16:15
Informatyka Teoretyczna
TBA - 2023.12.20
03.01.2024 16:15
Informatyka Teoretyczna
TBA - 2024.01.03
10.01.2024 16:15
Informatyka Teoretyczna
TBA - 2024.01.10
17.01.2024 16:15
Informatyka Teoretyczna
TBA - 2024.01.17
24.01.2024 16:15
Informatyka Teoretyczna
TBA - 2024.01.24
28.02.2024 16:15
Informatyka Teoretyczna
TBA - 2024.02.28
06.03.2024 16:15
Informatyka Teoretyczna
TBA - 2024.03.06
13.03.2024 16:15
Informatyka Teoretyczna
TBA - 2024.03.13

Poprzednie referaty

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

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

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

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

  1. Ł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).
14.06.2023 16:15
Fabrizio Frati
Università Roma Tre
Informatyka Teoretyczna
Currents Trends and Hot Problems in Graph Drawing

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

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

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

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

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

31.05.2023 16:15
Ola Svensson
École Polytechnique Fédérale de Lausanne
Informatyka Teoretyczna
The Price of Explainability for Clustering
Given a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio between the cost of the best explainable clusterings to that of the best clusterings.
We show that the price of explainability for k-medians is at most 1+Hk−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 lower-order terms. We also improve the price of explainability for the k-means 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 k-medians and k-means cannot be approximated better than O(ln k), under standard complexity-theoretic conjectures. This essentially settles the approximability of explainable k-medians and leaves open the intriguing possibility to get significantly better approximation algorithms for k-means 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
Optymalizacja Kombinatoryczna
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. 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).
25.05.2023 16:00
Jędrzej Kula
Optymalizacja Kombinatoryczna
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.

  1. Jędrzej Kula. slides. (2023).
  2. Brian Rabern, Landon Rabern. Playing cards with Vizing's demon. arXiv:2104.04624. (2021).
24.05.2023 16:15
Csaba Tóth
California State University, Northridge
Informatyka Teoretyczna
Optimal spanners in Euclidean spaces

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.

18.05.2023 16:45
Krzysztof Barański
Optymalizacja Kombinatoryczna
A note on degree-constrained subgraphs

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).
18.05.2023 16:00
Filip Konieczny
Optymalizacja Kombinatoryczna
On constructive methods in the theory of colour-critical graphs

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).
17.05.2023 16:15
John Iacono
Université Libre de Bruxelles
Informatyka Teoretyczna
The pursuit of the dynamic optimality conjecture via the geometry of binary search trees

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.

11.05.2023 16:45
Rafał Pyzik
Optymalizacja Kombinatoryczna
Improved lower bounds on the number of edges in list critical and online list critical graphs

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).
11.05.2023 16:00
Aleksander Katan
Optymalizacja Kombinatoryczna
A not 3-choosable planar graph without 3-cycles

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).
10.05.2023 16:15
Clément Rambaud
École Normale Supérieure, PSL Paris
Informatyka Teoretyczna
Neighborhood complexity of planar graphs

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(r4). 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.

04.05.2023 16:45
Rafał Kilar
Optymalizacja Kombinatoryczna
On the structure of k-connected graphs without K_k-minor

The famous Hadwiger's Conjecture states that every k-chromatic graph must contain the clique Kk as a minor. It remains unproven for k>6. Motivated by this conjecture we can ask about the structure of k-connected graphs without Kk 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).
04.05.2023 16:00
Bartłomiej Błoniarz
Optymalizacja Kombinatoryczna
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 #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).
27.04.2023 16:45
Demian Banakh
Optymalizacja Kombinatoryczna
Flip distance to a non-crossing perfect matching

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 θ(n2) 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).
27.04.2023 16:00
Szymon Salabura
Optymalizacja Kombinatoryczna
Edge lower bounds for list critical graphs, via discharging

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).
27.04.2023 14:15
Justyna Jaworska, Jakub Siuta
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
Informatyka Teoretyczna
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 PSPACE-hard problems and problems with unexpected polynomial-time algorithms.

20.04.2023 16:45
Piotr Kaliciak
Optymalizacja Kombinatoryczna
Decomposing 4-connected planar triangulations into two trees and one path

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).
20.04.2023 16:00
Kamil Galewski
Optymalizacja Kombinatoryczna
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.

  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).
19.04.2023 16:15
Pat Morin
Carleton University
Informatyka Teoretyczna
Proof of the Clustered Hadwiger Conjecture

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

13.04.2023 16:45
Łukasz Gniecki
Optymalizacja Kombinatoryczna
Sequences of points on a circle

Consider a sequence of points a1, a2, a3, ... on a circle with radius 1/(2π), in other words, numbers mod 1. The numbers a1, a2, ..., an 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).
13.04.2023 16:00
Ignacy Buczek
Optymalizacja Kombinatoryczna
10 Problems for Partitions of Triangle-free Graphs

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 n2/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).
13.04.2023 14:15
Rafał Pyzik, Sebastian Spyrzewski
Treewidth is NP-Complete on Cubic Graphs (and related results)
Autorzy pracy podają prosty dowód NP-zupełności problemu Treewidth, udowadniając jego NP-zupełność w klasie dopełnień grafów dwudzielnych. Praca poprawia też rezultat Bodlaedera i Thilikosa z roku 1997 mówiący, że Treewidth jest NP-zupełne w grafach o maksymalnym stopniu co najwyżej 9, pokazując NP-zupełność w grafach regularnych stopniu 3.
12.04.2023 16:15
Ruta Mehta
University of Illinois at Urbana-Champaign
Informatyka Teoretyczna
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 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.

05.04.2023 16:15
Ralph Keusch
Siemens Mobility CH
Informatyka Teoretyczna
A Solution to the 1-2-3 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 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.

30.03.2023 16:45
Jakub Siuta
Optymalizacja Kombinatoryczna
List-avoiding orientations

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 21/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).
30.03.2023 16:00
Grzegorz Gawryał
Optymalizacja Kombinatoryczna
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.

  1. Grzegorz Gawryał. slides. (2023).
  2. Ayesha Riasat, Uwe Schauz. Critically paintable, choosable or colorable graphs. Discrete Mathematics. 312 (22), 3373-3383. (2012).
30.03.2023 14:15
Łukasz Grobelczyk, Rafał Loska
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 NP-trudny w wersji offline, a nawet bez możliwości układania strzałek przez gracza jest zarówno NP- jak i coNP-trudny. Praca analizuje również problem istnienia strategii wygrywającej.
29.03.2023 16:15
Alex Scott
University of Oxford
Informatyka Teoretyczna
On a problem of El-Zahar and Erdős

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 Kt, 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
Optymalizacja Kombinatoryczna
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 n-vertex graph G without isolated vertices has an induced subgraph H on at least c(k)·n vertices such that degH(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).
23.03.2023 16:00
Katzper Michno
Optymalizacja Kombinatoryczna
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.

  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).
22.03.2023 16:15
Martin Grohe
RWTH Aachen
Informatyka Teoretyczna
A Deep Dive into the Weisfeiler-Leman Algorithm

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.

16.03.2023 16:00
Jakub Dziarkowski
Optymalizacja Kombinatoryczna
Research problems

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).
15.03.2023 16:15
Sebastian Siebertz
Universität Bremen
Informatyka Teoretyczna
Advances in algorithmic meta-theorems

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.

09.03.2023 16:00
Jędrzej Hodor
Optymalizacja Kombinatoryczna
Obstacle Number of Graphs

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).
08.03.2023 16:15
Sándor Kisfaludi-Bak
Aalto University
Informatyka Teoretyczna
On geometric variants of TSP and Steiner tree

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.

01.03.2023 16:15
Mikkel Thorup
University of Copenhagen
Informatyka Teoretyczna
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics)

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 Lk 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 Lk, k1, 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 Lk, k1, 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 L1 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 L1 for both tree and ultrametrics. This uses the special structure of L1 in relation to hierarchies.

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

26.01.2023 16:45
Krzysztof Barański
Optymalizacja Kombinatoryczna
A note on polynomials and f-factors of graphs

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).
26.01.2023 16:00
Demian Banakh
Optymalizacja Kombinatoryczna
Token sliding on graphs of girth five

In the Token sliding problem, one starts with a graph and independent sets Is, It. We put k tokens on vertices of Is and ask whether it's possible to reach It 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).
26.01.2023 14:15
Grzegorz Gawryał, Szymon Salabura
TSP in a Simple Polygon
Problem komiwojażera (TSP) jest jednym z najbardziej popularnych problemów optymalizacyjnych w algorytmice. Jest on NP-trudny, nawet wtedy, gdy graf na wejściu jest grafem odległości euklidesowych między danymi punktami na płaszczyźnie. Autorzy wprowadzają nowy wariant tego problemu - TSP w wielokącie prostym, w którym to problemie należy znaleźć najkrótszą trasę nie wychodzącą poza wielokąt i odwiedzającą pewien zbiór punktów w tym wielokącie, w dowolnej kolejności. Autorzy najpierw pokazują, jak zastosować ogólniejszy i dość skomplikowany algorytm Marxa, Pilipczuka i Pilipczuka do tego problemu, uzyskując złożoność poly(n,m) + 2(O(sqrt(n) log n)), a następnie prezentują własny, znacznie prostszy algorytm rozwiązujący ten wariant TSP w tej samej złożoności.
25.01.2023 16:15
Andrzej Grzesik
Informatyka Teoretyczna
Turán-type problems for directed cycles

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.

25.01.2023 12:14
Krzysztof Barański
Podstawy Informatyki
A verified framework for higher-order uncurrying optimizations by Zaynah Dargaye and Xavier Leroy
Function uncurrying is an important optimization for the efficient execution of functional programming languages. This optimization replaces curried functions by uncurried, multiple-argument functions, while preserving the ability to evaluate partial applications. First-order uncurrying (where curried functions are optimized only in the static scopes of their definitions) is well understood and implemented by many compilers, but its extension to higher-order functions (where uncurrying can also be performed on parameters and results of higher-order functions) is challenging. This article develops a generic framework that expresses higher-order uncurrying optimizations as type-directed insertion of coercions, and prove its correctness. The proof uses step-indexed logical relations and was entirely mechanized using the Coq proof assistant.
19.01.2023 16:45
Bartłomiej Błoniarz
Optymalizacja Kombinatoryczna
A Survey of the Game “Lights Out!"

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).
19.01.2023 16:00
Jakub Dziarkowski
Optymalizacja Kombinatoryczna
Note on Perfect Forests

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).
19.01.2023 14:15
Bartłomiej Wacławik, Krzysztof Ziobro
Tiny Pointers
Praca wprowadza nowe pojęcie: wskaźniczek. Wskaźniczek jest obiektem, który pozwala na 
dostęp do jednego z n miejsc w pamięci, jednocześnie używając znacząco mniej niż log(n)
bitów. Jest to możliwe dzięki użyciu wprowadzonej w pracy tablicy dereferencyjnej, która
pozwala dla danego klucza k (z dużym prawdopodobieństwem) zaalokować komórkę pamięci
zwracając wskaźniczek, który razem z kluczem pozwalaja uzyskać dostęp do zaalokowanej
komórki w czasie stałym. Dodatkowo autorzy podają przykłady zastosowań w popularnych
strukturach danych, których rozmiar można zredukować dzięki zastąpieniu klasycznych 
wskaźników wskaźniczkami. Wśród tych przykładów znajdują się między innymi drzewa BST
oraz słowniki o stałej pojemności. 
18.01.2023 16:15
Tuukka Korhonen
University of Bergen
Informatyka Teoretyczna
An improved parameterized algorithm for treewidth

Treewidth is a fundamental graph parameter that, informally, characterizes how tree-like a graph is. We give a 2O(k^2)·nO(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 2o(k^3)·nO(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 2O(k^3)·nO(1) time algorithm given in 1991 by Bodlaender and Kloks, and independently, by Lagergren and Arnborg. We also give a kO(k/ε)·nO(1) time (1+ε)-approximation algorithm for treewidth.

Joint work with Daniel Lokshtanov.

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

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

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

12.01.2023 16:45
Julia Biały
Optymalizacja Kombinatoryczna
Can a party represent its constituency?

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).
12.01.2023 16:00
Katzper Michno
Optymalizacja Kombinatoryczna
Internal Partitions of Regular Graphs

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).
12.01.2023 14:15
Ignacy Buczek, Tomasz Buczyński
List Colouring Trees in Logarithmic Space
Dla danego n-wierzchołkowego grafu G = (V, E) oraz listy L(v) ⊆ {1, ..., n} dozwolonych kolorów dla każdego wierzchołka v ∊ V, kolorowanie listowe jest kolorowaniem wierzchołkowym c grafu G spełniającym c(v) ∊ L(v) dla każdego v. Autorzy pracy dowodzą, że problem kolorowania listowego n-wierzchołkowych drzew może być rozwiązany za pomocą deterministycznej maszyny Turinga używającej O(log n) bitów na taśmie roboczej.
11.01.2023 16:15
Jonathan Narboni
Informatyka Teoretyczna
Vizing's Conjecture Holds

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.

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

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).
05.01.2023 16:00
Aleksander Katan
Optymalizacja Kombinatoryczna
A generalization of Konig's theorem

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).
04.01.2023 16:15
Michał Pilipczuk
University of Warsaw
Informatyka Teoretyczna
Flipper games for monadically stable classes of graphs

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.

04.01.2023 12:14
Sebastain Spyrzewski
Podstawy Informatyki
A characterization of lambda-terms transforming numerals by PAWEŁ PARYS
It is well known that simply typed λ-terms can be used to represent numbers, as well as some other data types. We show that λ-terms of each fixed (but possibly very complicated) type can be described by a finite piece of information (a set of appropriately defined intersection types) and by a vector of natural numbers. On the one hand, the description is compositional:
having only the finite piece of information for two closed λ-terms M and N, we can determine its counterpart for M N, and a linear transformation that applied to the vectors of numbers for M and N gives us the vector for M N. On the other hand, when a λ-term represents a natural number, then this number is approximated by a number in the vector corresponding to this λ-term. As a consequence, we prove that in a λ-term of a fixed type, we can store only a fixed number of natural numbers, in such a way that they can be extracted using λ-terms. More precisely, while representing k numbers in a closed λ-term of some type, we
only require that there are k closed λ-terms M1, . . . , M k such that M i takes as argument the λ-term representing the k-tuple, and returns the i-th number in the tuple (we do not require that, using λ-calculus, one can construct the representation of the k-tuple out of the k numbers in the tuple). Moreover, the same result holds when we allow that the numbers can be extracted approximately, up to some error (even when we only want to know whether a set is bounded or not). All the results remain true when we allow the Y combinator (recursion) in our λ-terms, as well as uninterpreted constants.
22.12.2022 16:45
Ignacy Buczek
Optymalizacja Kombinatoryczna
K4-free graphs have sparse halves

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 n2 edges. In our work we consider, and successfully prove, a modified version of this theorem which conjectures that every K4-free graph has n/2 vertices spanning at most 1/18 n2 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 K4-free graph which has at least 1/18 n2 edges in every half is the blow-up of a triangle.

  1. Christian Reiher. K4-free graphs have sparse halves. arXiv:2108.07297. (2021).
  2. Hubert Zięba. K4-free graphs have sparse halves. slides. (2022).
22.12.2022 16:00
Łukasz Selwa
Optymalizacja Kombinatoryczna
Isomorphic bisections of cubic graphs

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).
22.12.2022 14:15
Kamil Galewski, Piotr Kaliciak
Lower Bounds on Retroactive Data Structures