Optymalizacja Kombinatoryczna

dr hab. Bartłomiej Bosek

czwartek 16:00-17:30, sala 0174

Jest to seminarium magisterskie, którego tematyka dotyczy optymalizacji kombinatorycznej. W szczególności interesują nas następujące tematy:

  1.   Zaawansowane algorytmy znajdujące skojarzenia w grafach (także dwudzielnych) w przypadkach nieważonych i ważonych krawędzi.

  2.   Problemy konstruowania on-line skojarzeń w grafach dwudzielnych, AdWords Problem - rozwiązania optymalne, randomizowane.

  3.   Algorytmiczne aspekty pokrycia uniłańcuchami produktów częściowych porządków.

Strona seminarium z aktualna listą prac do zreferowania znajduje się tutaj.

Strona seminarium na UsosWeb znajduje się tutaj.

Forum seminarium znajduje się tutaj.

08.12.2022 16:00
Rafał Kilar
Minimal Non-Two-Colorable Hypergraphs and Minimal Unsatisfiable Formulas
  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. slides. (2022).
08.12.2022 16:45
Grzegorz Gawryał
On topological aspects of orientations
  1. H. de Fraysseix, P. Ossona de Mendez. On topological aspects of orientations. Discrete Mathematics. 229(1-3), 57-72. (2001).
  2. Grzegorz Gawryał. slides. (2022).
15.12.2022 16:00
Tomasz Mazur
Improved lower bound for the list chromatic number of graphs with no Kt minor
  1. Raphael Steiner. Improved lower bound for the list chromatic number of graphs with no Kt minor. arXiv:2110.09403. (2021).
  2. Tomasz Mazur. slides. (2022).
15.12.2022 16:45
Hubert Zięba
The 3-flow conjecture, factors modulo k, and the 1-2-3-conjecture
  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. slides. (2022).
05.01.2023 16:00
Aleksander Katan
A generalization of Konig's theorem
  1. L. Lovász. A generalization of Kónig's theorem. Acta Mathematica Academiae Scientiarum Hungaricae. 21, 443-446. (1970).
  2. Aleksander Katan. slides. (2022).
05.01.2023 16:45
Jakub Siuta
On Induced Subgraphs with All Degrees Odd
  1. A.D. Scott. On Induced Subgraphs with All Degrees Odd. Graphs and Combinatorics. 17, 539-553. (2001).
  2. Jakub Siuta. slides. (2022).
12.01.2023 16:00
Katzper Michno
On the discrepancy of circular sequences of reals
  1. Fan Chung, Ron Graham. On the discrepancy of circular sequences of reals. Journal of Number Theory. 164, 52-65. (2016).
  2. Katzper Michno. slides. (2022).
12.01.2023 16:45
Julia Biały
Can a party represent its constituency?
  1. Amoz Kats. Can a party represent its constituency? Public Choice. 44, 453-456. (1984).
  2. Julia Biały. slides. (2022).
19.01.2023 16:00
Jakub Dziarkowski
Note on Perfect Forests
  1. Gregory Gutin. Note on Perfect Forests. arXiv:1501.01079. (2015).
  2. Jakub Dziarkowski. slides. (2022).

Poprzednie referaty

01.12.2022 16:45
Szymon Salabura
Farey sequence and Graham’s conjectures
  1. Liuquan Wang. Farey sequence and Graham's conjectures. arXiv:2005.04429. (2020).
  2. Szymon Salabura. slides. (2022).
01.12.2022 16:00
Katarzyna Kępińska
Color-Critical Graphs on a Fixed Surface
  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. slides. (2022).
24.11.2022 16:45
Filip Konieczny
Factorizing regular graphs
  1. Carsten Thomassen. Factorizing regular graphs. Journal of Combinatorial Theory, Series B. 141, 343-351. (2020).
  2. Filip Konieczny. slides. (2022).
24.11.2022 16:00
Hubert Dej
On the Gap Structure of Sequences of Points on a Circle
  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. slides. (2022).
17.11.2022 16:00
Piotr Kaliciak
A counterexample to the lights out problem
  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. 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. 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. 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)

19.03.2020 16:15
Mateusz Tokarz
The Hadwiger-Nelson problem

We will focus on Hadwiger-Nelson problem - an open question from geometric graph theory that asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. There are a few interesting theorems related to the problem and results which we will go through. We will focus in particular on the most recent result of Aubrey de Grey who showed that the desired chromatic number is at least 5.

  1. Aubrey D.N.J. de Grey. The chromatic number of the plane is at least 5. arXiv:1804.02385. 2018.
  2. Mateusz Tokarz. slides. 2020.

(the seminar will only be online)

23.01.2020 16:15
Jan Gwinner
Spectrally Robust Graph Isomorphism

In the paper authors consider certain variants of Graph Isomorphism problem. They focus on properties of graph spectra and eigenspaces - namely if Laplacian of one of the graphs is greater or equal to another in Loewner ordering. In the first part of the paper they prove that one of the problems named Spectral Graph Dominance is NPC. The rest of the paper is devoted to an approximation algorithm for special case of the problem called Spectrally Robust Graph Isomorphism.

Alexandra Kolla, Ioannis Koutis, Vivek Madan, Ali Kemal Sinop. Spectrally Robust Graph Isomorphism. arXiv:1805.00181, 1-17, 2018.

16.01.2020 17:00
Gabriela Czarska
Driver surge pricing

Authors study Uber's pricing mechanisms from the perspective of drivers, presenting the theoretical foundation that has informed the design of Uber’s new additive driver surge mechanism. They present a dynamic stochastic model to capture the impact of surge pricing on driver earnings and their strategies to maximize such earnings.

Nikhil Garg, Hamid Nazerzadeh. Driver Surge Pricing. arXiv. 2019.

16.01.2020 16:15
Bartosz Podkanowicz
Planar graphs have bounded queue-number

The paper presents proof that the queue number of planar graphs is bounded. It also mentions generalizations of the result and other theorems that have similar proofs.

Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood. Planar graphs have bounded queue-number. arXiv. 2019.

09.01.2020 17:00
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.

Andrzej Kaczmarczyk, Piotr Faliszewski. Algorithms for Destructive Shift Bribery. arXiv. 2018.

09.01.2020 16:15
Dominik Gryboś
Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice

The paper shows that the Diffie-Hellman protocol is not as secure as we thought. The authors present the Logjam attack, which consists in quickly calculating discrete logarithms based on previously performed calculations. This can be done because many websites use the same prime numbers in the message encryption process.

David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelink, Paul Zimmermann. Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. WeakDH.org.

19.12.2019 17:00
Kamil Kropiewnicki
Impossibility of Distributed Consensus with One Faulty Proces

 

he consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.

Authors of the paper were awarded a Dijkstra Prize for this work - given to the most influential papers in distributed computing.

Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the Association for Computing Machinery, 32(2), 1985, 374-382.

19.12.2019 16:15
Filip Bartodziej
How to eat 4/9 of a pizza

Unevenly cut pizza is a frustrating occurrence. How can we then make sure that a friend is not trying to reduce our portion of the delicious meal? We will present a strategy which guarantees that one will leave the table satisfied, assuming that they started eating first.

Kolja Knauer, Piotr Micek, Torsten Ueckerdt. How to eat 4/9 of a pizza. arXiv. 2008.

12.12.2019 17:00
Krzysztof Michalik
Coloring planar graphs with 3 colors and no large monochromatic components

I will present a proof that there exists a function f(d), such that there exists a 3-coloring of any planar graph G in which each monochromatic subgraph has at most f(d) vertices, where d is the degree of the highest-degree vertex in G.

Louis Esperet, Gwenaël Joret. Coloring planar graphs with three colors and no large monochromatic components. arXiv, 1303.2487. 2013.

12.12.2019 16:15
Mateusz Kaczmarek
Hadwiger’s conjecture

Survey of Hadwiger's Conjecture from 1943, that for all t ≥ 0, every graph is either t-colorable or has a subgraph that can be contracted to the complete t+1 vertices graph. This conjecture is the tremendous strengthening of the four-color problem also known as map coloring problem.

Paul Seymour. Hadwiger’s conjecture.

05.12.2019 16:15
Kornel Dulęba
The Return of Coppersmith’s Atack: Practical Factorization of Widely Used RSA Moduli

During the seminar I will discuss a clever attack on RSA library used in Infineon chips. Researchers discovered that the prime factors used for constructing private keys have a peculiar form. This allowed them to use a modified version of Coppersmith algorithm to recover private key basing on their public counterpart in a reasonable time for keys up to 2048 bit long.

Dusan Klinec, Vashek Matyas, Matus Nemec, Marek Sys, Petr Svenda. The Return of Coppersmith’s A‚ack: Practical Factorization of Widely Used RSA Moduli.

28.11.2019 16:15
Mikołaj Twaróg
A Short Guide to Hackenbush

Hackenbush is a two player game played on a graph with a few marked vertices. Players alternate turns. Each turn consists of removing one edge from the graph and all vertices that lost their connection to all marked ones. Player, that can't make a move, loses. I will present three different variants of Hackenbush(Red-Blue Hackenbush, Green Hackenbush and R-G-B Hackenbush) with methods to determine, which player has a winning strategy.

Padraic Bartlett. A Short Guide to Hackenbush. VIGRE REU 2006.

21.11.2019 17:00
Adrian Siwiec
Edge Coloring Signed Graphs

We define a method for edge coloring signed graphs and what it means for such a coloring to be proper. It then turns out that Vizing's Theorem is a special case of the more difficult theorem concerning signed graphs.

Richard Behr. Edge Coloring Signed Graphs. arXiv. 2018.

21.11.2019 16:15
Paweł Palenica
Guess the Larger Number

We will discuss variations of a zero sum game where one player writes down two numbers on cards. The second player learns one of the numbers to make a guess which of the numbers is larger. We will show variations of the game where the second player has a greater chance of winning than 1/2.

Alexander Gnedin. Guess the Larger Number. arXiv. 2016.

07.11.2019 16:15
Kamil Rajtar
A Price-Based Iterative Double Auction for Charger Sharing Markets

Jie Gao, Terrence Wong, Chun Wang, and Jia Yuan Yu. A Price-Based Iterative Double Auction for Charger Sharing Markets. arXiv. 2019.

24.10.2019 16:15
Vladyslav Rachek
On Chromatic Number of Exact Distance Graphs

For any graph G and positive integer p we can consider "exact distance graph" G in which vertices x and y are connected if and only if their distance in G is exactly p. We can bound chromatic number of such graphs using notion of weak coloring numbers. Proof becomes particularly valuable for odd p and planar graphs G.

Jan van den Heuvel, H.A. Kierstead, Daniel A. Quiroz. Chromatic Numbers of Exact Distance Graphs. arXiv, abs/1612.02160. 2016.

17.10.2019 16:15
Vladyslav Rachek
Steinberg's conjecture is false

It's commonly known that planar graphs are at most 4-colorable. One possible direction towards determining when planar graphs can be 3-colorable is to narrow to particular planar graphs with enforced structure. For example, one can forbid cycles of length 4,5,...,k where k>=4. There is a conjecture of Steinberg from 1976, that planar graphs without cycles of length 4 and 5 (as subgraphs) are 3-colorable. It has been open problem till 2016, when it was disproved in joint paper of Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado, and we present proof from that paper.

Steinberg's Conjecture is false. Vincent Cohen-Addad, Michael Hebdige, Daniel Kral, Zhentao Li, Esteban Salgado. arXiv, abs/1604.05108. 2016.

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

One of the variations of graph coloring is the assignment of colors to vertices such that for each v vertex, at most half of the neighbors v have the same color as v. Such coloring is called the majority coloring of the graph. The goal is to color the graph in the above way with the smallest number of colors. During the presentation various variants of this problem will be discussed, historical results, the latest results, and still intriguing hypotheses. Among other things, the effects 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 Girão, Teeradej Kittipassorn, Kamil Popielarz, Generalized majority colourings of digraphs, Combinatorics, Probability and Computing, 26(6), 850–855, 2017.
  7. Fiachra Knox and Robert Šámal, 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.
03.10.2019 16:15
Bartłomiej Bosek
Choosability number of planar graphs

During the seminar, we will discuss some open problems regarding the choosability number of planar graphs and related problems.

13.06.2019 17:00
Bruno Pitrus
A Borsuk–Ulam Equivalent that Directly Implies Sperner’s Lemma

It is a known fact that Sperner's purely combinatorial lemma of triangulation is equivalent to theorems in the field of topology: Brouwer with a fixed point and Knastra-Kuratowski-Mazurkiewicz on covering the symplex. Both of these topological theorems have stronger versions (Borsuk-Ulam and Lusternik-Schnirelmann theorems on anti-inflammatory points). In the paper, the authors show a combinatorial analogue of Borsuk-Ulam theorem and use it to directly prove the Sperner lemma, closing the stronger trinity of theorems.

Kathryn L. Nyman, Francis Edward Su. A Borsuk–Ulam Equivalent that Directly Implies Sperner's Lemma. The American Mathematical Monthly 120 (2017), no. 4, 346-354.

13.06.2019 16:15
Paweł Palenica
Three famous theorems on finite sets

During the seminar I will present three statements about finite sets with evidence. Two of them are classic theorems of combinatorial power theory - theorems of Sperner and Erdős-Ko-Rado. The third of these is one of the most important theorems in finite set theory - the Hall theorem.

Martin Aigner, Günter M. Ziegler. Chapter 27 of Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

06.06.2019 16:15
Dominika Salawa
The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs

In computer game 'Lemmings', lemmings are placed in a level walking towards certain direction. When they encounter a wall, they turn and walk back in the direction they came from and when they encounter a hole, they fall. If a lemming falls beyond a certain distance, it dies. The goal is to guide lemmings to the exit by assigning them skills and modifying their behavior. I will show by polynomial-time reduction from 3-SAT that deciding whether particular level is solvable is an NP-Complete problem. This holds even if there is only one lemming in the level to save.

Graham Cormode. The Hardness of the Lemmings Game, or Oh no, more NP-Completeness Proofs.

16.05.2019 16:15
Krzysztof Maziarz
Exact Algorithms via Monotone Local Search

Parameterized algorithms can solve some optimization problems quickly, assuming a certain parameter is bounded: for example, when we aim to satisfy a SAT formula by setting at most k (out of n) variables to true. However, the same algorithms directly applied to the unbounded case (k = n) usually yield poor results. Here I will discuss a bridge between parameterized algorithms and general exact exponential-time algorithms. I will show a remarkably simple approach to obtaining a good exact exponential-time algorithm, given a good parameterized algorithm. The resulting algorithm will be randomized, but it is also possible to derandomize it with subexponential additional cost in the complexity. This approach, at the time of publishing, pushed the state-of-the-art for many optimization problems.

Fedor V. Fomin, Serge Gaspers, Daniel Lokshtanov, Saket Saurabh. Exact Algorithms via Monotone Local Search. arXiv. 2015.

09.05.2019 17:00
Anita Badyl
A Simplification of the MV Matching Algorithm and its Proof

Simple and effective algorithms solving the problem of finding maximum matchings in bipartite graphs had been known for years before a low-complexity algorithm for non-bipartite graphs was published for the first time. That algorithm is known as the Micali-Vazirani algorithm, and it constitutes an intricate combination of the Hopcroft-Karp algorithm for bipartite graphs and the Blossom algorithm for general graphs. It achieves the complexity of O(m√n), which demonstrates that matchings in general graphs are not harder to find than matchings in bipartite ones. We present an intuitive introduction to the algorithm, explaining its main definitions and procedures.

Vijay V. Vazirani. A Simplification of the MV Matching Algorithm and its Proof. arXiv. 2012.

09.05.2019 16:15
Kamil Rajtar
Rectangular tiling

During the seminar will be presented proofs of the seemingly geometrical problem of tiling a rectangle with tiles with at least one side of total length.

Martin Aigner, Günter M. Ziegler. Chapter 26 of Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

25.04.2019 17:00
Michał Stobierski
How 'hard' a video game can be?

Computer games are a well-studied branch of the theory of complexity. Many of them fit into a similar scheme, lying in the NP (and even NP-hard) and, thanks to Savitch's Theorem, in PSPACE (-hard). It turns out, however, that some of them, thanks to their unique mechanics, are able to simulate the operation of the Turing Machine and thus pose undecidable problems! An interesting example of such a game is Braid, on which this presentation is based. We will start by showing differences and similarities with other games, then we will show how to simulate the operation of the abstract 'counter machine' and talk about a particularly interesting variant of the game, which introduces an TM model that, when it writes to the tape, deletes all data on the tape to the right of the head. And despite the fact that it looks like simplified variant, it lies in EXPSPACE, making Braid a totally 'non-schematic' game.

25.04.2019 16:15
Rafał Byczek
The chromatic number of Kneser graphs

In 1955 the number theorist Martin Kneser posed a seemingly innocuous problem that became one of the great challenges in graph theory until a brilliant and totally unexpected solution, using the “Borsuk–Ulam theorem” from topology, was found by László Lovász twenty-three years later. It happens often in mathematics that once a proof for a long-standing problem is found, a shorter one quickly follows, and so it was in this case. Within weeks Imre Bárány showed how to combine the Borsuk–Ulam theorem with another known result to elegantly settle Kneser’s conjecture. Then in 2002 Joshua Greene, an undergraduate student, simplified Bárány’s argument even further, and it is his version of the proof that I present here.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

11.04.2019 17:00
Filip Bartodziej
Turán’s graph theorem

We’ll cover the Turan theorem from 1941, which provides a restriction on the number of edges in a graph that doesn’t contain an induced k-clique, depending on parameter k.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

11.04.2019 16:15
Mateusz Pabian
Gaming is a hard job, but someone has to do it!

General schemes relating the computational complex-ity of a video game to the presence of certain common elements or mechan-ics, such as destroyable paths, collectible items, doors opened by keys or activated by buttons or pressure plates, etc. Proofs of complexity of several video games, including Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3, and Starcraft.

Giovanni Viglietta. Gaming is a hard job, but someone has to do it! arXiv. 2013.

04.04.2019 17:00
Marcin Briański
A short story of graphs that count

In 1978 Thomason provided a simple, constructive proof of Smith’s theorem; in particular this proof provides a simple algorithm enables one to find a second Hamiltonian cycle whenever one is given a cubic graph and a Hamiltonian cycle in it. For a couple of years, the runtime of the algorithm remained unknown, with worst known cases being cubic (in the number of vertices), however in 1999 Krawczyk found an example of a graph family, such that Thomason’s algorithm takes time Ω(2n/8) where is the number of vertices in the input graph from the family.

In this talk, I will present a family of cubic, planar, and 3-connected graphs, such that Thomason’s algorithm takes time Θ(1.1812n) on the graphs in this family. This scaling is currently the best known.

04.04.2019 16:15
Mateusz Tokarz
The Slope Problem
28.03.2019 17:00
Vladyslav Hlembotskyi
The Angel of power 2 wins

Let's consider the following game: we have two players (they are called the angel and the devil) and an infinite chessboard. The angel is located in some cell on the board. Players make moves alternatively. The devil chooses any cell that is not occupied by the angle and blocks it. The angel can jump to any other cell which is at distance at most p (p is fixed) from its present location and is not blocked. The devil wins if the angel cannot jump to any other cell. The angel wins if it can avoid being captured forever. We will show that the angel of power 2 has a winning strategy.

András Máthé. The Angel of power 2 wins. Combinatorics, Probability and Computing 16 (2007), no. 3, 363–374.

28.03.2019 16:15
Katarzyna Bułat
Distributed tracing

The presentation will cover the topic of distributed tracing, which is an important issue in the field of distributed systems. Services are nowadays implemented as complex networks of related sub-systems and it is often hard to determine the source of performance problem in such complex structures. We will take a look at Dapper, a large-scale distributed systems tracing infrastructure, and discuss the challenges its designers had to face, as well as the opportunities the tool gives to programmers. We will discuss the core goals of effective instrumentation, analyze the problem of handling huge amount of tracing data and focus on security concerns.

21.03.2019 16:15
Adrian Siwiec
Online Maximum Matching with Recourse

Online maximum matching problem has a recourse of k, when the decision whether to accept an edge to a matching can be changed k times, where k is typically a small constant. First, we consider the model in which arriving edge never disapears. We show that greedy algorithm has competitive ratio of 3/2 for even k and 2 for odd k. Then we show an improvement for typical values of k and proceed to show a lower bound of 1+1/(k-1). Later, we discuss a model where edges can appear and disappear at any time and show generalized algorithms.

Spyros Angelopoulos, Christoph Dürr, and Shendan Jin. Online Maximum Matching with Recourse. arXiv. 2018.

14.03.2019 16:15
Bartłomiej Bosek
Open problem session

At the seminar were presented some interesting open problems in the field of graph theory.

07.03.2019 16:15
Kamil Kropiewnicki
Identities versus bijections

In 1740 Leonhard Euler began to work on counting partitions. It resulted in two fundamental papers in the field. Integer partitions have been an active field of study ever since, tackled by many including Srinivasa Ramanujan, Paul Erdős and Donald Knuth. We present a few beautiful proofs of identities using only basic generating functions and simple bijections.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

24.01.2019 16:15
Rafał Burczyński
Basic properties of 3CCP graphs

We will introduce a class of graphs called 3CCP, which contains graphs that are 3-connected, cubic (3-regular) and planar. It was shown by Tarjan that finding Hamiltonian cycle in a graph assuming these properties remains NP-complete - we will show the reduction from 3-SAT problem. After that we will present Smith's theorem about parity of number of Hamiltonian cycles containing given edge in cubic graphs and show elegant constructive proof using Thomason's lollipop method. After that we will show a class of graphs for which previous algorithm for finding second Hamiltonian cycle takes exponential number of steps.

17.01.2019 16:15
Adrian Siwiec
List coloring of Latin Squares

For each cell (i, j) of NxN square there is given a list C(i, j) of N colors. Can we choose a color for each cell in such a way that colors in each row and each column are distinct?

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

10.01.2019 16:15
Kamil Kropiewnicki
Shuffling cards

What do the birthday paradox, the coupon collector problem and shuffling cards have in common? What does it mean for a deck of cards to be "random" or "close to random"? How long does one have to shuffle a deck of cards until it is random? In practical use cases, the question is not about the asymptote - it is about the exact numbers.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

03.01.2019 16:15
Kamil Rajtar
Communication without errors

Main aim of the lecture is the answer for Claude Shannon's question from 1956: "Suppose we want to transmit messages across a channel (where some symbols may be distorted) to a receiver. What is the maximum rate of transmission such that the receiver may recover the original message without errors?"

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

20.12.2018 16:15
Filip Bartodziej
Cayley’s formula for the number of trees & How to guard a museum

First, several proofs for the number of labeled trees, each using different approach (bijection, linear algebra, recursion, double counting) will be presented. Second part of the seminar will introduce an interesting graph problem first raised by Victor Klee in 1973. This problem can be represented as placing guards in a museum to guard it properly - that is area of the museum must be completely covered by the field of view of the guards.

Martin Aigner, Günter M. Ziegler. Proofs from The Book. Sixth edition. Springer, Berlin, 2018. viii+326 pp. ISBN: 978-3-662-57264-1; 978-3-662-57265-8.

13.12.2018 17:00
Franciszek Stokowacki
An Approximate Restatement of the Four-Color Theorem

Four color theorem was proven in 1976 with extensive computer help. Since then there is interest in finding a simpler proof that uses no computer computation. I will present relation between Four Color Theorem and edge 3-coloring of planar, cubic graphs without bridges, and a new result proving that the existence of approximate coloring (with the fourth color used ‘rarely’) is enough to imply Four Color Theorem.

Atish Das Sarma, Amita S. Gajewar, Richard Lipton, Danupon Nanongkai. An approximate restatement of the four-color theorem. Journal of Graph Algorithms and Applications 17(5), pages 567–573, 2013.

13.12.2018 16:15
Vladyslav Hlembotskyi
EERTREE: An Efficient Data Structure for Processing Palindromes in Strings

A palindrome is a string which reads the same forward as backward, such as `Ada` or `lol`. We will present a data structure which stores information about all the different palindromic substrings of a given string and prove some basic facts about the data structure. We will show that it is useful and discuss some problems which can be solved with it.

Mikhail Rubinchik, Arseny M. Shur. EERTREE: An Efficient Data Structure for Processing Palindromes in Strings. arXiv, pages 1-21, 2015.

06.12.2018 16:00
Jakub Nowak
Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies

Consensus is one of the most important goals to be achieved when many distributed computers share the same task and resources. There are two main families of algorithms solving this problem. Traditional consensus protocols require O(n2) communication, while blockchains rely on proof-of-work. In this talk we will introduce a new family of leaderless Byzantine fault tolerance protocols, built on a metastable mechanism. These protocols provide a strong probabilistic safety and are both quiescent and green. We will analyze some of their properties and guarantees. Finally we will see results of porting Bitcoin transactions to the introduced family of protocols.

Team Rocket. Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies. 2018.

29.11.2018 16:00
Jan Derbisz
Choosability of Planar Graphs

Colorability and choosability of planar graphs have been heavily studied in the past. In 1994 Thomassen proved that every planar graph is 5-choosable using concise induction. Recently Grytczuk and Zhu used similar ideas to prove that for every planar graph G we can find a matching M in it such that G-M is 4-choosable with the help of Combinatorial Nullstellensatz theorem.

22.11.2018 16:00
Krzysztof Maziarz
A refinement of choosability of graphs

Between the well-known concepts of k-colorability and k-choosability (also know as k-list colorability) lies a whole spectrum of more refined notions. This allows for seeing k-colorability and k-choosability under one unified framework. Exploring this, one immediately discovers interesting problems - for example, possible strengthenings of the four color theorem. We will take a look at these notions, prove some of their properties, and leave many conjectures and open problems.

08.11.2018 16:15
Marcin Muszalski
On the queue-number of graphs with bounded tree-width

In this talk I will present upper bound for a queue-number of graphs with bounded tree-width obtained by Veit Wiechert. The new upper bound, 2k - 1, improves upon double exponential upper bounds due to Dujmović et al. and Giacomo et al. Additionally I will show his construction of k-trees that have queue-number at least k + 1. The construction solves a problem of Rengarajan and Veni Madhavan, namely, that the maximal queue-number of 2-trees is equal to 3.

Veit Wiechert. On the queue-number of graphs with bounded tree-width. Electronic Journal of Combinatorics, 24(1):1-14, 2017.

Marcin Muszalski. Queue-number of graphs with bounded tree-width - Veit Wiechert. slides. 2018.

25.10.2018 16:15
Bartłomiej Bosek
A new variant of the game of cops and robber

We consider the following metric version of the Cops and Robbers game. Let G be a simple graph and let k≥1 be a fixed integer. In the first round, Cop picks a subset of k vertices B={v1,v2,...,vk} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector Du(B)=(d1,2,...,dk) whose components di=dG(u,vi), i=1,2,...,k, are the distances from u to the vertices of B. In the second round, Robber may stay at the vertex u or move to any neighbouring vertex which is kept in a secret. Then Cop picks another k vertices and asks as before for the corresponding distances to the vertex occupied by Robber. And so on in every next round. The game stops when Cop determines exactly the current position of Robber. In that case, she is the winner. Otherwise, Robber is the winner (that is if Cop is not able to localise him in any finite number of rounds). Let ζ(G) denote the least integer k for which Cop has a winning strategy. Notice that this parameter is well defined since the inequality ζ(G)≤|V(G)| holds obviously. The aim of the talk is to present results concerning 2-trees, outerplanar graphs and planar graphs. This is a joint work with Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, and Małgorzata Śleszyńska-Nowak.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Centroidal localization game. arXiv, pages 1-15, 2017.

Bartłomiej Bosek, Przemysław Gordinowicz, Jarosław Grytczuk, Nicolas Nisse, Joanna Sokół, Małgorzata Śleszyńska-Nowak. Localization game on geometric and planar graphs. arXiv, pages 1-15, 2017.

18.10.2018 16:15
Bartłomiej Bosek
Local Dimension is Unbounded for Planar Posets

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.

11.10.2018 16:15
Bartłomiej Bosek
A Tight Bound for Shortest Augmenting Paths on Trees

The shortest augmenting path technique is one of the fundamental ideas used in maximum matching and maximum flow algorithms. Since being introduced by Edmonds and Karp in 1972, it has been widely applied in many different settings. Surprisingly, despite this extensive usage, it is still not well understood even in the simplest case: online bipartite matching problem on trees. In this problem a bipartite tree T=(WB, E) is being revealed online, i.e., in each round one vertex from B with its incident edges arrives. It was conjectured by Chaudhuri et. al. that the total length of all shortest augmenting paths found is O(n log n). In this paper we prove a tight O(n log n) upper bound for the total length of shortest augmenting paths for trees improving over O(n log² n) bound. This is a joint work with Dariusz Leniowski, Piotr Sankowski, and Anna Zych-Pawlewicz.

Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz. A Tight Bound for Shortest Augmenting Paths on Trees. arXiv, pages 1-22, 2017.

04.10.2018 16:15
Bartłomiej Bosek
Some open problems
14.06.2018 16:15
Mateusz Twaróg, Patryk Urbański, Łukasz Majcher
Progress in the Arachne Project
07.06.2018 17:15
Krzysztof Maziarz
The chromatic number of the plane is at least 5​

The Hadwiger-Nelson problem asks for the minimum number of colors required to color the plane, in such a way, that any two points at distance exactly one are assigned different colors. Albeit its simple definition, no significant progress on the question was made for nearly a century. In the discussed paper, Aubrey D. N. J. de Grey has shown a set of points in the plane, such that 5 colors are necessary to color it properly, thus improving a long-standing lower bound of 4 colors. Interestingly, the smallest such set discovered so far has 1581 vertices.

The chromatic number of the plane is at least 5, Aubrey D.N.J. de Grey
07.06.2018 16:15
Szymon Łukasz
Dynamic F-free Coloring of Graphs

An F-free coloring is a coloring of a graph such that each color induces an F-free graph. In this talk we consider dynamic F-free coloring which can be interpreted as a game of Presenter and Painter. In each move Presenter presents new vertices along with the edges between them and already known vertices. In the same move Presenter can also discolor arbitrary vertices and request Painter to color some vertices. The problem we consider can be stated as follows: For a given graph G, is there a sequence of moves for which the greedy algorithm uses at least k colors during dynamic F-free coloring of G. We will show that for some classes of graphs this problem is decidable in polynomial time (for fixed F and k) in the case where F is 2-connected or F is path of length 2.

Piotr Borowiecki, Elżbieta Sidorowicz, Dynamic F-free Coloring of Graphs, Graphs and Combinatorics 2018, Volume 34, Issue 3, pp 457-475
24.05.2018 16:15
Marcin Briański
How many ants does it take to find the food?

In this talk we will consider the ANTS (Ants Nearby Treasure Search) problem: consider n agents (ants), controlled by finite automata (or PDAs) exploring an infinite grid attempting to locate a hidden treasure. The question we want to answer is: how many agents are necessary to accomplish this task in (expected) finite time? Of course, the answer will depend on the way we model this situation. We will consider synchronous as well as asynchronous environment, agents with access to randomness as well as deterministic ones, agents controlled by PDA as well as finite automata and various combinations thereof. In most cases established bounds are tight, however in certain cases there is still ample room for improvement (which some might consider interesting).

Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, Roger Wattenhofer, How many ants does it take to find the food?, Theoretical Computer Science Volume 608, Part 3, 10 December 2015, Pages 255-267
17.05.2018 16:15
Marcin Muszalski
On the Number of Maximum Empty Boxes Amidst n Points

I will present article written by Adrian Dumitrescu and Minghui Jiang in which they revisit the following problem (along with its higher dimensional variant):
Given a set S of n points inside an axis-parallel rectangle U in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in U but contains no points of S.
They created first superlinear lower bound for the number of maximum-volume empty boxes amidst n points in R d (d ≥ 3). I would like to present it and show a prove that the number of maximum-area empty rectangles amidst n points in the plane is O(n log(n) 2^α(n) ), where α(n) is the extremely slowly growing inverse of Ackermann’s function. The previous best bound for this problem, O(n^2 ), is due to Naamad, Lee, and Hsu (1984).

Adrian Dumitrescu, Minghui Jiang, On the Number of Maximum Empty Boxes Amidst n Points, Discrete & Computational Geometry, Volume 59 (3), 742-756, 2018
10.05.2018 16:15
Jakub Szarawski
Faster approximation schemes for the two-dimensional knapsack problem

In 2008 Klaus Jansen and Roberto Solis-Oba presented a polynomial time approximation scheme (PTAS) for the square packing problem. Sandy Heydrich and Andreas Wiese base on their work and show a faster approximation (EPTAS) for the same problem. During the seminar both the common parts of the two papers (such as dividing the squares into large and small ones, dividing the rectangle into cells, frames, rows and blocks) and the new ideas (faster large squares guessing and block size guessing) will be presented.

S. Heydrich, A. Wiese, Faster approximation schemes for the two-dimensional knapsack problem, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 79-98

26.04.2018 16:15
Sylwester Klocek
Colouring of (P3∪P2)-free graphs

In a paper authors are colouring of (P3∪P2)-free graphs, a super class of 2K2 -free graphs. During lecture I am going to present three discovered upper bounds of the chromatic number of (P3∪P2) -free graphs, and sharper bounds for (P3∪P2 , diamond)-free graphs and for (2K2, diamond)-free graphs. The first part of a talk will contain an explanation of terminology and notation along with problem statements and results. In the second part, I will focus on proving each result in a sequence of claims and proofs.

Arpitha P. Bharathi, Sheshayya A. Choudum, Colouring of (P3∪P2)-free graphs, Graphs and Combinatorics, Volume 34 (1), 2018
19.04.2018 16:15
Grzegorz Jurdziński
Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density

Circle packing problem, where one asks whether a given set of circles can be fit into a unit square, is known to be NP-hard. I will show that when combined area of circles does not exceed ≈0,539, then it is possible to pack them. The given bound is tight in the meaning that for larger combined area an instance impossible to pack can be found. Proof for this theorem is constructive and gives an algorithm, called Split Packing, for finding a solution for instances satisfying the conditions. Moreover it can also serve as a constant-factor approximation algorithm for the problem of finding a smallest square which can fit given circles.

Sebastian Morr, Split Packing: An Algorithm for Packing Circles with Optimal Worst-Case Density, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 99-109

12.04.2018 16:15
Maciej Woźniak
Find Your Place: Simple Distributed Algorithms for Community Detection

Graph G = (V_1 \cup V_2, E) is regular clustered graph (with two communities) if:

  • G is connected and not bipartite,
  • |V_1| = |V_2|
  • V_1 \cap V_2 = \emptyset
  • Every vertex has degree d
  • Every vertex in V_1 has exactly b neighbours in V_2 and d-b neighbours in V_1,
  • Every vertex in V_2 has exactly b neighbours in V_1 and d-b neighbours in V_2.

We define (weak) block reconstruction of graph as two-coloring of vertices that separates V_1 and V_2 up to small "error" fraction of vertices. The reconstruction is said to be strong if separation is exact.
I will present simple distributed algorithm (protocol) that produces strong reconstruction for clustered regular graphs within O(log n) iterations. I will also show that this algorithm produces weak reconstruction for non-regular clustered graphs with two communities and discuss an approach to solving this problem for regular graphs with more than two communities.

Becchetti, L., Clementi, A., Natale, E., Pasquale, F., & Trevisan, L. (2017). Find Your Place: Simple Distributed Algorithms for Community Detection. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 940-959). Philadelphia

05.04.2018 16:15
Anna Kobak
On tree-partition-width

A tree-partition of a graph G is a proper partition of its vertex set into "bags", such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G. I will prove three theorems presented in the article, showing an upper bound on the tree-partition-width of all graphs, a lower bound for chordal graphs and a lower bound for graphs with tree-width 2.

David R.Wood, On tree-partition-width, European Journal of Combinatorics, Volume 30, Issue 5, July 2009, Pages 1245-1253

22.03.2018 16:15
Aleksandra Mędrek
The Matching Problem in General Graphs is in Quasi-NC

Authors show that the perfect matching problem in general graphs is in quasi-NC by presenting a deterministic parallel algorithm which runs in O(log^3 n) time on n^O(log^2 n) processors. The paper extends the framework of Fenner, Gurjar and Thierauf, who proved that finding perfect matching in bipartite graphs is in quasi-NC. I describe their algorithm in the first part of my presentation. In the second part I talk about difficulties that arise in the general case and how they are approached.

Ola Svensson, Jakub Tarnawski, The Matching Problem in General Graphs is in Quasi-NC, FOCS 2017

15.03.2018 16:15
Dawid Pyczek
Punctured combinatorial Nullstellensätze

This article presents an extension of Alon’s Nullstellensatz to functions of multiple zeros at the common zeros of some polynomials. It also includes an introduction to the polynomials of multiple variables and other useful definitions. There are also many corollaries useful for polynomial problem-solving. Possibly the presentation will include some geometrical usage of Nullstellensatze extensions.

Simeon Ball, Oriol Serra, Punctured combinatorial Nullstellensätze, Combinatorica, September 2009, Volume 29, Issue 5, pp 511–522

08.03.2018 16:15
Jakub Rówiński
On the 1/3–2/3 Conjecture

Let (P,≤) be a finite poset. For distinct elements x, y ∈ P , we define P(x ≺ y) to be the proportion of linear extensions of P in which x comes before y. For 0 ≤ α ≤ 1, we say (x,y) is an α-balanced pair 2 if α ≤ P(x ≺ y) ≤ 1 − α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. Proof of above conjecture as well as stronger condition of having a 1/2-balanced pair for certain families of posets will be shown. These include lattices such as the Boolean, set partition, subspace lattices and variety of diagrams.

Emily J. Olson, Bruce E. Sagan, On the 1/3--2/3 Conjecture, Order, 2018

01.03.2018 16:15
Bartłomiej Bosek
Some open problems
25.01.2018 16:15
Bartłomiej Bosek
News about Combinatorial Nullstellensatz

I will present some new theorems, proofs and open problems concerning about Combinatorial Nullstellensatz and related problems.

Terence Tao. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. arXiv:1310.6482 (2014), pp 1-44.

18.01.2018 16:15
Jarek Duda
Some nonstandard approaches to hard computational problems

I will talk about nonstandard approaches to some problems for which there is not known polynomial time classical algorithm. I will start with briefly explaining mechanism used in Shor algorithm and the problem with global optimization formulations used in adiabatic quantum computers. Then show some perspectives on the subset-sum NP complete problem, like geometric, integration and divergence formulations. Then show how Grassmann variables would be useful for the Hamilton cycle problem. Finally discuss the difficulty of the graph isomorphism problem on the most problematic cases: strongly regular graphs, and algebraic perspective on this problem.

Jarek Duda. Some unusualapproaches to hard computational problems. slides.

  • 1
  • 2