Combinatorial Optimization Seminar

Dr Bartłomiej Bosek

Thursday 16:15 - 17:45, classroom 0174

This is an MA seminar, whose theme relates to combinatorial optimization. In particular, we are interested in the following topics:

  1. The advanced algorithms contained in graphs associations (including bipartite) in cases unweighted and weighted edges.

  2. The problems of constructing on-line matching in bipartite graphs, AdWords Problem - the optimum solution, randomized.

  3. Algorithmic aspects of unichain partition of products partial orders.

Previous seminars

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

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

  1. Zhiguo Li, Zeling Shao, Fedor Petrov, Alexey Gordeev. The Alon-Tarsi Number of A Toroidal Grid. arXiv:1912.12466. (2019).
  2. Łukasz Gniecki. slides. (2024).
06.06.2024 16:45
Jędrzej Hodor
Planarity and dimension

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

  1. Jędrzej Hodor. slides. (2024).
16.05.2024 16:45
Rafał Pyzik
The Alon-Tarsi number of K3,3-minor-free graphs

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

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

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

  1. Ron Aharoni, Penny Haxell. Hall's theorem for hypergraphs. J. Graph Theory, 35: 83-88. (2000).
  2. Filip Konieczny. slides. (2024).
09.05.2024 16:45
Aleksander Katan
Dynamic monopolies in directed graphs: The spread of unilateral influence in social networks

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

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

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

  1. Jacob Turner. Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited. arXiv:2004.08636. (2020).
  2. Ignacy Buczek. slides. (2024).
25.04.2024 16:45
Sebastian Spyrzewski
Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited

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

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

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

  1. Katarzyna Kępińska. slides. (2024).
18.04.2024 16:45
Jan Klimczak
3-Colorability of 4-Regular Hamiltonian Graphs

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

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

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

  1. Mario E. Valencia-Pabon. Revisiting Tucker's Algorithm to Color Circular-Arc Graphs. Electronic Notes in Discrete Mathematics. 7, 198-201. (2001).
  2. Maksym Zub. slides. (2024).
11.04.2024 16:45
Mateusz Hurkała
The two possible values of the chromatic number of a random graph

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

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

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

  1. Christine Eisenbeis, Sylvain Lelait , Bruno P Marmol. Circular-arc Graph Coloring and Unrolling. INRIA. RR-3336, (1998).
  2. Rafał Kajca. slides. (2024).
04.04.2024 16:45
Filip Jasionowicz
The Lefthanded Local Lemma Characterizes Chordal Dependency Graphs

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

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

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

  1. Richard Arratia, Béla Bollobás, Don Coppersmith, and Gregory B. Sorkin. Euler circuits and DNA sequencing by hybridization. Discrete Applied Mathematics. 104(1-3), 63-96. (2000).
  2. Agata Margas. slides. (2024).
21.03.2024 16:45
Kamil Galewski
Shannon Entropy of Ramsey Graphs with up to Six Vertices

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

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

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

  1. Kristóf Bérczi, Yusuke Kobayashi. An algorithm for identifying cycle-plus-triangles graphs. Discrete Applied Mathematics. 226. 10-16. (2017).
  2. Piotr Kaliciak. slides. (2024).
14.03.2024 16:45
Michał Mizołek
An O(n^2) algorithm for coloring proper circular arc graphs

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

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

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

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

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

  1. Ron Aharoni, Eli Berger, Maria Chudnovsky, Frédéric Havet, Zilin Jiang. Cooperative colorings of trees and of bipartite graphs. arXiv:1806.06267. (2018).
  2. Bartłomiej Błoniarz. slides. (2024).
29.02.2024 16:00
Bartłomiej Bosek
Some open problems from combinatorics and algorithmics

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

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

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

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

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

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

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

  1. Matthieu Rosenfeld. Another approach to non-repetitive colorings of graphs of bounded degree. arXiv:2006.09094. (2020).
  2. Katzper Michno. Another approach to non-repetitive colorings of graphs of bounded degree. slides. (2024).
18.01.2024 16:45
Milana Kananovich
A Linear Recognition Algorithm for Cographs. A Simple Linear Time LexBFS Cograph Recognition Algorithm.

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

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

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

  1. Zdeněk Dvořák, Sergey Norin, Luke Postle. List coloring with requests. arXiv:1612.08698. (2016).
  2. Sebastian Spyrzewski. List coloring with requests. slides. (2024).
11.01.2024 16:45
Aleksander Katan
Countable graphs are majority 3-choosable

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

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

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

  1. Yangyan Gu, Xuding Zhu. The Alon-Tarsi number of planar graphs - a simple proof. arXiv:2203.16308. (2022).
  2. Łukasz Gniecki. The Alon Tarsi Number of Planar Graphs - a Simple Proof. slides. (2024).
21.12.2023 16:45
Kamil Galewski
On two generalizations of the Alon–Tarsi polynomial method

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

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

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

  1. Ignacy Buczek. A note on computer-assisted proofs in flag algebras. slides. (2023).
14.12.2023 16:00
Jędrzej Hodor
Wythoff's game

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

  1. W. A. Wythoff. A modification of the game of nim. Nieuw Archief voor Wiskunde. 2(7). 199-202. (1907).
  2. Jędrzej Hodor. Wythoff’s game. slides. (2023).
07.12.2023 16:00
Piotr Kaliciak
Hat guessing numbers of strongly degenerate graphs

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

  1. Charlotte Knierim, Anders Martinsson, Raphael Steiner. Hat guessing numbers of strongly degenerate graphs. arXiv:2112.09619. (2021).
  2. Piotr Kaliciak. Hat guessing numbers of strongly degenerate graphs. slides. (2023).
30.11.2023 16:45
Jan Klimczak
On the equitable distribution of points on the circle

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

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

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

  1. Niv Buchbinder, D. Segev, Yevgeny Tkach. Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. Algorithmica. 81, 1781-1799. (2019)
  2. Rafał Pyzik. Online Algorithms for Maximum Cardinality Matching with Edge Arrivals slides. (2023).
23.11.2023 16:45
Izabela Tylek
Any 7-chromatic graph has a K7 or K4,4 as a minor

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

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

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

  1. Wei-Kuan Shih, Wen-Lian Hsu. An O(n1.5) algorithm to color proper circular arcs. Discrete Applied Mathematics. 25(3), 321-323. (1989).
  2. Justyna Jaworska. An O(n1.5) algorithm to color proper circular arcs. slides. (2023).
16.11.2023 16:45
Maciej Sanocki
Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm

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

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

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

  1. Katarzyna Kępińska. On Two problems of Defective Choosability of Graphs. slides. (2023).
09.11.2023 16:00
Karolina Okrasa
Warsaw University of Technology
Graph Homomorphisms: From Structure to Algorithms

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

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

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

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

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

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

  1. Bruno Courcelle. Circle graphs and monadic second-order logic. Journal of Applied Logic. 6(3). 416-442. (2008).
  2. Mikołaj Kot. Circle graphs and monadic second-order logic. slides. (2023).
19.10.2023 16:45
Maksym Zub
A note concerning the Grundy and b-chromatic number of graphs

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

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

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

  1. M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou. SIAM Journal on Algebraic Discrete Methods. 1(2). 216-227. (1980).
  2. Jakub Fedak. The Complexity of Coloring Circular Arcs and Chords. slides. (2023).
12.10.2023 16:00
Bartłomiej Błoniarz
(Some of) the many uses of Eulerian graphs in graph theory (plus some applications)

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

  1. Bartłomiej Błoniarz. (Some of) the many uses of Eulerian graphs in graph theory (plus some applications). slides. (2023).
  2. H. Fleischner. (Some of) the many uses of Eulerian graphs in graph theory (plus some applications) Discrete Mathematics 230(1-3). 23-43. (2001).
05.10.2023 16:00
Bartłomiej Bosek
Some open problems from combinatorics and algorithmics

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

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

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

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

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

  1. Michael Stiebitz, Zsolt Tuza, Margit Voigt. Orientations of Graphs with Prescribed Weighted Out-Degrees. Graphs and Combinatorics 31, 265-280. (2015).
25.05.2023 16:45
Katarzyna Król
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. Ball Packing. 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
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. Playing cards with Vizing's demon. slides. (2023).
  2. Brian Rabern, Landon Rabern. Playing cards with Vizing's demon. arXiv:2104.04624. (2021).
18.05.2023 16:45
Krzysztof Barański
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. A note on degree-constrained subgraphs. 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
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. On constructive methods in the theory of colour-critical graphs. 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).
11.05.2023 16:45
Rafał Pyzik
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. Improved lower bounds on the number of edges in list critical and online list critical graphs. 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
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. A not 3-choosable planar graph without 3-cycles. 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).
04.05.2023 16:45
Rafał Kilar
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. On the structure of k-connected graphs without Kk-minor. 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
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. Pólya's Permanent Problem. 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
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. Flip distance to a non-crossing perfect matching. 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
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. Edge lower bounds for list critical graphs, via discharging. slides. (2023).
  2. Daniel W. Cranston, Landon Rabern. Edge Lower Bounds for List Critical Graphs, via Discharging. arXiv:1602.02589. (2016).
20.04.2023 16:45
Piotr Kaliciak
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. Decomposing 4-connected planar triangulations into two trees and one path. 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
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. On the discrepancy of circular sequences of reals. slides. (2023).
  2. Fan Chung, Ron Graham. On the discrepancy of circular sequences of reals. Journal of Number Theory. 164, 52-65. (2016).
13.04.2023 16:45
Łukasz Gniecki
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. Sequences of points on a circle. 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
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. 10 Problems for Partitions of Triangle-free Graphs. slides. (2023).
  2. József Balogh, Felix Christian Clemen, Bernard Lidický. 10 Problems for Partitions of Triangle-free Graphs. arXiv:2203.15764. (2022).
30.03.2023 16:45
Jakub Siuta
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. List-avoiding orientations. 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ł
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ł. Critically paintable, choosable or colorable graphs. slides. (2023).
  2. Ayesha Riasat, Uwe Schauz. Critically paintable, choosable or colorable graphs. Discrete Mathematics. 312 (22), 3373-3383. (2012).
23.03.2023 16:45
Tomasz Mazur
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. A note on large induced subgraphs with prescribed residues in bipartite graphs. 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
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. Dimension and cut vertices: an application of Ramsey theory. slides. (2023).
  2. William T. Trotter, Bartosz Walczak, Ruidong Wang. Dimension and cut vertices: an application of Ramsey theory. arXiv:1505.08162. (2015).
16.03.2023 16:00
Jakub Dziarkowski
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. Research problems. Discrete Mathematics. 257 (2-3), 599-624. (2002).
09.03.2023 16:00
Jędrzej Hodor
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 Hodor. Obstacle Number of Graphs. slides. (2023).
  2. Hannah Alpert, Christina Koch, Joshua D. Laison. Obstacle Numbers of Graphs. Discrete & Computational Geometry. 44, 223-244 (2010).
26.01.2023 16:45
Krzysztof Barański
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. A note on polynomials and f-factors of graphs. slides. (2023).
  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
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).
19.01.2023 16:45
Bartłomiej Błoniarz
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. A Survey of the Game “Lights Out!" slides. (2023).
19.01.2023 16:00
Jakub Dziarkowski
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. Note on Perfect Forests. slides. (2023).
12.01.2023 16:45
Julia Biały
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. Can a party represent its constituency? slides. (2023).
12.01.2023 16:00
Katzper Michno
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. Internal Partitions of Regular Graphs. slides. (2023).
05.01.2023 16:45
Jakub Siuta
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
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).
22.12.2022 16:45
Ignacy Buczek
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
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).
15.12.2022 16:45
Hubert Zięba
The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture

The 1-2-3 conjecture asserts that for every connected simple graph of order at least 3 edges can be weighted with 1,2 and 3 so that each pair of adjacent has different weighted degrees. We consider a modified version of this conjecture with 1,2 weights only. By using f-factors modulo k of the graph, we prove it for non-bipartite (6𝛘(G)-5)-edge-connected graphs and completely characterize bipartite graphs having this property.

  1. Carsten Thomassen, Yezhou Wu, Cun-Quan Zhang. The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture. Journal of Combinatorial Theory, Series B. 121, 308-325. (2016).
  2. Hubert Zięba. The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture. slides. (2022).
15.12.2022 16:00
Tomasz Mazur
Improved lower bound for the list chromatic number of graphs with no Kt minor

Hadwiger's conjecture is an important conjecture in graph theory which states that every graph without a Kt-minor is (t-1)-colorable. This conjecture does not extend to list colorings, but Kawarabayashi and Mohar (2007) conjectured that there exists a constant c such that every graph with no Kt-minor has a list chromatic number at most c·t. More specifically, they conjectured that c = 3/2 is sufficient. Refuting the latter conjecture, we prove using the probabilistic method that there exist graphs with no Kt-minor with list chromatic number at least (2-o(1))·t, and hence c 2 is necessary. This improves the previous best-known lower bound by Barát, Joret, and Wood (2011), who proved that c ≥ 4/3.

  1. Raphael Steiner. Improved lower bound for the list chromatic number of graphs with no Kt minor. arXiv:2110.09403. (2021).
  2. Tomasz Mazur. Improved lower bound for the list chromatic number of graphs with no Kt minor. slides. (2022).
08.12.2022 16:45
Grzegorz Gawryał
On topological aspects of orientations

Constrained graph orientation problem deals with directing graph edges such that graph vertices fulfills some conditions. Here, we are focusing on contant indegree orientations of maximal planar and similar classes of graphs. We analyse the relationship between such orientations and other combinatorial properties of these graphs, including the existence of particular decompositions into trees given by the famous Nash William's theorem.

  1. H. de Fraysseix, P. Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics. 229(1-3), 57-72. (2001).
  2. Grzegorz Gawryał. On topological aspects of orientations. slides. (2022).
08.12.2022 16:00
Rafał Kilar
Minimal Non-Two-Colorable Hypergraphs and Minimal Unsatisfiable Formulas

It is known that the number of edges in a minimal non-2-colorable hypergraph is at least as high as the number of its vertices. We show the link between this and the fact that a minimal unsatisfiable CNF formula with n variables must contain at least n + 1 clauses. We show different proof of these facts and give infinite versions. We also analyze the structure of minimal unsatisfiable CNF formulas with exactly n variables and n + 1 clauses.

  1. Ron Aharoni, Nathan Linial. Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. Journal of Combinatorial Theory, Series A. 4(2), 196-204. (1986).
  2. Rafał Kilar. Minimal Non-Two-Colorable Hypergraphs and Minimal Unsatisfiable Formulas. slides. (2022).
01.12.2022 16:45
Szymon Salabura
Farey sequence and Graham’s conjectures

The Farey sequence Fn is the set of rational numbers a/b with 0 ≤ a ≤ b ≤ n and gcd(a,b) = 1. In 1970, Graham proposed the following conjecture. Let a1, a2, ..., an be distinct positive integers. There exist indices i ≠ j, such that we have ai/gcd(ai,aj) ≥ n. In the paper, the authors show interesting properties of Farey sequence sets and how they are closely related to Graham's problems.

  1. Liuquan Wang. Farey sequence and Graham's conjectures. arXiv:2005.04429. (2020).
  2. Szymon Salabura. Farey sequence and Graham’s conjectures. slides. (2022).
01.12.2022 16:00
Katarzyna Kępińska
Color-Critical Graphs on a Fixed Surface

A graph G is k-color-critical if G is not (k-1)-colorable, but every proper subgraph is. For S, an orientable surface other than the sphere, there are infinitely many k-color-critical graphs if and only if 2<k<6. For k>4 there is the polynomial algorithm for deciding if a graph can be colored with k colors. In this paper, the authors prove those theorems and show some results for list coloring.

  1. Carsten Thomassen. Color-Critical Graphs on a Fixed Surface. Journal of Combinatorial Theory, Series B. 70(1), 67-100. (1997).
  2. Katarzyna Kępińska. Color-Critical Graphs on a Fixed Surface. slides. (2022).
24.11.2022 16:45
Filip Konieczny
Factorizing regular graphs

A q-factor of a k-regular graph is its q-regular subgraph covering all vertices. q-factorization is a partition of edges of a graph into disjoint q-factors. For q-factorization to exist it is necessary that q\mid k. It was proven that for even q the converse is also true - qd-regular graph has a q-factorization. The paper investigates when qd-regular graph with odd q admits q-factorization, given additional assumptions like planarity and/or high connectivity.

  1. Carsten Thomassen. Factorizing regular graphs. Journal of Combinatorial Theory, Series B. 141, 343-351. (2020).
  2. Filip Konieczny. Factorizing regular graphs. slides. (2022).
24.11.2022 16:00
Hubert Dej
On the Gap Structure of Sequences of Points on a Circle

The problem of determining a sequence of points on the unit circle is considered, such that at any time t the lengths of the segments (sticks) resulting from splitting the circle at the locations set by the first t points are as equal as possible. The authors consider the sequence xk=lg(2k-1) mod 1 discovered and analyzed by De Brujin and Erdos in 1949 called the log stick-breaking strategy, proven to be optimal under 3 selected measures. The analysis of this sequence is extended by showing an interpretation in which log stick-breaking is a uniquely optimal strategy, and a more general framework is designed in which the optimality of this strategy can be explored.

  1. Lyle Ramshaw. On the gap structure of sequences of points on a circle. Indagationes Mathematicae (Proceedings). 81(1), 527-541. (1978).
  2. Hubert Dej. On the Gap Structure of Sequences of Points on a Circle. slides. (2022).
17.11.2022 16:45
Kamil Galewski
Majority colorings of sparse digraphs

A Majority k-coloring of a directed graph is an assignment of k colors to its vertices in such a way that every vertex has the same color as at most half of its out-neighbors. It is known that every digraph is majority 4-colorable, but it remains an open question whether every digraph is majority 3-colorable. The authors of the paper validate this conjecture for digraphs with a chromatic number at most 6 and digraphs with a dichromatic number at most 3. They also prove analogous theorems for list coloring: digraphs with a list chromatic number at most 6 or list dichromatic number at most 3 are majority 3-choosable. The paper also investigates which digraphs are majority 2-colorable: the authors show that digraphs without directed odd cycles are majority 2-colorable, but in general deciding whether a given digraph is majority 2-colorable is NP-complete. The last result proposed in this paper is proof that every digraph has a fractional majority of 3.9602-coloring.

  1. Michael Anastos, Ander Lamaison, Raphael Steiner, Tibor Szabó. Majority Colorings of Sparse Digraphs. Electronic Journal of Combinatorics. 28(2), P2.31. (2021).
  2. Kamil Galewski. Majority colorings of sparse digraphs. slides. (2022).
17.11.2022 16:00
Piotr Kaliciak
A counterexample to the lights out problem

In the basic Lights Out problem, we are given the undirected graph of turned-off lights, and our goal is to turn on all the lights. In the generalized version of this problem, our mission is to assign every vertex a value from 0 to p, such that for every vertex, the sum of values in its neighbors is equal to 0 mod p. The authors not only prove that a generalized version of this problem isn't always solvable but also they show conditions, under which the problem has a solution.

  1. János Nagy, Péter Pál Pach. A counterexample to the lights out problem. Journal Graph Theory. 101, 265-273. (2022).
  2. Piotr Kaliciak. A counterexample to the lights out problem. slides. (2022).
10.11.2022 16:45
Rafał Pyzik
Every graph contains a linearly sized induced subgraph with all degrees odd

It was proven by Gallai, that every undirected graph on n vertices contains an induced subgraph on at least n/2 vertices with all degrees even. It is natural to ask a similar question for odd degrees. It was conjectured, that in every graph on n vertices, without isolated vertices, we can find an induced subgraph on at least cn vertices with all degrees odd for some constant c>0. We will prove this conjecture for c=1/10000.

  1. Asaf Ferber, Michael Krivelevich. Every graph contains a linearly sized induced subgraph with all degrees odd. Advances in Mathematics. 406, 108534, (2022).
  2. Rafał Pyzik. Every graph contains a linearly sized induced subgraph with all degrees odd. slides. (2022).
10.11.2022 16:00
Justyna Jaworska
The Lovász Local Lemma is Not About Probability

Since the original statement of Lovas Local Lemma in 1973, multiple variants of the lemma with different levels of complexity have been formulated. We will present a general theorem from which most known variants of LLL follow. Additionally, the results will be generalized to supermodular functions rather than probability measures, allowing a wider range of applications.

  1. Dimitris Achlioptas, Kostas Zampetakis. The Lovász Local Lemma is Not About Probability. arXiv:2111.08837. (2021).
  2. Justyna Jaworska. The Lovász Local Lemma is Not About Probability. slides. (2022).
03.11.2022 16:45
Jędrzej Kula
Complete minors and average degree – a short proof

We call graph H a minor of graph G, if there exists such a sequence of deletions of vertices, deletions of edges, or contradictions of edges, which transforms G into H. The authors of the paper created a short proof of the result of Kostochka and of Thomasen. The proven theorem states that for every graph whose vertices have the average degree d the graph itself also contains a complete minor of order Ω(d/sqrt(log(d))).

  1. Noga Alon, Michael Krivelevich, Benny Sudakov. Complete minors and average degree – a short proof. arXiv:2202.08530. (2022).
  2. Jędrzej Kula. Complete minors and average degree – a short proof. slides. (2022).
03.11.2022 16:00
Krzysztof Ziobro
Note on the Lamp Lighting Problem

In the most basic version of the Lamp Lighting Problem, we are given an undirected graph G. We can toggle light in a chosen vertex and all of its neighbors. Our goal is to decide if it is possible to turn on the light in all vertices by performing only moves as described. Authors prove that it is always possible and explore other variants of the problem such as the directed case or the problem of checking if all lighting configurations are possible to achieve.

  1. Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand. Note on the lamp lighting problem. arXiv:math/0411201. (2004).
  2. Krzysztof Ziobro. Note on the Lamp Lighting Problem. slides. (2022).
27.10.2022 16:00
Bartłomiej Bosek
On a Problem of Steinhaus

Let N be a positive integer. A sequence X=(x1,x2,…,xN) of points in the unit interval [0,1) is piercing if {x1,x2,…,xn}∩[i/n,(i+1)/n)≠∅ holds for every n=1,2,…,N and every i=0,1,…,n−1. In 1958 Steinhaus asked whether piercing sequences can be arbitrarily long. A negative answer was provided by Schinzel, who proved that any such sequence may have at most 74 elements. This was later improved to the best possible value of 17 by Warmus, and independently by Berlekamp and Graham. We study a more general variant of piercing sequences. Let f(n)≥n be an infinite nondecreasing sequence of positive integers. A sequence X=(x1,x2,…,xf(N)) is f-piercing if {x1,x2,…,xf(n)}∩[i/n,(i+1)/n)≠∅ holds for every n=1,2,…,N and every i=0,1,…,n−1. A special case of f(n)=n+d, with d a fixed nonnegative integer, was studied by Berlekamp and Graham. They noticed that for each d≥0, the maximum length of any (n+d)-piercing sequence is finite. Expressing this maximum length as s(d)+d, they obtained an exponential upper bound on the function s(d), which was later improved to s(d)=O(d3) by Graham and Levy. Recently, Konyagin proved that 2d⩽s(d)<200d holds for all sufficiently big d. Using a different technique based on the Farey fractions and stick-breaking games, we prove here that the function s(d) satisfies ⌊c1d⌋⩽s(d)⩽c2d+o(d), where c1=ln2/(1−ln2)≈2.25 and c2=(1+ln2)/(1−ln2)≈5.52. We also prove that there exists an infinite f-piercing sequence with f(n)=γn+o(n) if and only if γ≥1/ln2≈1.44. This is joint work with Marcin Anholcer, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Rafał Pyzik, and Mariusz Zając.

  1. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Rafał Pyzik, Mariusz Zając. On a Problem of Steinhaus. arXiv:2111.01887. (2021).
20.10.2022 16:00
Bartłomiej Bosek
A Note on Generalized Majority Colorings

A majority coloring of a directed graph is a vertex coloring in which each vertex has the same color as at most half of its out-neighbors. In this note we simplify some proof techniques and generalize previously known results on various generalizations of majority coloring. In particular, our unified and simplified approach works for paintability - an online analog of list coloring. This is joint work with Marcin Anholcer, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Mariusz Zając.

  1. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Grzegorz Gutowski, Jakub Przybyło, Mariusz Zając. Mrs. Correct and Majority Colorings. arXiv:2207.09739. (2022).
13.10.2022 16:00
Bartłomiej Bosek
Recoloring Unit Interval Graphs with Logarithmic Recourse Budget

We study the problem of coloring a unit interval graph that changes dynamically. In our model the unit intervals are added or removed one at a time and have to be colored immediately so that no two overlapping intervals share the same color. After each update, only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper, we show, that if the graph remains k-colorable at all times, and the updates consist of insertions only, then we can achieve the amortized recourse budget of O(k7logn) while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bosek et al., Recoloring Interval Graphs with Limited Recourse Budget. SWAT 2020] in terms of both k and n. We complement this result by showing the lower bound of Ω(n) on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As a byproduct of independent interest, we include a new result on coloring proper circular-arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs A. We show that if there is a set A′ of non-intersecting unit arcs of size L2−1 such that A∪A′ does not contain L+1 arcs intersecting in one point, then it is possible to color A with L colors. This complements the work on unit circular arc coloring, which specifies sufficient conditions needed to color A with L+1 colors or more. This is joint work with Anna Zych-Pawlewicz.

  1. Bartłomiej Bosek, Anna Zych-Pawlewicz. Recoloring Unit Interval Graphs with Logarithmic Recourse Budget. arXiv:2202.08006. (2022).
06.10.2022 16:00
Jędrzej Hodor
Dimension of planar posets

It is a long-standing open problem if planar posets are dim-bounded (an analog of chi-bounded in the graph theory). I summarize recent progress on this problem. We explore different notions of what does it mean for posets to be planar. Finally, I will sketch the proof of dim-boundedness in the case of posets with planar cover graphs and a zero.

  1. Piotr Micek, Heather C. Smith Blake, William T. Trotter. Boolean dimension and dim-boundedness: Planar cover graph with a zero. arXiv:2206.06942. (2022).
  2. Jędrzej Hodor. Dimension of planar posets. slides. (2022).
09.06.2022 16:15
Bartłomiej Bosek
The 1/3 - 2/3 conjecture

A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field.

02.06.2022 17:00
Krzysztof Pióro
Brooks' Theorem via the Alon-Tarsi Theorem

Brooks' Theorem states that every connected graph G with maximum degree d is d-colorable unless G is an odd cycle or a complete graph. It is one of the most famous theorem on graph colorings. In the paper, the author presents yet another proof of this theorem. This proof is based on Alon-Tarsi Theorem and it remains valid in a more general choosability version of Brooks' theorem.

  1. Jan Hladký, Daniel Král’, Uwe Schauz. Brooks’ Theorem via the Alon–Tarsi Theorem. Discrete Mathematics. 310 (23), 3426-3428. (2010).
  2. Krzysztof Pióro. Brooks’ Theorem via the Alon-Tarsi Theorem. slides. (2022).
02.06.2022 16:15
Demian Banakh
Separating polynomial χ-boundedness from χ-boundedness

A class of graphs is hereditary χ-bounded if it is closed under taking induced subgraphs and every graph’s chromatic number is bounded by some function of its clique number. A well-known recently stated open question has been whether for every hereditary χ-bounded class that function can be chosen to be a polynomial. We provide a counterexample for it; namely, for any function f, we construct a hereditary χ-bounded class containing graphs of large chromatic number. In particular, for any polynomial f, such a class exists, which answers the aforementioned question negatively.

  1. Marcin Briański, James Davies, Bartosz Walczak. Separating polynomial χ-boundedness from χ-boundedness. arXiv:2201.08814. (2022).
  2. Demian Banakh. Separating polynomial χ-boundedness from χ-boundedness. slides. (2022).
26.05.2022 17:00
Bartosz Podkanowicz
Digraphs are 2-weight choosable

Consider following problem. We are given a digraph. For every edge, there are 2 options to choose a weight for this edge. We want to pick the weights of edges in a specific way. After picking weights we color vertices. The color of the vertex will be the sum of incoming edges minus the sum of outgoing edges from that vertex. We show that it is always possible to choose weights of edges such that the resulting coloring will be proper. This property is called 2-weight-choosability.

  1. Mahdad Khatirinejad, Reza Naserasr, Mike Newman, Ben Seamone, Brett Stevens. Digraphs are 2-Weight Choosable. Electronic Journal of Combinatorics. 18(1), P21. (2011).
  2. Bartosz Podkanowicz. Digraphs are 2-weight choosable. slides. (2022).
26.05.2022 16:15
Łukasz Selwa
A better lower bound on average degree of 4-list-critical graphs

A graph G is k-list-critical if it is not (k-1)-choosable, but every proper subgraph of G is (k-1)-choosable. We give a new lower bound for the average degree of incomplete k-list-critical graphs and online k-list-critical graphs. The presented bound improves the earlier known lower bounds for k = 4,5,6.

  1. Hal Kierstead, Landon Rabern. Extracting list colorings from large independent sets. arXiv:1512.08130. (2015).
  2. Landon Rabern. A better lower bound on average degree of 4-list-critical graphs. arXiv:1602.08532. (2016).
  3. Łukasz Selwa. A better lower bound on average degree of 4-list-critical graphs. slides. (2022).
19.05.2022 17:00
Rafał Kilar
Lower Bounds on the On-line Chain Partitioning of Semi-orders with Representation

An online chain partitioning algorithm is presented with one element of a poset at a time and has to assign it to a chain, partitioning the poset. We consider posets with elements represented by unit length intervals. The paper slightly improves the lower bound for the minimum number of chains needed by an online algorithm to partition these posets from ⌊3/2 w⌋ to ⌈3/2 w⌉.

  1. Csaba Biró, Israel R. Curbelo. Improved lower bound on the on-line chain partitioning of semi-orders with representation. arXiv:2111.04790. (2021).
  2. Rafał Kilar. Lower Bounds on the On-line Chain Partitioning of Semi-orders with Representation. slides. (2022).
19.05.2022 16:15
Krzysztof Potępa
Unit-Monge matrices and seaweed braids

Simple unit-Monge matrices form a special subclass of square matrices, which can be represented implicitly in linear space by permutations. Somewhat surprisingly, the subclass is closed under distance multiplication. We will show connection between simple unit-Monge matrices and seaweed braids: braids in which each pair of strings crosses at most once. In particular, distance multiplication is equivalent to a "combing procedure", where double-crossings in braid are removed. We will discuss applications of these methods to a few subsequence problems. In particular, the combing procedure can be exploited to obtain an elegant algorithm for all-substring LCS problem.

  1. Alexander Tiskin. Semi-local string comparison: algorithmic techniques and applications. arXiv:0707.3619. (2007).
  2. Krzysztof Potępa. Unit-Monge matrices and seaweed braids. slides. (2022).
12.05.2022 17:00
Jacek Salata
A Short Proof of Nash-Williams' Theorem for the Arboricity of a Graph

Nash-Williams theorem (tree-packing theorem) is a classical result due to Nash-Williams (1961) that characterizes graphs with k edge-disjoint spanning trees. In the seminar, I will present a short and elegant proof of the theorem.

  1. Boliong Chen, Makoto Matsumoto, Jianfang Wang, Zhongfu Zhang, Jianxun Zhang. A short proof of Nash-Williams' theorem for the arboricity of a graph. Graphs and Combinatorics, 10 (1). 27-28. (1994).
  2. Jacek Salata. A Short Proof of Nash-Williams' Theorem for the Arboricity of a Graph. slides. (2022).
12.05.2022 16:15
Kamil Galewski
Bears with Hats and Independence Polynomials

The hat guessing game is a game in which bears sit in the vertices of an undirected graph. A demon puts hats on the bears' heads. Each hat has one of the h available colors. Each bear sees only the hat colors of his neighbors. The goal of the bears is to guess the color of their hats - each bear has g tries to guess his hat color. The bears win if at least one of them has guessed the color of his hat correctly. This paper describes the relationship between the hat guessing game and the independence polynomial of graphs.

  1. Václav Blažej, Pavel Dvořák, Michal Opler. Bears with Hats and Independence Polynomials. arXiv:2103.07401. (2021).
  2. Kamil Galewski. Bears with Hats and Independence Polynomials. slides. (2022).
05.05.2022 17:00
Szymon Salabura
Contact graphs of ball packings

A contact graph of a ball packing is a graph with non-intersecting balls as vertices and edges between pairs of tangent balls. In the seminar, we will focus on the upper bounds for the average degree of such graphs in any number of dimensions.

  1. Alexey Glazyrin. Contact graphs of ball packings. arXiv:1707.02526. (2017).
  2. Szymon Salabura. Contact Graphs on Ball Packings. slides. (2022).
05.05.2022 16:15
Mateusz Pach
Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

It has been conjectured that every planar triangle-free graph G has exponentially many proper vertex-3-colorings. In this paper, the conjecture is disproved. It is also shown that the conjecture holds if we add an assumption about the non-existence of separating cycles of lengths 4 and 5. Specifically, it is proved that the number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2n/17700000.

  1. Carsten Thomassen. Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles. Journal of Combinatorial Theory, Series B. (2021).
  2. Mateusz Pach. Exponentially many 3-colorings of planar graphs with no short separating cycles. slides. (2022).
28.04.2022 17:00
Karolina Gontarek
On topological aspects of orientations

The paper considers two classes of planar graphs: maximal planar graphs and maximal bipartite planar graphs. The authors describe how these graphs can be oriented in the way that each vertex has prescribed indegree. Then the relation of such orientations to specific graph decompositions and orderings on the vertex set is provided. Discussed orientations can be used to characterize some of the planar graphs. Described properties have applications e.g. in graph drawing and planar augmentation problems.

  1. Hubert de Fraysseix, Patrice Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics. 229(1-3). 57-72. (2001).
  2. Karolina Gontarek. On topological aspects of orientations. slides. (2022).
28.04.2022 16:15
Ruslan Yevdokymov
Flexible Color Lists in Alon and Tarsi’s Theorem, and Time Scheduling with Unreliable Participants

By describing a winning strategy for Mrs. Correct in the coloring game of Mr. Paint and Mrs. Correct author presents a purely combinatorial proof of a strengthening of Alon and Tarsi's Theorem. Strengthening of the theorem also leads to the strengthening of its applications, for example, upper bounds for list chromatic numbers of bipartite graphs, list chromatic indices of complete graphs, and chess tournament time scheduling problem with unreliable participants.

  1. Uwe Schauz. Flexible Color Lists in Alon and Tarsi's Theorem, and Time Scheduling with Unreliable Participants. Electronic Journal of Combinatorics. 17. R13. (2010).
  2. Ruslan Yevdokymov. Flexible Color Lists in Alon and Tarsi’s Theorem. slides. (2022).
21.04.2022 17:00
Wojciech Buczek
On an early paper of Maryam Mirzakhani

In this seminar, we will talk about Maryam Mirzakhani, who had an enormous influence on research about Combinatorics. We will study her idea of creating a small (with (only!) 63 vertices), non-4-choosable planar graph, which is also 3-choosable. We will also consider other problems she worked on.

  1. William J. Martin. On an early paper of Maryam Mirzakhani. arXiv:1709.07540. (2017).
  2. Wojciech Buczek. On an early paper of Maryam Mirzakhani. slides. (2022).
21.04.2022 16:15
Maciej Nemś
Avoiding squares over words with lists of size three amongst four symbols

Word creation from lists of size t is a problem where for alphabet Σ each sign of created word is chosen from a list of t different signs from Σ. Word is "square-free" when it does not contain any squares. A square is a word of form ww with w being a nonempty word. The author first shows that there are at least 2.45n square-free words of length n created from lists of 4. This is an improvement from the previous bound which is 2n. After that, the main result of the paper is shown which is an existence of at least 1.25n words of length n from lists of 3.

  1. Rosenfeld, Matthieu. Avoiding squares over words with lists of size three amongst four symbols. arXiv:2104.09965. (2021).
  2. Maciej Nemś. Avoiding squares over words with lists of size three amongst four symbols. slides. (2022).
14.04.2022 16:15
Bartłomiej Bosek
From 1-2-3 conjecture to Riemann hypothesis

We consider some coloring issues related to the famous Erdős Discrepancy Problem. A set of the form As,k={s,2s,…,ks}, with s,k ∈ N, is called a homogeneous arithmetic progression. We prove that for every fixed k there exists a 2-coloring of N such that every set As,k is perfectly balanced (the numbers of red and blue elements in the set As,k differ by at most one). This prompts reflection on various restricted versions of Erdős' problem, obtained by imposing diverse confinements on parameters s,k. In a slightly different direction, we discuss a majority variant of the problem, in which each set As,k should have an excess of elements colored differently than the first element in the set. This problem leads, unexpectedly, to some deep questions concerning completely multiplicative functions with values in {+1,−1}. In particular, whether there is such a function with partial sums bounded from above.

07.04.2022 17:00
Marcin Serwin
Can a party represent its constituency?

Upon gaining p% votes in an election in a proportional system, a party appoints p% of its proposed candidates to represent the party. The order of candidates to appoint is chosen beforehand. This may create tensions if the party members are not perfectly aligned politically, if some candidates of particular tendency are lower down the list and thus less likely to be appointed. This presentation examines the problem of existence and characterization of the list that would not create such tension and related problems.

  1. Amoz Kats. Can a Party Represent Its Constituency?. Public Choice. 44(3), 453-456. (1984).
  2. Marcin Serwin. Can a party represent its constituency? slides. (2022).
07.04.2022 16:15
Piotr Kaliciak
2-List-coloring planar graphs without monochromatic triangles

The author is considering a planar graph, where every vertex has a list of 2 colors, and every coloring of this graph has to choose for every vertex one of these two colors. Unlike the standard colorings, the author doesn't mind having a monochromatic edge, but he tries to avoid having a monochromatic triangle. In this paper, he not only proves, that every planar graph can be colored this way, for every list assignment, but also he proves a stronger result for graphs with some vertices pre-colored.

  1. Carsten Thomassen. 2-List-coloring planar graphs without monochromatic triangles. Journal of Combinatorial Theory, Series B. 98(6). 1337-1348. (2008).
  2. Piotr Kaliciak. List coloring planar graphs without monochromatic triangles. slides. (2022).
31.03.2022 17:00
Katarzyna Król
On List-Coloring Outerplanar Graphs

An outerplanar graf is a planar graph whose vertices can all be drawn on the outer face. The author researched the problem of coloring outerplanar graphs from lists. First, it is shown that the outerplanar graph is L-colorable if satisfies |L(v)| ≥ min{deg(v),4} and is bipartite. Then additional assumptions are searched for so that a similar inequality could define L-colorability in general outerplanar graphs. The results given by the author are the best possible for each condition in the bounds and hypotheses.

  1. J.P. Hutchinson. On list-coloring outerplanar graphs. J. Graph Theory. 59, 59-74. (2008).
  2. Katarzyna Król. On List-Coloring Outerplanar Graphs. slides. (2022).
31.03.2022 16:15
Jędrzej Kula
Multiple list colouring of planar graphs

Since every planar graph G can be colored by 4 colors, there is also an integer m such that G is (4m,m)-choosable. The problem here is that such m is changing with G. The author of this paper proves that there cannot be such a universal m that every planar graph is (4m,m)-choosable. To be precise he shows that for each positive integer m, there is a planar graph G which is not (4m+⌊(2m-1)/9⌋,m)-choosable. Also, he poses some conjectures about planar graphs multiple list coloring.

  1. Xuding Zhu. Multiple list colouring of planar graphs. Journal of Combinatorial Theory, Series B. 122, 794-799. (2017).
  2. Jędrzej Kula. Multiple list colouring of planar graphs. slides. (2022).
24.03.2022 17:00
Jędrzej Hodor
Clustered Coloring and Hadwiger's conjecture

Hadwiger conjecture states, that for every Ks+1 minor free graph it can be colored with s colors. For now, it is wide open. There are plenty of well-known results improving the bound on the number of colors. However, there exists another approach to make the problem easier. We can relax the notion of proper coloring. A graph class can be η-clustered colored with n colors if in every graph only n colors are used and the size of each monochromatic component is bounded by η. Liu and Wood proved that for a class of graphs excluding Ks+1 minor can be η(s)-clustered colored with s+2 colors, which is almost optimal (s < s+2). I will describe their approach and prove the result in a simplified case.

  1. Chun-Hung Liu, David R. Wood. Clustered Coloring of Graphs Excluding a Subgraph and a Minor. arXiv:1905.09495. 2019.
  2. Jędrzej Hodor. Clustered Coloring of Graphs Excluding a Subgraph and a Minor. slides. (2022).
24.03.2022 16:15
Grzegorz Gawryał
The Catalan matroid

A path of length 2n, that starts in (0,0) and at each step moves from (x,y) to (x+1,y+1) or (x+1,y-1) is a Dyck path, if it ends in (2n,0) and never passes below y=0 line. Such paths are counted by Catalan numbers. In this presentation, we'll show, that the Dyck paths for fixed n form a matroid. We'll show what are bases, independent sets, and other matroid-related terms in this object, explore some properties of this matroid, and see how it generalizes to shifted matroids.

  1. Federico Ardila. The Catalan matroid. arXiv:math/0209354. 2002.
  2. Grzegorz Gawryał. The Catalan Matroid. slides. (2022).
17.03.2022 16:15
Krzysztof Ziobro
A note on polynomials and f-factors of graphs

The factor of a graph is its spanning subgraph which adheres to given constraints on the degrees. The authors of the article discuss the f-factor, which for every vertex defines a set of possible degrees. The main result shows a new sufficient condition for the existence of an f-factor in a given graph. Authors obtain it by using Combinatorial Nullstellensatz.

  1. Hamed Shirazi, Jacques Verstraëte. A Note on Polynomials and f-Factors of Graphs. Electronic journal of combinatorics. 15, N22. 2008.
  2. Krzysztof Ziobro. A note on polynomials and f -factors of graphs. slides. (2022).
27.01.2022 17:30
Bartosz Podkanowicz
Alon Tarsi number of planar graphs

We prove that the Alon-Tarsi number of a planar graph is less or equal to 5. Alon Tarsi number is an important parameter for the graph. It is greater than the choice number and paintability for every graph. We show the modification of the standard argument presented by Carsten Thomassen. We construct a special orientation that doesn't have Euler subgraphs and allows us to reason about the Alon-Tarsi number.

  1. X. Zhu. The Alon-Tarsi number of planar graphs. arXiv:1711.10817. (2017).
  2. Bartosz Podkanowicz. Thomassen orientations. slides. (2022).
27.01.2022 16:45
Jędrzej Kula
Bipartite Perfect Matching is in quasi-NC

The class NC represents the problems that have efficient parallel algorithms. In this work, the authors present two algorithms. The first algorithm proves that the perfect matching problem for bipartite graphs is in quasi-NC2. The second algorithm proves that the same problem is in the RNC class and uses only O(log2 n) random bits. Note that a complete derandomization would be achieved when the number of random bits comes down to O(log n).

  1. S. A. Fenner, R. Gurjar, T. Thierauf. Bipartite Perfect Matching is in quasi-NC. arXiv:1601.06319. (2016).
  2. Jędrzej Kula. Bipartite Perfect Matching is in quasi-NC. slides. (2022).
27.01.2022 16:00
Krzysztof Pióro
Graph coloring game

In the game coloring game two players are given graph and a set of k colors. Players take turns, coloring properly an uncolored vertex. The goal of the first player is to complete the coloring of the graph, while the other one tries to prevent him from achieving it. The game chromatic number of a graph is the minimum number of colors needed for the first player to win. In this presentation I will show bounds for the game chromatic number for some classes of graphs.

  1. Krzysztof Pióro. Graph Coloring Game. slides. (2022).
20.01.2022 16:00
Szymon Salabura
The Hats game. On max degree and diameter

In the Hats game, the sages, located at graph vertices, try to guess colors of their own hats, only seeing colors of hats on sages at the adjacent vertices. If using a deterministic strategy, at least one sage can guess the color of his own hat correctly, we say that the sages win. In this presentation, we consider the hat guessing number - the maximum number of possible colors, for which the sages can guarantee the win. We will see examples of graphs contradicting the previously stated hypothesis, that the hat guessing number is smaller than the graph's maximal degree + 1. We also show its independence from the graph's diameter.

  1. Aleksei Latyshev, Konstantin Kokhas. The Hats game. On max degree and diameter. arXiv:2108.08065. (2021).
  2. Szymon Salabura. The Hats game. On max degree and diameter. slides. (2021).
13.01.2022 16:45
Jacek Salata
Choosability of K5-minor-free graphs

Thomassen showed in 1994 that all planar graphs are 5-choosable and Škrekovski showed in 1998 that all K5-minor-free graphs also are 5-choosable. In this presentation we will take a look at two different proofs of the latter theorem: the Škrekovski's one from the original paper, and the one proposed by Wenjie Hea, Wenjing Miao and Yufa Shenb in 2007.

  1. Wenjie He, Wenjing Miao, Yufa Shen. Another proof of the 5-choosability of -minor-free graphs. Discrete Mathematics. 308(17), 4024-4026. (2008).
  2. Kacek Salata. Choosability of K5-minor-free graphs. slides. (2022).
13.01.2022 16:00
Demian Banakh
A relative of Hadwigers conjecture

The well-known open Hadwiger's conjecture asserts that every simple graph G which is not t-colorable has Kt+1 minor. In this presentation, we will take a look at the proof of a relaxed version of this conjecture (in terms of so-called "defective colorings" - i.e. allowing a "small" number of monochromatic edges), as well as see how it can be useful for solving some other graph problems.

  1. Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, Paul Seymour. A relative of Hadwiger's conjecture. arXiv:1407.5236. (2014).
  2. Demian Banakh. A Relative of Hadwiger’s Conjecture. slides. (2022).
16.12.2021 16:45
Wojciech Buczek
Parking functions: From combinatorics to probability

Let's say m drivers have their favourite parking spot in the linear car park with n spots. Now, in some order, drivers will try to park their car at their favourite spot, and if they fail (because other car is standing there), they will try to park at the next avaible spot. If all drivers could park their car, we call this choices a parking function. In this seminar, we will look at this function proporties, create bijection from them to spanning forests and talk about some conjectures related to parking functions.

  1. Richard Kenyon, Mei Yin. Parking functions: From combinatorics to probability. arXiv 2103.17180. (2021).
  2. Wojciech Buczek. Parking functions. slides. (2021).
16.12.2021 16:00
Rafał Kilar
A first moment proof of the Johansson-Molloy Theorem

The paper provides a simple proof of a stronger version of Johansson-Molloy theorem, providing a bound on the list chromatic number of a graph based on maximum degree and neighbouhood density. The new proof only makes use of the first moment method. The counting argument used in the proof is inspired by work by Rosenfeld in the contex of non-repetitive graph coloring. The result is than extended to graphs with neighbourhoods with bounded density, which strengthens previous results. Lastly, the method is adapted to show asymptotically tight lowe bound on the number of colourings of sparse graphs .

  1. François Pirot, Eoin Hurley. Colouring locally sparse graphs with the first moment method. arXiv 2109.15215. (2021).
  2. Rafał Kilar. Colouring locally sparse graphs with the first moment method. slides. (2021).
09.12.2021 16:45
Marcin Serwin
Bears with Hats and Independence Polynomials

A hat guessing game consists of a graph and bears assigned to vertices with a certain hat color. Each bear knows the colors of the bears belonging to the neighborhood of their vertex but does not know their own color. The bears win if at least one of them can guess the color of their hat. This presentation will introduce the aforementioned game, its variants and present findings of Václav Blažej, Pavel Dvořák and Michal Opler regarding fractional hat chromatic number of graphs with independence polynomials.

  1. Václav Blažej, Pavel Dvořák, Michal Opler. Bears with Hats and Independence Polynomials. arXiv 2103.07401. 2021.
  2. Marcin Serwin. Bears with Hats and Independence Polynomials. slides. (2021).
09.12.2021 16:00
Krzysztof Potępa
Weak degeneracy of graphs

The paper introduces a new graph parameter called "weak degeneracy", a variant of the degeneracy parameter. The authors show various applications of weak degeneracy. For example, it turns out that this new parameter is strongly correlated with graph coloring. Authors derive alternative proofs for several classic upper bounds in graph coloring theory, including 5-list-coloring of planar graphs. My presentation will summarize the findings of the paper.

  1. Anton Bernshteyn, Eugene Lee. Weak degeneracy of graphs. arXiv 2111.05908, (2021).
  2. Krzysztof Potępa. Weak degeneracy of graphs. slides. (2021).
02.12.2021 16:45
Krzysztof Michalik
Improved lower bound for the list chromatic number of graphs with no Kt minor

This paper begins with recounting known limits regarding Hadwiger's conjecture and related problems including list Hadwiger's conjecture, stating that there does exist constant c, such that Kt minor free graph G has list coloring number not exceeding ct. After the introduction, we are presented with proof that such constant has to be at least equal to 2, contrary to previous results, where c was bounded by 4/3 and conjectured to be equal to 3/2.

  1. Krzysztof Michalik. Improved Lower Bound For The List Chromatic Number Of Graphs With No Kt Minor. slides. (2021).
02.12.2021 16:00
Krzysztof Ziobro
Polynomials over structured grids

Paper discusses properties of multivariate polynomials over finite grids, focaausing on he grids that are in some way "structured". To capture the degree to which a grid is structured, author introduces a notion of nullity, which can give us a numerical measure of structure. It is noted that for more structured grids we can obtain stronger versions of general theorems. This leads to the main results of the paper: the Structured Combinatorial Nullstellensatz and the Complete Coefficient Theorem.

  1. Bogdan Nica. Polynomials over structured grids. arXiv 2110.05616. (2021).
  2. Krzysztof Ziobro. Polynomials over structured grids. slides. (2021).
25.11.2021 16:45
Artur Salawa
The Open Problems Project

Paper records open problems in computational geometry and related fields. For every problem, the authors provide a statement, origin, current status, partial results and related problems. My presentation focuses on a few chosen problems explained in a friendly manner.

  1. Erik D. Demaine Joseph, S. B. Mitchell, and Joseph O’Rourke. The Open Problems Project. manuscript. (2020).
  2. Artur Salawa. The Open Problems Project. slides. (2021).
25.11.2021 16:00
Grzegorz Wawrzesta
Density conditions for panchromatic colourings of hypergraphs

A hypergraph is defined as a pair H = (V, E), where V is a set of vertices and E is a set of subsets of V - these subsets of vertices are called (hyper)edges. Graphs can be then seen as a concretization where all edges are sets of size 2. This can be shortly ascribed to the hypergraph as being 2-uniform. T-uniformity is a useful assumption for deriving its properties but sometimes one would wish for more general results. This approach is one of a few that are considered by the authors of the following paper which focuses on boundaries we can put on some characteristic properties of hypergraphs relating to their colorability and list-colorability. During the meeting, the basic concepts of hypergraphs and their colorability will be introduced and then the results of the paper will be interpreted alongside the presentation of the theorems and lemmas (and also an exemplar proof of one of them or two) which are used in the paper to attain the results.

  1. Alexandr V. Kostochka, Douglas R. Woodall. Density Conditions for Panchromatic Colourings of Hypergraphs. Combinatorica 21, 515-541. (2001).
  2. Grzegorz Wawrzesta. Density conditions for panchromatic colourings of hypergraphs - introduction and overview. slides. (2021).
18.11.2021 16:45
Maciej Nemś
Fair Correlation Clustering

In this paper authors propose approximation for Correlation Clustering problem with additional constaint of fairness. In a fair version of correlation clustering vertices have also colors and in the end in each cluster there should be "some" number of vertices of each color. What "some" means is dependent on variant of this constraint. Authors first reduce a problem of fair clustering correlation to a problem they call Fairlet Decomposition and then show approximation algorithm for this problem. In the end they describe some experiments they have done to prove Fair Correlation Clustering a viable version of Correlation Clustering.

  1. Sara Ahmadian, Alessandro Epasto, Ravi Kumar, Mohammad Mahdian. Fair Correlation Clustering, arXiv 2002.02274. (2021).
  2. Maciej Nemś. Fair Correlation Clustering. slides. (2021).
18.11.2021 16:00
Karolina Gontarek
Growth properties of power-free languages

Paper surveys common part of two formal language issues. Issue of repetition free words and languages and issue of growth functions for words and languages. Paper gives an overview of current knowledge and search about an intersection of those two areas. It classifies power-free languages with regard to their growth rate. It also describes methods of esimating complexity of power-free languages paying attention to amount of computer resources needed by special method. Finally, it presents future directions of research in this area.

  1. Karolina Gontarek. Growth properties of power-free languages. slides. (2021).
04.11.2021 16:45
Roch Wójtowicz
Problems and results on 3-chromatic hypergraphs and some related questions

Authors in this work aim to establish various bounds and constraints on hypergraphs which are k-chromatic. Hypergraph is a graph where an edge don’t have to link exactly two vertices. Hypergraph is called simple, when none two of his edges has more then one common point, and is called clique when each two of his edges has at least one common point. Hyper graph is r-uniform when each of its edges contains exactly r points. Chromatic number is a smallest number k such that you can color points of the graph using k colors in the way that no edge is monochromatic. Main part of the work involves around the impact that being clique or simple has on 3-chromatic hypergraph structure. The main reason why those two things are connected is following trivial observation: If a hypergraph has chromatic number > 3 then it has two edges with exactly one common point.

  1. Paul Erdős, László Lovász. Problems and results on 3-chromatic Hypergraphs and some related questions. Coll Math Soc J Bolyai. 10. (1974).
  2. Roch Wójtowicz. Problems and results on 3-chromatic hypergraphs and some related questions. slides. (2021).
04.11.2021 16:00
Grzegorz Gawryał
Defective and clustered choosability of sparse graphs

This paper explores almost proper graph colorings and list colorings - we allow the coloring to be improper, but we impose restrictions on the maximum number of neighbours of any vertex with the same color as the vertex itself (defect) or the maximum allowed size of a monochromatic connected graph component (clustering). The paper provides new bounds on coloring and list coloring number for sparse graphs, i.e. having bounded maximum average degree, taken over all subgraphs, or limited maximum degree. More precisely, the two main results of this paper are the new bounds on defective choosability and clustered choosability of graphs with bounded maximum average degree, being the best known results for graphs with unbounded maximum degree, but bounded maximum average degree, like k-stack and k-queue graphs.

  1. Kevin Hendrey, David R. Wood. Defective and clustered choosability of sparse graphs. Combinatorics, Probability and Computing, 28, 791-810. (2019).
  2. Grzegorz Gawryał. Defective and clustered choosability of sparse graphs. slides. (2021).
14.10.2021 16:00
Jędrzej Hodor
Reconfiguring Independent Sets on Interval Graphs

In the reconfiguration problem, we are given a set of objects and rules of how one object can be reconfigured into another one. The main questions to be asked are if it is possible to reconfigure two given objects into each other (Reachability Problem) or how long is the shortest possible reconfiguration sequence. We focus on reconfiguring independent sets in a given graph. Two independent sets are reconfiguration-adjacent if their symmetric difference consists exactly of two vertices connected by an edge. It is known that for some graph classes the Reachability Problem can be solved in polynomial time. I briefly survey the topic and show that the problem is computationally hard for incomparability graphs. Moreover, I discuss the reconfiguration paths length problem in general and in more detail in the class of interval graphs.

  1. Marcin Briański, Stefan Felsner, Jędrzej Hodor, Piotr Micek. Reconfiguring Independent Sets on Interval Graphs. arXiv, 2105.03402, (2021).
  2. Marcin Brianski, Stefan Felsner, Jedrzej Hodor and Piotr Micek. Reconfiguring Independent Sets On Interval Graphs. slides. (2021).
07.10.2021 16:15
Bartłomiej Bosek
Open problem session

Several open problems related to 1-2-3 Conjecture are presented.

17.06.2021 17:00
Szymon Salabura
The Fixing Block Method in Combinatorics on Words

A word is repetitive if it contains two consecutive identical blocks. A sequence is non-repetitive up to mod r if each of its mod k (1⩽k⩽r) subsequences is non-repetitive. Let L be a language of non-repetitive (up to mod r) words. In this seminar, we are going to take a look at fixing blocks - a special kind of suffixes preventing words of L to have an extension in L. Using the fixing blocks method we are going to show some interesting properties of such languages. We also outline a method of attack for more complex problems.

  1. James D. Currie, Cameron W. Pierce. The Fixing Block Method in Combinatorics on Words. Combinatorica 23, 571-584, (2003).
  2. Szymon Salabura. The Fixing Block Method in Combinatorics on Words. slides. (2021).

(the seminar will only be online)

17.06.2021 16:15
Wojciech Węgrzynek
Non-repetetive words: ages and essences

The age of an infinite word will be the set of all its finite subwords, it's essence will be the set of all finite subwords occurring infinitely many times. The language L{121,323} is the language of all square-free infinite words, such that they don’t have 121 or 323 as subwords. It turns out if we consider the equivalence relations on L{121,323} in respect to the ages and the essences we will get an uncountable cardinality of equivalence classes and 1 equivalence class respectively.

  1. James D. Currie. Non-repetitive words: Ages and essences. Combinatorica 16, 19-40, (1996).
  2. Wojciech Węgrzynek. Non-repetitive words: ages and essences. slides. (2021).

(the seminar will only be online)

10.06.2021 17:00
Bartosz Wodziński
Zarankiewicz's Problem and some related results

In 1951, Kazimierz Zarankiewicz posed a problem asking for the largest possible number of edges in a bipartite graph that has a given number of vertices (n) and has no complete bipartite subgraphs of a given size. Although solved for some specific cases, it still remains open in general. It led to some interesting results in extremal graph theory, such as Kővári–Sós–Turán theorem which gives an upper bound for this problem. During the seminar, I will discuss several problems related to forbidding subgraphs, from easy up to unsolved ones. I will also show their connection with some geometric problems such as creating a maximum number of unit distances between n points on a plane.

  1. Matoušek J. Incidence Problems. In: Matoušek J. (eds) Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol 212. Springer, New York, NY. (2002).
  2. Yufei Zhao. Graph Theory and Additive Combinatorics. course. MIT. (2020).
  3. Bartosz Wodziński. Zarankiewicz's Problem and some related results. slides. (2021).

(the seminar will only be online)

10.06.2021 16:15
Michał Zwonek
Polyomino Tilings

A polyomino is a subset of R2 formed by a strongly connected union of axis-aligned unit squares centered at locations on the square lattice Z2. Let T = {T1,T2,...} be an infinite set of finite simply connected closed sets of R2. Provided the elements of T have pairwise disjoint interiors and cover the Euclidean plane, then T is a tiling and the elements of T are called tiles. Provided every T∈ T is congruent to a common shape T, then T is monohedral, T is the prototile of T, and the elements of T are called copies of T. In this case, T is said to have a tiling. We will go through some of the open problems related to polyomino tilings.

  1. Michał Zwonek. Polyomino Tilings. slides. (2021).

(the seminar will only be online)

27.05.2021 17:00
Jan Mełech
Rödl Nibble

For positive integers r<k<n let m(n,k,r) be the maximal size of a family F of k-element subsets of [n] such that no r vertices lie in more than one A in F. The Erdös-Hanani conjecture states that as n grows to infinity m(n,k,r) tends to (n choose r)/(k choose r). Firstly, we will see a sketch of the proof of this conjecture proposed by Vojtech Rödll. Then we will talk about how this is connected with packing in hypergraph and discuss the idea of an algorithm called Rödl nibble that achieves asymptotically optimal packing k-uniform hypergraphs.

  1. Joonleng Tan. Rödl Nibble. manuscript. (2012).
  2. Jan Mełech. Rödl Nibble. slides. (2021).

(the seminar will only be online)

27.05.2021 16:15
Krzysztof Pióro
Decomposing planar graphs into graphs with degree restrictions

Given a graph G, its (d,h)-decomposition is a partition of a set of edges of this graph into a d-degenerate graph and a graph with maximum degree at most h. We will study (d,h)-decomposability of planar graphs and consider the problem of finding minimum hd such that every planar graph is (d,hd)-decomposable. Since every planar graph is 5-degenerate, we will consider only the case of d less than 5.

  1. Krzysztof Pióro. Decomposing planar graphs into graphs with degree restrictions. slides. (2021).

(the seminar will only be online)

20.05.2021 17:00
Maciej Nemś
Ant Colony Optimization

Ant Colony Optimization algorithms are part of swarm intelligence approach to solving problems. They are inspired by behavior of ants. After finding a desired destination ants leave pheromones on the way back to the colony. This way all ants can detect the scent and decide to go in the direction suggested by pheromone trail. ACO is based on this concept and involves multi-agent computation. Communication between agents is done by changing the stimuli for all agents, to make a certain action. This is similar to ants leaving pheromones. Presentation will include basic concept of Ant Colony Optimization and an example of solving a well known problem using it. I will also present a formalization of ACO into a metaheuristic for combinatorial optimization problems. Presentation will end with talk about current state of ACO, its limitation and possible future.

  1. M. Dorigo, M. Birattari, and T. Stutzle. Ant colony optimization. IEEE Computational Intelligence Magazine1(4), 28-39. (2006).
  2. M. Dorigo and T. Stützle. Ant Colony Optimization: Overview and Recent Advances. In: Gendreau M., Potvin JY. (eds) Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol 146. Springer, Boston, MA. (2010).
  3. Maciej Nemś. Ant Colony Optimization. slides. (2021).
  4. ANTS International Conference on Swarm Intelligence.

(the seminar will only be online)

20.05.2021 16:15
Wojciech Buczek
Woodall’s conjecture

Woodall’s conjecture tells us, that any directed cut with at least k edges has at least k disjoint dijoins. Set of edges D is a dijoin if and only if the digraph (V, E ∪ D-1) is strongly connected. We will say about the linear programming formulation of this problem, equivalent and related problems to it, and some partial results by Shrijver, Lee and Wakabayashi, and Meszaros. We will also show counterexamples to a generalized version of the conjecture.

  1. Paulo Feofiloff. Woodall’s conjecture on Packing Dijoins: a survey. manuscript. (2005)
  2. Wojciech Buczek. Woodall’s conjecture. slides. (2021).

(the seminar will only be online)

13.05.2021 16:15
Vladyslav Rachek, Ruslan Yevdokymov
An Introduction to the Discharging Method via Graph Coloring

The discharging method is a technique that can be used to show that some global properties of a graph imply the existence of local structures. Then, we can sometimes show, that such structures imply that the graph has another global property. The discharging method is thus a "connector" between global properties of a graph (via local properties, e.g. having subgraphs or minors). In the first part of the presentation, we talk about the structure and coloring of sparse and plane graphs. Typical statements will sound like "If there is some global degree bound, then the chromatic number is somehow bounded"

  1. D. Cranston, D. West. A Guide to the Discharging Method. manuscript. (2013).
  2. Vladyslav Rachek, Ruslan Yevdokymov. An Introduction to the Discharging Method via Graph Coloring. slides. (2021).

(the seminar will only be online)

06.05.2021 17:00
Marcin Serwin
Aanderaa-Karp-Rosenberg conjecture

The conjecture deals with queries on graph. More concretely given property of a graph (such as connectedness or non-emptiness) we may ask whether it is possible to recognize a graph with this property without querying all of its edges. It turns out that for many properties it is indeed not possible to do so in a deterministic manner for all graphs. The Aanderaa–Karp–Rosenberg conjecture states that any non-trivial monotone graph property cannot be determined by a deterministic algorithm with less than n(n-1)/2 queries. Such graph properties are called evasive, thus this conjecture is sometimes called evasiveness conjecture.

  1. Marcin Serwin. Aanderaa-Karp-Rosenberg conjecture. slides. (2021).

(the seminar will only be online)

06.05.2021 16:15
Krzysztof Potępa
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds

In the edge orientation problem, one is asked to orient edges of a given graph such that the out-degrees of vertices are bounded by some function. In the fully dynamic variant, we want to process arbitrary edge insertions and deletions in an online fashion. We will show an algorithm for graphs with bounded arboricity that achieves logarithmic out-degree bound and supports updates in O(log n) worst-case time.

  1. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. ICALP 2014, LNCS 8573, 532-543, (2014). (arXiv:1312.1382)
  2. Krzysztof Potępa. Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. slides. (2021).

(the seminar will only be online)

29.04.2021 16:15
Mateusz Kaczmarek
On triangles in Kr-minor free graphs

There is a close connection between minors of the graph and a lower bound on such number k that each edge (or vertex) belongs to at least k triangles. One of the most interesting classes of minors is the class of complete graphs Kr. In the paper 'On triangles in Kr-minor free graphs', Boris Albar and Daniel Gonçalves take a closer look at this class of graphs. Based on their work I will present some interesting results regarding this connection and show how it correlates with Hadwiger's conjecture.

  1. Boris Albar Daniel Gonçalves. On triangles in Kr‐minor free graphs. Journal of Graph Theory, 88(1), 154-173, (2017). (arXiv:1304.5468)
  2. Mateusz Kaczmarek. On triangles and minors. slides. (2021).

(the seminar will only be online)

22.04.2021 16:15
Bartłomiej Jachowicz
Acyclic coloring of graphs with fixed maximum degree

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted as a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. Known problem in this area is to find an upper bound for an acyclic chromatic number for graphs with a fixed maximum degree. One of the first papers on this topic is Hocquard's article "Graphs with maximum degree 6 are acyclically 11-colorable". The proofing technique from his work has been used in many later papers that show similar bounds for graphs with fixed maximum grades.

  1. Hervé Hocquard. Graphs with maximum degree 6 are acyclically 11-colorable. Information Processing Letters, 111(15), 748-753, (2011). (manuscript)
  2. Bartłomiej Jachowicz. Acyclic coloring of graphs with fixed maximum degree. slides. (2021).

(the seminar will only be online)

15.04.2021 16:15
Piotr Mikołajczyk
Thomassen's choosability argument revisited

The Hadwiger Conjecture states that if a graph G does not contain a clique on t vertices as a minor, then G is (t-1)-colorable. For low values of t (<7) it was already shown that this claim is actually true. Currently, the best-known upper bound on the chromatic number of Kt-minor-free graphs is O(ct*sqrt(log(t))) and the proof follows from a degeneracy argument. Unfortunately, this approach cannot be exploited further. However, by revisiting Thomassen's reasoning from '94 we can try to prepare the ground for a new way of attacking the Hadwiger Conjecture based on graph choosability. For that, we will take a look at a new proof of a theorem that every K5-minor-free graph is 5-choosable.

  1. David R. Wood, Svante Linusson. Thomassen's Choosability Argument Revisited. SIAM Journal on Discrete Mathematics, 24(4), 1632-1637, (2010). (arXiv:1005.5194)
  2. Piotr Mikołajczyk. Thomassen's choosability argument revisited. slides. (2021).

(the seminar will only be online)

08.04.2021 16:15
Jędrzej Kula
Combinatorial Nullstellensatz

Proposed by Noga Alon in 1999 an algebraic technique inspired by Hilbert’s Nullstellensatz. Despite being an observation about roots of a polynomial in n variables, it finds a usage in numerous fields - from Combinatorial Number Theory to Graph Theory. The theory itself is simple, but can be used in ingenious ways - appearing even as almost a necessary step to solve a problem during the 2007 IMO competition. During this time slot I will present a theorem and prove it with as I believe a simpler proof constructed by Mateusz Michałek, that is using a basic induction idea over a polynomial degree. Finally we will again follow the original N. Alon paper to see applications of a theorem in the graph coloring problems and some more.

  1. Noga Alon. Combinatorial Nullstellensatz. Combinatorics Probability and Computing, 8 (1999), 7-29. (manuscript)
  2. Mateusz Michałek. A short proof of Combinatorial Nullstellensatz. American Mathematical Monthly, 117 (2010), 821-823. (arXiv:0904.4573)
  3. Tomasz Kochanek. Combinatorial Nullstellensatz. (2012) (pl). manuscript.
  4. Jędrzej Kula. Combinatorial Nullstellensatz. slides. (2021).

(the seminar will only be online)

25.03.2021 16:15
Bartłomiej Bosek
Local Dimension of Planar Poset

In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter.

Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter. Local Dimension is Unbounded for Planar Posets. arXiv, pages 1-12, 2017.

(the seminar will only be online)

18.03.2021 16:15
Bartłomiej Bosek
The 1/3 - 2/3 conjecture

A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field.

(the seminar will only be online)

11.03.2021 16:15
Jędrzej Hodor
Polynomial Treedepth Bounds in Linear Colorings

Centered graph coloring is graph coloring, such that for every connected subgraph, this subgraph contains a vertex with a unique color (we call such a vertex center). Linear coloring is coloring, such that every path has a center. We denote by cen(G) and lin(G) respectively, a minimal number of colors needed. It is obvious that lin(G) ≤ cen(G). What about the other direction? Authors of the paper show that cen f(lin), where f is a polynomial of the degree 190. Moreover, the authors conjecture that cen 2 lin for every graph. What is interesting, we don't know how to prove such abound even for trees. Luckily, for some classes of graphs, we can do better than 190-poly. During the seminar, I will present results for simple classes of graphs and I will try to sketch the general proof. In particular, I will present a cubic bound for interval graphs. The proof in the paper is incorrect, but I and dr Micek managed to fix it. Finally, I will present our new result for graphs with bounded path width.

  1. Jeremy Kun, Michael P. O’Brien, Marcin Pilipczuk, and Blair D. Sullivan. Polynomial Treedepth Bounds in Linear Colorings. Algorithmica. volume 83, pages 361–386. 2021.
  2. Jędrzej Hodor. Polynomial Treedepth Bounds in Linear Colorings. slides. 2021.

(the seminar will only be online)

04.03.2021 16:15
Bartłomiej Bosek
Majority choosability of digraphs

One of the variations of coloring a graph is assigning colors to vertices such that for each vertex v, at most half of the neighbors of v have the same color as v. Such coloring is called majority coloring of the graph. The goal is to color the graph as a majority with the fewest possible colors. During the presentation, various variants of this problem, historical results, the latest results as well as still intriguing hypotheses will be discussed. Among other things, the results of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented.

  1. László Lovász, On decomposition of graphs Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences, 1, 237–238, 1966.
  2. Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 25, 303–312, 1974.
  3. Dominic van der Zypen, Majority coloring for directed graphs MathOverflow, 2016.
  4. Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, and David R. Wood, Majority colourings of digraphs, Electronic Journal of Combinatorics, 24(2):Paper 2.25, 9, 2017.
  5. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Majority Choosability of Digraphs Electronic Journal of Combinatorics, 24(3), Paper 3.57, 2017.
  6. António Girao, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Samal, Linear bound for majority colourings of digraphs, Electronic Journal of Combinatorics, 25(3):Paper 3.29, 4, 2018.
  8. Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak, Majority Coloring Game, Discrete Applied Mathematics, 255, 15–20, 2019.

(the seminar will only be online)

25.02.2021 16:15
Kamil Kropiewnicki
Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming

We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the Exponential Time Hypothesis fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems. This presentation might be of interest for, among the others, the participants of the Algorithmic Game Theory course as it presents the modern approach for maximizing revenue in second-price auctions.

  1. Joey Huchette, Haihao Lu, Hossein Esfandiari, Vahab Mirrokni. Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming. arXiv:2002.08841. 2020.
  2. Kamil Kropiewnicki. Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming. slides. 2021.

(the seminar will only be online)

28.01.2021 17:00
Rafał Burczyński
Bollobás-Eldridge-Catlin Conjecture on graph packing

Let G1, G2 be n-vertex graphs. We say that they pack if they are edge-disjoint subgraphs of a complete graph on n vertices. The Bollobás-Eldridge-Catlin conjecture states that if (Δ(G1) + 1) (Δ(G2) + 1) < n + 1, then G1 and G2 pack. During the seminar, we will take a look at current results related to this problem, i.e. classes of graphs for which it has been proven as well as similar conjectures stemming from it.

  1. Rafał Burczyński. Bollobás-Eldridge-Catlin Conjecture. slides. 2021.

(the seminar will only be online)

28.01.2021 16:15
Weronika Lorenczyk
The Cap Set Conjecture

The cap set problem asks how large can a subset of Z/3Zn be and contain no lines or, more generally, how can large a subset of Z/pZn be and contain no arithmetic progression. The problem was open until 2016 when its basic version was solved. During the lecture, we'll see the motivation for thinking about this. It appears there are some interesting applications of this result in combinatorics, geometry, and even board games.

  1. Weronika Lorenczyk. Cap Conjecture - motywacje i zastosowania. slides. 2021. (Polish)

(the seminar will only be online)

21.01.2021 17:00
Bartosz Wodziński
Graph Removal Lemma

Let H be a graph on h vertices. The Graph Removal Lemma states that for any ε > 0, there exists a constant δ(ε, H) > 0 such that for any n-vertex graph G with fewer than δnh subgraphs isomorphic to H, it is possible to eliminate all copies of H by removing at most εn2 edges from G. It has several important consequences in number theory, discrete geometry, graph theory, and computer science.

During the seminar, I will discuss this lemma and its extensions. I will also tell about some of its applications, such as graph property testing and Szeremedi's Theorem proof.

  1. David Conlon, Jacob Fox. Graph removal lemmas. arXiv:1211.3487. 2012.
  2. Bartosz Wodziński. Graph removal lemma. slides. 2021.

(the seminar will only be online)

21.01.2021 16:15
Artur Kasymov
Machine learning in Combinatorial Optimization

Machine learning has already leaked almost all areas. What about Combinatorial Optimization? At this seminar, I will present basic ML concepts and methods in CO: Where you can add ML black box in your algorithm? Can heuristics be compared to ML? What are the recent achievements?

  1. Artur Kasymov. Machine learning in Combinatorial Optimization. slides. 2021.

(the seminar will only be online)

14.01.2021 17:00
Bruno Pitrus
Seven trees in one: objects of categories as complex numbers

Consider the following absurd argument concerning planar, binary, rooted, unlabelled trees. Every such tree is either the trivial tree or consists of a pair of trees joined together at the root, so the set T of trees is isomorphic to 1+T². Pretend that T is a complex number and solve the quadratic T = 1+T² to find that T is a primitive sixth root of unity and so T⁶ = 1. Deduce that T⁶ is a one-element set; realize immediately that this is wrong. Notice that T⁷ = T is, however, not obviously wrong, and conclude that it is therefore right. In other words, conclude that there is a bijection T⁷ ≅ T built up out of copies of the original bijection T ≅ 1+T²: a tree is the same as seven trees.

  1. Andreas Blass. Seven Trees in One. arXiv:math/9405205. 1994.
  2. Marcelo Fiore, Tom Leinster. Objects of Categories as Complex Numbers. arXiv:math/0212377. 2002.
  3. Bruno Pitrus. Seven trees in one: objects of categories as complex numbers. slides. 2021.

(the seminar will only be online)

14.01.2021 16:15
Krzysztof Pióro
Gallai’s conjecture

A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most ⌈n/2⌉. Gallai’s Conjecture has been verified for many classes of graphs. In this seminar, we will cover some of these graph classes.

  1. Krzysztof Pióro. Hipoteza Gallai. slides. 2020.

(the seminar will only be online)

07.01.2021 16:15
Szymon Żak
Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes

In this seminar, I will cover general ideas that stand behind Aleph protocol. Aleph is a leaderless, fully asynchronous, Byzantine fault tolerant consensus protocol for ordering messages exchanged among processes. It is based on a distributed construction of a partially ordered set and the algorithm for reaching a consensus on its extension to a total order.

  1. Adam Gągol, Michał Świetek. Aleph: A Leaderless, Asynchronous, Byzantine Fault Tolerant Consensus Protocol. arXiv:1810.05256. 2018.
  2. Adam Gągol, Damian Leśniak, Damian Straszak, Michał Świetek. Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. arXiv:1908.05156. 2019.
  3. Adam Gągol, Damian Straszak. Blockchain Fundamentals. 2020.
  4. Szymon Żak. Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes. slides. 2021.

(the seminar will only be online)

17.12.2020 17:00
Jan Mełech
Hamiltonian paths/cycles in vertex-transitive/symmetric graphs

Graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on the vertices and edges surrounding it. In 1969, Lovasz conjectured that every finite connected vertex-transitive graph has Hamiltonian path. Moreover, up to now there are currently only five known connected vertex-transitive graphs not containing Hamiltonian cycle. In this seminar we will focus also on some other weaker variants of Lovasz conjecture related to other interesting class of graphs that encode the abstract structures of a groups - Cayley graphs.

  1. Jan Mełech. Hamiltonian paths/cycles in vertex-transitive/symmetric graphs. slides. 2020.

(the seminar will only be online)

17.12.2020 16:15
Mateusz Kaczmarek
From linear lambda terms to rooted trivalent maps

Recent work on the combinatorics of the linear lambda term shows that it has various connections to the theory of graph surfaces (maps). Based on paper [1] I will present a bijection between linear lambda terms (presented as diagrams) and rooted trivalent maps. Also, I will cover the recent conjecture proposed in 2019 that a special class of planar lambda terms can be counted the same way that rooted bicubic maps.

  1. Noam Zeilberger. Linear lambda terms as invariants of rooted trivalent maps. arXiv:1512.06751. 2015.
  2. Mateusz Kaczmarek. From linear lambda terms to rooted trivalent maps. slides. 2020.

(the seminar will only be online)

10.12.2020 17:00
Wojciech Buczek
Inscribed square problem

Let C be a Jordan curve. We say that polygon P is inscribed in C if all vertices of P belong to C. In the inscribed square problem we ask if every Jordan curve admits an inscribed square. It's also known as "Toeplitz’s conjecture" or the "Square peg problem". In this seminar, we will show some equivalent problems to this conjecture and focus on special cases of the Jordan curves.

  1. Wojciech Buczek. Inscribed square problem. slides. 2020.

(the seminar will only be online)

10.12.2020 16:15
Bartłomiej Jachowicz
Parameterized by treewidth algorithms for Hamiltonian Cycle

The Hamiltonian Cycle problem is one of the oldest and most common NP-complete problems. It consists of checking whether in a given graph there is a cycle visiting each vertex exactly once. I will present a parameterized algorithm based on graph tree decomposition. Assuming that a nice tree decomposition of the width k is known at the input Hamiltonian cycle problem can be solved in a time 2(O(k))n(O(1)).

  1. Bartłomiej Jachowicz. Parameterized by treewidth algorithms for Hamiltonian Cycle. slides. 2020.

(the seminar will only be online)

03.12.2020 17:00
Michał Zwonek
Approximate Distance Oracles

Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v∈V, returns an approximation to the actual distance between u and v which is within some bounded stretch factor of the true distance. The first work in this area was done by Mikkel Thorup and Uri Zwick, they devised an oracle with construction time being O(kmn(1/k)) and with the space complexity of O(kn(1+1/k)). The achieved stretch, that is the measure of how accurate the answer by the approximate oracle will be, is bounded by (2k-1). The query time is O(k), this has been subsequently improved to O(log n) by Wulff-Nilsen and to O(1) by Shiri Chechik.

  1. Michał Zwonek. Approximate Distance Oracles. slides. 2020.

(the seminar will only be online)

03.12.2020 16:15
Wojciech Grabis
Double-critical graph conjecture

A connected graph G is called double-critical if the chromatic number of G decreases by two if any two adjacent vertices of G are removed. In 1966, Erdős and Lovász conjectured that the only double-critical n-chromatic graph is the complete graph on n vertices. During the seminar, I will present what has been verified about the conjecture.

  1. Wojciech Grabis. Double-critical graph conjecture. slides. 2020.

(the seminar will only be online)

26.11.2020 17:00
Krzysztof Potępa
Erdős–Hajnal conjecture

A well-known theorem of Erdős states that there exists a graph on n vertices, with no clique or independent set of a size larger than O(log n). The Erdős–Hajnal conjecture says it is very different if we consider families of graphs defined by forbidden induced subgraphs. Specifically, it is conjectured that for every graph H, there exists a constant δ(H) such that every H-free graph G has either a clique or independent set of size |V(G)|δ(H). We will discuss some classes of graphs for which the conjecture has been proven, as well as weaker theorems that hold for all graphs.

  1. Krzystzof Potępa. The Erdős–Hajnal conjecture. slides. 2020.

(the seminar will only be online)

26.11.2020 16:15
Marcin Serwin
(m,n)-cycle cover conjectures

An (m,n)-cycle cover is a covering of a graph consisting of m cycles such that every edge is covered exactly n times. For positive integers m, n it is natural to ask what family of graphs have (m,n)-cycle covers. The answers are known for some values, but for many others, they are conjectured or totally open.

  1. Marcin Serwin. (m,n)-cycle cover conjectures. slides. 2020.

(the seminar will only be online)

12.11.2020 16:15
Bartłomiej Bosek
Harmonious Coloring of Hypergraphs

A harmonious coloring of a k-uniform hypergraph H is a vertex coloring such that no two vertices in the same edge share the same color, and each k-element subset of colors appears on at most one edge. The harmonious number h(H) is the least number of colors needed for such a coloring. We prove that k-uniform hypergraphs of bounded maximum degree Δ satisfy h(H) = O(k√k!m), where m is the number of edges in H which is best possible up to a multiplicative constant. Moreover, for every fixed Δ, this constant tends to 1 with k → ∞. We use a novel method, called entropy compression, that emerged from the algorithmic version of the Lovász Local Lemma due to Moser and Tardos. This is joint work with Sebastian Czerwinski, Jarosław Grytczuk, and Paweł Rzazewski.

  1. Bartłomiej Bosek, Jarosław Grytczuk, Paweł Rzążewski, Sebastian Czerwiński. Harmonious coloring of uniform hypergraphs. Applicable Analysis and Discrete Mathematics, 10(1), 73-87, 2016.

(the seminar will only be online)

05.11.2020 16:15
Piotr Mikołajczyk
Polynomial algorithms for CFGs via semiring embeddings

A few years ago M. Might et al. published somehow unusual approach to parsing context-free grammars by using derivative operator. Later it was proven, that its worst case complexity is polynomial, putting it on a par with other classical approaches. We introduce an elegant generalization to this method by a generic algorithm parametrized with a semiring. Depending on the chosen algebra we can obtain polynomial algorithms for problems like parsing, recognizing or counting parse trees for CFGs.

  1. Piotr Mikołajczyk. Polynomial algorithms for CFGs via semiring embedding. slides. 2020.

(the seminar will only be online)

29.10.2020 16:15
Bartłomiej Bosek
Majority choosability of digraphs

One of the variations of coloring a graph is assigning colors to vertices such that for each vertex v, at most half of the neighbors of v have the same color as v. Such coloring is called majority coloring of the graph. The goal is to color the graph as a majority with the fewest possible colors. During the presentation, various variants of this problem, historical results, the latest results as well as still intriguing hypotheses will be discussed. Among other things, the results of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented.

  1. László Lovász, On decomposition of graphs Studia Scientiarum Mathematicarum Hungarica. A Quarterly of the Hungarian Academy of Sciences, 1, 237–238, 1966.
  2. Paul D. Seymour, On the two-colouring of hypergraphs, The Quarterly Journal of Mathematics. Oxford. Second Series, 25, 303–312, 1974.
  3. Dominic van der Zypen, Majority coloring for directed graphs MathOverflow, 2016.
  4. Stephan Kreutzer, Sang-il Oum, Paul D. Seymour, Dominic van der Zypen, and David R. Wood, Majority colourings of digraphs, Electronic Journal of Combinatorics, 24(2):Paper 2.25, 9, 2017.
  5. Marcin Anholcer, Bartłomiej Bosek, Jarosław Grytczuk, Majority Choosability of Digraphs Electronic Journal of Combinatorics, 24(3), Paper 3.57, 2017.
  6. António Girao, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Samal, Linear bound for majority colourings of digraphs, Electronic Journal of Combinatorics, 25(3):Paper 3.29, 4, 2018.
  8. Bartłomiej Bosek, Jarosław Grytczuk, Gabriel Jakóbczak, Majority Coloring Game, Discrete Applied Mathematics, 255, 15–20, 2019.

(the seminar will only be online)

22.10.2020 16:15
Bartłomiej Bosek
Conjecture 1/3 - 2/3

A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field.

(the seminar will only be online)

15.10.2020 16:15
Vladyslav Rachek
Small weak epsilon-nets

Let P be a set of n points in R2, ε > 0. A set of points Q is called a weak ε-net for P with respect to a family S of objects (e.g. axis-parallel rectangles or convex sets) if every set from S containing more than εn points of P contains a point from Q. Let R be the family of all axis-parallel rectangles in R2 and εRk be the smallest real number such that for any P there exists a weak εRk-net of size k. The work by Aronov et al. suggests that the inequality εRk ≤ 2/(k+3) may hold. In this talk we present the complete proofs of this inequality for k=1,...,5 and prove that this bound is tight for k=1,2,3. Besides, it is not clear how to construct optimal nets. Langerman conjectured that k-point 2/(k+3)-nets can be chosen from some speciffc set of points which are the intersections of grid lines, where the grid is of size k×k. We give counterexamples to this conjecture for nets of size 3 through 6.

  1. Vladyslav Rachek. Small weak epsilon-nets in families of rectangles. Bachelor's Thesis. Jagiellonian University. 2020.
  2. B. Aronov, F. Aurenhammer, F. Hurtado, S. Langerman, D. Rappaport, C.Seara, and S. Smorodinsky. Small weak epsilon-nets. Computational Geometry: Theory and applications. 42(5), 2009. pp. 455-462.
  3. Vladyslav Rachek. On small weak epsilon-nets for axis-parallel rectangles. slides. 2020.

(the seminar will only be online)

08.10.2020 16:15
Bartłomiej Bosek
From the 1-2-3 Conjecture to the Riemann Hypothesis

A series of open (and solved) problems will be presented at the seminar, starting with the 1-2-3 Conjecture and ending with the Riemann Hypothesis.

  1. Jarosław Grytczuk. From the 1-2-3 conjecture to the Riemann hypothesis. European Journal of Combinatorics, 91, 2021, 103213.

(the seminar will only be online)

10.06.2020 17:00
Bartosz Wodziński
On the unique games conjecture

For many hard problems, instead of solving them directly, we need good approximation algorithms. Apart from good their time complexity and decent approximation factor guarantee, we would like to know whether they achieve the best possible approximation ratio (assuming P ≠ NP) possible. Unfortunately, for many NP-complete problems, there is a huge gap between best-known approximation ratio and the ratio that is proved to be unachievable in polynomial time. For instance, for Vertex Cover problem, we don't know any algorithm having a better ratio than 2, and it has been proved in 2005 that it is impossible to get a better ratio than ~1.36. As an attempt to fill in this gap, in 2002, the so-called Unique Games Conjecture was formulated by Khot. It states that having a (1-𝜀)-satisfiable instance of Unique Label Cover problem, it is NP-hard to find a solution satisfying even epsilon fraction of constraints. Assuming it, we are able to prove many tight inapproximability results, for example, it implies that Goemans-Williamson Algorithm for Max-Cut problem achieves the best possible approximation rate. It also follows that we cannot get any better ratio than 2 in the case of Vertex Cover problem. The Unique Games Conjecture is an unusual open problem since the academic world is about evenly divided on whether it is true or not. During the seminar, I will cover this conjecture in more details giving more examples of its influence and presenting recent progress in order to prove it.

  1. Subhash Khot. On the Unique Games Conjecture (Invited Survey). 2010 IEEE 25th Annual Conference on Computational Complexity, Cambridge, MA, 2010, pp. 99-121.
  2. Bartosz Wodziński. Unique Games Conjecture. slides. 2020.

(the seminar will only be online)

10.06.2020 16:15
Gabriela Czarska
The Lonely Runner Conjecture

Abstract. Suppose that k runners having different constant speeds run laps on a circular track of unit length. The Lonely Runner Conjecture states that, sooner or later, any given runner will be at distance at least 1/k from all the other runners. We prove that with probability tending to one, a much stronger statement holds for random sets in which the bound 1/k is replaced by 1/2 − ε. The proof uses Fourier analytic methods. We also point out some consequences of our result for colouring of random integer distance graphs.

  1. Gabriela Czarska. Lonely runner conjecture. slides. 2020.

(the seminar will only be online)

04.06.2020 17:00
Paweł Mader
Oblivious routing on 2d grid

Oblivious routing is a routing problem, in which a packet path is selected independently from path choices of other packets. One of the open problems is to find networks for which there exists an oblivious routing algorithm, which allows simultaneously optimizing stretch and congestion of the network. We are presenting an algorithm for oblivious routing on 2dgrid, which is O(log n) approximation for congestion and Θ(1) approximation of stretch.

(the seminar will only be online)

04.06.2020 16:15
Raja L'hamri
Mohammed V University
Examples of codes from zero-divisor graphs

In 2013, Dankelmann, Key, and Rodrigues introduced and investigated codes from incidence matrices of a graph. Several authors have been developed their study to several context. In this talk, we present some properties of codes associated with zero divisor graphs. Recall, the zero divisor graph of R denoted by Γ(R), is the simple graph associated with R whose set of vertices consists of all nonzero zero-divisors of R such that two distinct vertices x and y are joined by an edge if xy = 0. This is joint work with K. Abdelmoumen, D. Bennis, and F. Taraza.

  1. D. Bennis, J. Mikram, and F. Taraz. On the extended zero divisor graph of commutative rings. Turkish Journal of Mathematics. 40, 376-388, 2016.
  2. P. Dankelmann, J. D. Key, and B. G. Rodrigues. Codes from incidence matrices of graphs. Des. Codes Cryptogr. 68, 373-393, 2013.
  3. D. F. Anderson, P. S. Livingston. The Zero-Divisor Graph of a Commutative Ring. Journal of Algebra. 217(2), 434-447 , 1999.
  4. Raja L'hamri.Codes from zero-divisor graphs. slides. 2020.

(the seminar will only be online)

28.05.2020 17:00
Michał Stobierski
The 1-2-3 Conjecture

We all know how important mathematical theorems are in general. Less obvious is the fact that theorems in one area like algebra or number theory could have a significant impact on another. In our case, these will be combinatorial problems. In this presentation, We will go through a few simple graph coloring questions (based on the original 1-2-3 Conjecture), which unfortunately don't have simple solutions at all and we'll classify them. Moreover, thanks to Combinatorial Nullstellensatz and some greedy techniques, we will be able to prove some weaker versions of our original claims. And finally, we will see how one simple question, through a chain of small modifications, can lead us to completely different problems.

  1. Michał Stobierski. The 1-2-3 Conjecture. slides. 2020.

(the seminar will only be online)

28.05.2020 16:15
Rafał Byczek
Wegner’s conjecture - colouring the square of a planar graph

The square G2 of a graph G is the graph with the same vertex set in which two vertices are joined by an edge if their distance in G is at most two. The chromatic number of the square of a graph G is between D + 1 and D+ 1, where D is the maximum degree of G. Equivalently, the square coloring of a graph is to color the vertices of a graph at distance at most 2 with different colors.

In 1977, Gerd Wegner proved that the square of cubic planar graphs is 8-colorable. He conjectured that his bound can be improved - the chromatic number of G2 is at most 7, if D = 3, at most D + 5, if 4 ≤ D ≤ 7, and [3D / 2] + 1, otherwise. Wegner also gave some examples to illustrate that these upper bounds can be obtained.

C. Thomassen (2006) proved the conjecture is true for planar graphs with D = 3. The conjecture is still open for planar graphs with D ≥ 4. However several upper bounds in terms of maximum degree D have been proved as follows. In 1993, Jonas proved that χ(G2) ≤ 9D-19, for planar graphs with D ≥ 5. Agnarsson and Halldorson showed that for every planar graph G with maximum degree D ≥ 749, χ(G2) ≤ [9D / 5] + 2. Van den Heuvel and McGuinness (2003) showed that χ(G2) ≤ 2D + 25, Bordin (2002) proved that χ(G2) ≤ [9D / 5] + 1, if D ≥ 47, and Molloy and Salavatipour (2005) proved χ(G2) ≤ [5D / 3] + 78, moreover, χ(G2) ≤ [5D / 3] + 25 if D ≥ 241. Moreover, conjecture is confirmed in the case of outerplanar graphs and graphs without K4 minor.

The aim of the seminar will be to present the main facts about Wegner’s conjecture and main techniques and ideas which were used to prove some upper bounds. The presentation will be based on my master thesis.

  1. Rafał Byczek. Wegner’s conjecture Colouring the square of a planar graph. slides. 2020.

(the seminar will only be online)

21.05.2020 16:15
Wojtek Grabis
Algorithms for Destructive Shift Bribery.

Destructive Shift Bribery is a problem in which we are given an election with a set of candidates and a set of voters, a budget , a despised candidate and price for shifting the despised candidate in the voters rankings. Our objective is to ensure that selected candidate cannot win the election. We're going to study the complexity of this problem under diffrent election methods.

  1. Andrzej Kaczmarczyk, Piotr Faliszewski. Algorithms for Destructive Shift Bribery. arXiv:1810.01763. 2018.
  2. Wojtek Grabis. Conflict-free Replicated Data Types. slides. 2020.

(the seminar will only be online)

14.05.2020 17:00
Jan Mełech
Upper Bounds for the domination numbers of graphs

Sharareh Alipour and Amir Jafari showed various upper bounds for minimal cardinality of (a,b)-dominating set. For positive integers a and b, a subset S ⊆ V(G) is an (a,b)-dominating set if every vertex v ∈ S is adjacent to at least a vertices inside S and every vertex v ∈ V\S is adjacent to at least b vertices inside S. To achieve upper bounds, the authors used Turan's Theorem and Lovasz Local Lemma. These tools allowed them to obtain well-known bounds in a simpler way or new improved bounds in some special cases, including regular graphs.

  1. Sharareh Alipour, Amir Jafari. Upper Bounds for the Domination Numbers of Graphs Using Turán’s Theorem and Lovász Local Lemma. Graphs and Combinatorics35, 2019, 1153-1160.
  2. Jan Mełech. Upper bounds for domination number. slides. 2020.

(the seminar will only be online)

14.05.2020 16:15
Szymon Kapała
Goldbach conjectures (weak and strong).

(the seminar will only be online)

07.05.2020 16:15
Michał Zwonek
3-flow conjecture

3-flow-conjecture
“Every 4-edge-connected graph has a nowhere-zero 3-flow.”

Grötzsch proved that every triangle free (and loopless) planar graph is 3-colorable. By flow/coloring duality, this is equivalent to the statement that every 4-edge-connected planar graph has a nowhere-zero 3-flow. The 3-flow conjecture asserts that this is still true without the assumption of planarity.

Jaeger proved that 4-edge-connected graphs have nowhere-zero 4-flows. The following weak version of the 3-flow conjecture used to remain open until 2010, but the original 3-flow conjecture remains wide open.

C̶o̶n̶j̶e̶c̶t̶u̶r̶e̶ (The weak 3-flow conjecture (Jaeger))
“There exists a fixed integer k so that every k-edge-connected graph has a nowhere-zero 3-flow.” 

These problems and the surrounding results will be presented during the seminar.

  1. Carsten Thomassen. The weak 3-flow conjecture and the weak circular flow conjecture. Journal of Combinatorial Theory, Series B102(2), 2012, 521-529.
  2. Fuyuan Chen, Bo Ning. A note on nowhere-zero 3-flow and Z_3-connectivity. arXiv:1406.1554. 2014.
  3. Michał Zwonek. Nowhere Zero Flow and related open problems, slides. 2020.

(the seminar will only be online)

30.04.2020 17:00
Mateusz Kaczmarek
χ-boundedness

If a graph has bounded clique number and sufficiently large chromatic number, what can we say about its induced subgraphs? To answer that question Paul Seymour and Alex Scott took a closer look at recent progress in this field in their χ-boundedness survey. Based on their work I will present some results on forests and holes and few open problems like Gyárfás-Sumner conjecture or χ-boundedness connection to Erdős-Hajnal conjecture.

  1. Alex Scott, Paul Seymour. A survey of χ-boundedness. arXiv:1812.07500. 2018.
  2. Mateusz Kaczmarek. χ-boundedness, slides. 2020.

(the seminar will only be online)

30.04.2020 16:15
Kornel Dulęba
Odd Perfect numbers

A number is perfect if it is equal to the sum of its divisors. So far only even perfect numbers have been found. For example, it was proven that squares of Mersenne’s numbers are perfect. However, no one has been able to prove that odd perfect numbers don’t exist. I’m going to start by presenting a summary of known facts about odd prime numbers. Then I’ll prove that an odd perfect number with at least eight distinct prime factors has to be divisible by 5.

  1. John Voight. On the nonexistence of odd perfect numbers. MASS selecta, 293–300, Amer. Math. Soc., Providence, RI, 2003.
  2. Kornel Dulęba. Perfect Numbers. slides. 2020.

(the seminar will only be online)

23.04.2020 17:00
Bartłomiej Jachowicz
Lonely runner conjecture

One of number theory open problem is the Lonely Runner Conjecture. It is interesting for several reasons. First the conjecture is relatively intuitive to grasp and easy to state. This conjecture can be find in two different contexts: as a problem in Diophantine’s approximation and as a geometric view obstruction problem. What is more, the difficulty of proving the Lonely Runner Conjecture may seem to increase exponentially with the number of runners. I present statement of the conjecture and known partial results.

  1. Clayton Barnes II. The Lonely Runner Conjecture. arXiv:1211.2482. 2012.
  2. Thomas W. Cusick, Jorg M. Wills. Lonely runner conjecture. Open Problem Garden. 2007.
  3. Bartłomiej Jachowicz. Lonely Runner Conjecture. slides. 2020.

(the seminar will only be online)

23.04.2020 16:15
Filip Bartodziej
Meyniel’s conjecture on the cop number

A cops and robbers problem determines if the number of cops is sufficient to always catch a robber in a game with defined rules played on an undirected graph. Cop number of a graph is the minimal number of cops necessary for cops to win in that game on the specific graph. Mayniel’s conjuncture remains an open problem and states that cop number for graphs of order n is sqrt(n). I’ll present a survey of results achieved that are related to this conjecture.

  1. William Baird, Anthony Bonato. Meyniel's conjecture on the cop number: a survey. arXiv:1308.3385. 2013.
  2. Filip Bartodziej. Meyniel’s conjecture. slides. 2020.

(the seminar will only be online)

16.04.2020 17:00
Mateusz Pabian
Synchronizing Automata and the Černý Conjecture

I present many results and finally open problem related to synchronizing automata and synchronizing word sends any state of the DFA to one and the same state. This leads to the some natural problems such as: how can we restore control over such a device if we don't know its current state but can observe outputs produced by the device under various actions? I prove some uperbounds for length of this kind of word and in particular I will make a statement of Cerny conjecture.

  1. Mikhail V. Volkov. Synchronizing Automata and the Černý Conjecture. LATA 2008. 11-27.
  2. Mateusz Pabian. Synchronizing Automata and the Černý Conjecture. slides. 2020.

(the seminar will only be online)

16.04.2020 16:15
Adrian Siwiec
Online Computation with Untrusted Advice

The advice model of online computation captures the setting in which the online algorithm is given some partial information concerning the request sequence. We study online computation in a setting in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze online algorithms that are robust and perform well even when the advice is generated in a malicious, adversarial manner.To this end, we focus on well-studied online problems such as ski rental, online bidding, bin packing, and list update.

  1. Spyros Angelopoulos, Christoph Durr, Shendan Jin, Shahin Kamali, and Marc Renault. Online Computation with Untrusted Advice. arXiv:1905.05655. 2019.
  2. Adrian Siwiec. Online Computation with Untrusted Advice. slides. 2020.

(the seminar will only be online)

09.04.2020 17:00
Wojciech Buczek
Seymour's Second Neighbourhood Conjecture

Seymour's Second Neighbourhood Conjecture tells us, that any oriented graph has a vertex whose outdegree is at most its second outdegree, which is also known as Second neighborhood problem. Intuitively, it suggests that in a social network described by such a graph, someone will have at least as many friends-of-friends as friends. We will say about Chen-Shen-Yuster prove, that for any digraph D, there exists a vertex v such that |N++(v)|≥γ|N+(v)|, where γ=0.67815. We will consider graphs, in which we know, that such vertex exists. We will also say about unsuccessful attempts at proving this conjecture.

  1. Salman Ghazal. Seymour's second neighborhood conjecture for tournaments missing a generalized star. arXiv:1106.0085, 2011.
  2. Tyler Seacrest. Seymour's Second Neighborhood Conjecture for Subsets of Vertices. arXiv:1106.0085, 2018.
  3. Wojciech Buczek. Seymour’s Second Neighbourhood Conjecture. slides. 2020.

(the seminar will only be online)

09.04.2020 16:15
Mikołaj Twaróg
Collatz conjecture

The Collatz conjecture, also known as 3n + 1 conjecture considers a function, which returns n/2 if n is even and 3n + 1 if n is odd. The conjecture states that for every n we can repeatedly apply this function to eventually reach 1. I will talk about different approaches to proving this conjecture.

  1. Mikołaj Twaróg. Collatz conjecture. slides. 2020.

(the seminar will only be online)

02.04.2020 17:00
Adam Pardyl
Undirected edge geography

The game of edge geography is played by two players who alternately move a token on a graph from one vertex to an adjacent vertex, erasing the edge in between. The player who first has no legal move loses the game. We analyze the space complexity of the decision problem of determining whether a start position in this game is a win for the first player. We also show a polynomial time algorithm for finding winning moves for bipartite graphs.

  1. Aviezri S. Fraenkel, Edward R. Scheinerman, Daniel Ullman. Undirected Edge Geography. Theoretical Computer Science112(2), 1993, 371-381.
  2. Adam Pardyl. Undirected edge geography. slides. 2020.

(the seminar will only be online)

02.04.2020 16:15
Piotr Mikołajczyk
ARRIVAL game

Consider a directed graph such that every vertex has at most 2 outgoing edges - one of them is labeled as 'open' (we can traverse it) and the second one is labeled as 'closed' (we cannot traverse it). Every time we go somewhere from the vertex v, labels at its two edges are swapped, so the next time we visit v, we will take another direction. Given designated two vertices: origin and destination, we need to decide, whether eventually we will reach destination starting in the origin. This problem lies in both NP and coNP, but it is still an open question whether it belongs to P.

  1. Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, Emo Welzl. ARRIVAL: A zero-player graph game in NP ∩ coNP. arXiv:1605.03546. 2020.
  2. Piotr Mikołajczyk. ARRIVAL game. slides. 2020.

(the seminar will only be online)

26.03.2020 16:15
Vladyslav Rachek
Small weak epsilon-nets

Let P be a set of n points in R2. A point q (not necessarily in P) is called a centerpoint of P if each closed half-plane containing q at least ⌈n/3⌉ points of P, or, equivalently, any convex set that contains more than 2/n points of P must also contain q. It is a well-known fact that a centerpoint always exists and the constant 2/3 is the best possible. Can we improve this constant by using, say, two points, or some other small number of points? In the presentation we'll try to answer those questions.

Vladyslav Rachek. Small weak epsilon-nets. slides. 2020.

(the seminar will only be online)

 
19.03.2020 17:00
Kamil Rajtar
How voting can be manipulated during selecting voting places

During today presentation we will learn how we can use graph theory to proof hardness of general problem of manipulating poll outcome. Based on paper: "Selecting Voting Locations for Fun and Profit" written by Zack Fitzsimmons and Omer Lev.

Zack Fitzsimmons, Omer Lev. Selecting Voting Locations for Fun and Profit. arXiv:2003.06879. 2020.

(the seminar will only be online)

  • 1
  • 2