## Optymalizacja Kombinatoryczna

### dr hab. Bartłomiej Bosekczwartek 16:15-17:45, jedynie online

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.

# Poprzednie referaty

 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. (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. (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. (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. (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 D2 + 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. (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. (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. (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. (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. (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. (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. (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. (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. (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. (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. (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. (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. (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. (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/3 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. (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.
 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 17:00 Paweł Mader Probability makes counting (sometimes) easy 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.
 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 Turá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.
 15.11.2018 16:00 Jakub Łabaj Contracting a Planar Graph Efficiently Jacob Holm, Giuseppe F. Italiano, Adam Karczmarz, Jakub Lacki, Eva Rotenberg, Piotr Sankowski: Contracting a Planar Graph Efficiently. CoRR abs/1706.10228 (2017) Jakub Łabaj. Contracting a Planar Graph Efficiently. slides. 2018.
 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=(WB, 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.
 11.01.2018 16:15 Maciej Woźniak, Dawid Pyczek Online Vertex Cover and Matching: Beating the Greedy Algorithm Authors study the online vertex cover problem and online matching problem in bipartite graphs and in general graphs. For the case of bipartite graphs their result is optimal water-filling algorithm with competitive ratio 1/(1-1/e) . The main contribution of this paper is a 1.901-competitive algorithm for vertex cover in general graphs which beats the well-known trivial 2-competitive algorithm. The next major result is a primal-dual analysis of given algorithm that implies the dual result of a 0.526-competitive algorithm for online fractional matching in general graphs. On the hardness side authors show that no randomized online algorithm can achieve a competitive ratio better than 1.753 and 0.625 for the online fractional vertex cover problem and the online fractional matching problem respectively, even for bipartite graphs. Yajun Wang, Sam Chiu-wai Wong. Online Vertex Cover and Matching: Beating the Greedy Algorithm. arXiv (2013), pp 1-21.
 04.01.2018 16:15 Grzegorz Bukowiec Feedback Vertex Set Problem A Feedback Vertex Set (FVS) is a subset of vertices in a graph such that its removal results in an acyclic graph. The problem of finding a minimal FVS is one of the classic NP-complete problems. However, in some practical cases, we can assume that its size is fairly small. This motivated an intensive study of the parametrized version of this problem, which asks either for FVS of a size at most k or an information that it doesn't exist. There are several deterministic algorithms known which solve this in time O*(ck), the best one for now being O*(3.592k).
 21.12.2017 16:15 Paweł Kubiak, Jakub Rówiński Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms On bipartite graphs, problem of constrained minimum vertex cover (MIN-CVCB) is defined as follows: given a bipartite graph G = (V, E) with vertex bipartition V = U ∪ L and two integers ku and kl, decide whether there is a minimum vertex cover in G with at most ku vertices in U and at most kl vertices in L. We show how it is related to practical problems. We prove that (MIN-CVCB) is NP-complete. However, there are many parametrized algorithms running in decent time. We describe one of them, whereby linear kernelization method it achieves O(1.26ku+kl +(ku +kl)|G|) time. Jianer Chen, Iyad A.Kanj. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms. Journal of Computer and System Sciences. Vol. 67, Iss. 4, (2003), pp. 833-847.
 14.12.2017 17:00 Jakub Nowak Dulmage–Mendelsohn Decomposition In a graph G, let B be the set of vertices covered by every maximum matching in G, and let D = V(G) − B. Further partition B by letting A be the subset consisting of vertices with at least one neighbor outside B, and let C = B − A. The Gallai-Edmonds Decomposition of G is the partition of V(G) into the three sets A, C, D. The Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is an extension of the Gallai-Edmonds decomposition. L. Lovász, M. D. Plummer. Matching theory. North-Holland Mathematics Studies, 121. Annals of Discrete Mathematics, 29. North-Holland Publishing Co., Amsterdam. 1986. pp. xxvii+544. ISBN: 0-444-87916-1. Chapter 4.3.
 14.12.2017 16:15 Lev Deliatynskyi A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem This paper studies the maximum matching in a graph. It shows a short proof of a Berge-Tutte formula and the Gallai-Endmonds structure theorem. Authors use Hall's theorem to prove it. Deficiency in a graph (def(S), S⊆V(G)) is o(G-S) - |S|, where o(G-S) is the number of odd components in G-S. Berge-Tutte formula says that the maximum size of a matching in an n-vertex graph G is 1/2(n-def(G)), where def(G) = maxS⊆V(G)def(S). Gallai Edmonds has a sharper formulation which gives considerable information about the structure of maximum size matchings. Douglas B.West. A short proof of the Berge–Tutte Formula and the Gallai–Edmonds Structure Theorem. European Journal of Combinatorics. Vol. 32, Iss. 5, (2011), pp. 674-676.
 07.12.2017 16:15 Jan Derbisz, Franciszek Stokowacki On Low Rank-Width Colorings We say that a class C of graphs admits low rank-width colorings if there exist functions N : N → N and Q: N → N such that for all p ∈ N, every graph G ∈ C can be vertex colored with at most N(p) colors such that the union of any i ≤ p color classes induces a subgraph of rank-width at most Q(i). It turns out that for every graph class C of bounded expansion and every positive integer r, the class {Gr : G ∈ C} of r-th powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. Additionally, every graph class admitting low rank-width colorings is χ-bounded. O-joung Kwon, Michał Pilipczuk, and Sebastian Siebertz. On Low Rank-Width Colorings. arXiv (2017), pp. 1-17.
 30.11.2017 16:15 Krzysztof Maziarz, Tomasz Wesołowski The Generalised Colouring Numbers on Classes of Bounded Expansion We introduce two classes of graphs - graphs with bounded expansion and nowhere dense graphs. These notions are a common generalization of proper minor closed classes, classes of graphs with bounded degree, locally planar graphs, to name just a few classes which are studied extensively in combinatorial and computer science contexts. We also present generalized colouring numbers admr(G), colr(G), and wcolr(G) and show important applications in the theory of above-mentioned classes of graphs. Finally, we prove that every graph excluding a fixed topological minor admits a universal order, that is, one order witnessing that the colouring numbers are small for every value of r, and show that it can be efficiently computed. Stephan Kreutzer, Michał Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. The Generalised Colouring Numbers on Classes of Bounded Expansion. In Proceedings of 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Vol. 58 (2016), pp. 85:1-85:13.
 23.11.2017 16:15 Gabriel Jakóbczak Majority coloring games A vertex coloring of graph G satisfies the majority rule, if for each vertex v at most half of its neighbors receive the same color as v. A coloring which satisfies the majority rule is called majority coloring. We consider its game version. For given graph G and color set C two players, Alice and Bob, in alternating turns color vertices with respect to the majority rule. Alice wins when every vertex becomes colored, while goal for Bob is to create a vertex which cannot be colored with any color belonging to the set C without breaking the majority rule. Let µg(G) denote the least number of colors belonging to C for which Alice has winning strategy in game on graph G. We show that if the color set C is finite, there exists a graph G on which Bob has winning strategy. We prove also that for graphs with col(G) = 3 parameter µg(G) is still unbounded.
 16.11.2017 16:15 Anna Kobak, Grzegorz Jurdziński The Erdős discrepancy problem - Part II Erdős discrepancy problem has waited for the solution for over 70 years until last year Terrence Tao, with a help of Polymath project, has published a paper with its solution. After having our friends given an introduction to the topic and shown the Fourier analytic reduction of the problem last week we will continue presenting the proof. It will include the proof of Elliot-type conjecture and a sketch of how to apply a generalised Borwein-Choi-Coons analysis for the final steps of the main proof. Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2 (2016), pp. 1-20.
 09.11.2017 16:15 Aleksandra Mędrek, Marcin Muszalski The Erdős discrepancy problem - Part I Erdős discrepancy problem had remained unresolved for more than 80 years. In 2015 Erdős theorem has been proofed by Terrence Tao. We present first part of his proof where he uses a Fourier-analytic reduction obtained as part of the Polymath5 project which reduces the problem to the case when f is replaced by a (stochastic) completely multiplicative function g. Terence Tao. The Erdős discrepancy problem. Discrete Analysis. Vol. 2, (2016), pp. 1-20.
 26.10.2017 16:15 Wojciech Kruk Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching We give a simple proof that the RANKING algorithm of Karp, Vazirani and Vazirani is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. Nikhil R. Devanur, Kamal Jain, Robert D. Kleinberg. Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 101-107, SIAM, Philadelphia, PA, 2012.
 19.10.2017 16:15 Sylwester Klocek On-line bipartite matching made simple We examine the classic on-line bipartite matching problem studied by Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. Algorithm attempts to match online new vertices with edges. Such a decision, once made, is irrevocable. The objective is to maximize the size of the resulting matching. We will see a sketch of simple proof of their result that the Ranking algorithm for this problem achieves a competitive ratio of 1 − 1/e. B.E. Birnbaum, C. Mathieu. On-line bipartite matching made simple. SIGACT News 39 (1), 80-87, 2008.
 12.10.2017 16:15 Zygmunt Łenyk Handwritten graph diagrams recognition Graph visualisation problem is well known and there are many solutions to it. The reverse process - graph recognition - has been disregarded so far. Such solution has wide applications - from scientific to didactic. This paper focuses on hand-written graphs. Objects do not necessarily have regular shapes and there might be a lot of noise. Using computer vision techniques, we recognize first vertices and then edges. The result of the algorithm is a list of edges and a generated graph visualisation.
 05.10.2017 16:15 Szymon Borak On some problems in planar graphs We give insight into competitive reachability for outerplanar graphs and also for other classes of graphs with bounded degree. Competitive reachability is a game where two players orient the edges of undirected graph G alternately until all edges of G have been oriented. One player wants to minimize the number of ordered pairs of distinct vertices (x, y) with a directed path from x to y. And the second want to maximize it. Furthermore we focus on harmonious coloring conjecture for outerplanar graphs and further attempts in this area. A harmonious coloring of a graph G is a proper vertex coloring of G in which every pair of colors appears on adjacent vertices at most once. The harmonious chromatic number, denoted by h(G), is the minimum number of colors in a harmonious coloring. Analogically we define  harmonious edge coloring in which every pair of colors appears on incident edges at most once. The minimal number of color we denote by h'(G). The conjecture states that h(G)<=h'(G). Finally we tackle the hamiltonian cycles in grid graphs. Grid graph are finite vertex induced subsets of infinite lattice, composed from unit-side squares, equilateral triangles or equilateral hexagons. Decide whether the grid graph has hamiltonian cycle is NP-hard in general.
 01.06.2017 16:15 Wojciech Kruk, Piotr Kruk Ulam Sequences and Ulam Sets The Ulam sequence is given by a1=1,a2=2, and then, for n≥3, the element an is defined as the smallest integer that can be written as the sum of two distinct earlier elements in a unique way. This gives the sequence 1,2,3,4,6,8,11,13,16,…, which has a mysterious quasi-periodic behavior that is not understood. Ulam's definition naturally extends to higher dimensions: for a set of initial vectors {v1,…,vk}⊂ℝn, we define a sequence by repeatedly adding the smallest elements that can be uniquely written as the sum of two distinct vectors already in the set. The resulting sets have very rich structure that turns out to be universal for many commuting binary operations. We give examples of different types of behavior, prove several universality results, and describe new unexplained phenomena. Noah Kravitz, Stefan Steinerberger Ulam Sequences and Ulam Sets
 25.05.2017 16:15 Sylwester Klocek, Maciej Woźniak On the complexity of the chip-firing reachability problem In this paper, we study the complexity of the chip-firing reachability problem. We show that for Eulerian digraphs, the reachability problem can be decided in polynomial time, even if the digraph has multiple edges. We also show a special case when the reachability problem can be decided in polynomial time for general digraphs: if the target distribution is recurrent restricted to each strongly connected component. Both of these algorithms are strongly polynomial. As a further positive result, we show that the chip-firing reachability problem is in co-NP for general digraphs. We also show that the chip-firing halting problem is in co-NP for Eulerian digraph
 18.05.2017 16:15 Katrzyna Janocha Proper Orientations of Planar Bipartite Graphs An orientation of a graph G is proper if any two adjacent vertices have different indegrees. The proper orientation number χ (G) of a graph G is the minimum of the maximum indegree, taken over all proper orientations of G. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that χ (G) ≤ 4, when G is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.
 11.05.2017 16:15 Anna Kobak Lambda number for the direct product of some family of graphs An L(2,1) labeling for a graph G = (V,E) is a function f on V such that | f(u) - f(v)| >= 2 if u,v are adjacent and f(u), f(v) are distinct if u,v are vertices of distance two. The lambda(G) for G is the minimum span over all L(2,1) labelings of G. We will show that when m>=6 and n>=3, lambda(Pm x Cn) = 7 if and only if n is not a multiple of 7 and also provide the conditions on m and n such that lambda(Cm x Cn) <= 7.
 04.05.2017 16:15 Grzegorz Bukowiec Even factors of graphs An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. It has been shown that if a graph G has an even factor, it also has an even factor F such that |E(F)| >= 4/7 (|E(G)| + 1). 4/7 is the best possible ratio here, but we will try to strengthen this lower bound by taking the set of vertices of degree 2 into consideration.
 27.04.2017 16:15 Jakub Szarawski A greedy approach to the Turtle Tower problem In the Turtle Tower problem we are given n turtles with a mass and capacity for each of them. We are looking for the highest tower possible, regarding that capacity of every turtle in the tower cannot be exeeded by the sum of the masses of turles it carry. Presented solution is faster than commonly known dynamic one.
 20.04.2017 16:15 Helena Borak, Zygmunt Łenyk Necklaces, Convolutions, and X + Y, A new upper bound for the online square packing Necklaces, Convolutions, and X + Y The necklace alignment problem is to find the optimal rotation of the necklaces to best align the beads, when we have two necklaces given, each with n beads at arbitrary positions. Alignment is measured according to the ℓ_p norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p = 1, p even, and p = ∞ and how these problems can be reduced to convolution problems which can be solve in subquadratic time. Besides, we say how the necklace alignment problems, and their corresponding convolution problems, are also intrinsically connected to problems on X + Y matrices. A new upper bound for the online square packing In online square packing problem we try to minimise the height of squares on a plane with width 1. Squares come one by one, they can’t overlap and once set, it’s position can’t be changed. A new upper bound (ratio between algorithm result and optimal packing) is found by applying modified version of previously used First Fit Shelf algorithm.
 06.04.2017 16:15 Andrzej Głuszyński, Jakub Nowak Local Antimagic Vertex Coloring of a Graph, A short proof of Cayley's tree formula Local Antimagic Vertex Coloring of a Graph The edge labelling is called 'local antimagic', if for all vertices sum of labels for incident edges is different for every two adjacent vertices. Such sum induce a correct vertex colouring. The local antimagic chromatic number - X_la(G) - is the minimum number of colours used by any proper local antimagic labelling. In the paper authors present results on this parameter for trees, friendship, wheel and clique graphs. A short proof of Cayley's tree formula Cayley’s tree formula is a very elegant result in Graph Theory. The problem is to find the number of all possible trees on a given set of labeled vertices. For n = 2 and vertex set {v1, v2}, we have only one tree. For n = 3 and vertex set {v1, v2, v3}, we have 3 different trees. Similarly for n = 4, we have 16 trees. We give a short proof of Cayley’s tree formula for counting the number of different labeled trees on n vertices. Alok Bhushan Shukla, A short proof of Cayley's tree formula.
 23.03.2017 16:15 Aleksandra Mędrek, Marcin Muszalski Planning for Fast Connectivity Updates Understanding how a single edge deletion can affect the connectivity of a graph amounts to finding the graph bridges. But when faced with d > 1 deletions, can we establish as easily how the connectivity changes? When planning for an emergency, we want to understand the structure of our network ahead of time, and respond swiftly when an emergency actually happens. We describe a linear-space representation of graphs which enables us to determine how a batch of edge updates can impact the graph. Given a set of d edge updates, in time O(d polylg n) we can obtain the number of connected components, the size of each component, and a fast oracle for answering connectivity queries in the updated graph. The initial representation is polynomial-time constructible.
 16.03.2017 16:15 Patryk Urbański Generating Linear Extensions Fast One of the most important sets associated with a poset P is its set of linear extensions, E(P). In this paper, we present an algorithm to generate all of the linear extensions of a poset in constant amortized time; that is, in time O(e(P)), where e(P) = |E(P)|. The fastest previously known algorithm for generating the linear extensions of a poset runs in time O(n*e(P)), where n is the number of elements of the poset. Our algorithm is the first constant amortized time algorithm for generating a ``naturally defined'' class of combinatorial objects for which the corresponding counting problem is #P-complete. Furthermore, we show that linear extensions can be generated in constant amortized time where each extension differs from its predecessor by one or two adjacent transpositions. The algorithm is practical and can be modified to efficiently count linear extensions, and to compute P(x < y), for all pairs x,y, in time O(n^2 + e(P)). Gara Pruesse, Frank Ruskey. Generating Linear Extensions Fast. SIAM J. Comput. Vol. 23, No. 2 (1994), pp. 373-386.
 09.03.2017 16:15 Grzegorz Matecki Boolean dimension of posets A boolean dimension bdim(P) of a poset P=(X,<) is a smallest number k for which there is a set l1, l2, ..., lk of labelings X:->N and a boolean formula f(a1, ..., ak) such that the following is true: x < y in P iff f(a1, .., a_k) = 1 where ai =1 iff li(x) < li(x). Generally, it is simple to observe that bdim(P) <= dim(P). Also, it is known that there is a constant c such that bdim(n) <= c log(n) for any poset P of size n. The are few interesting open problems for boolean dimension: 1) Is boolean dimension of the boolean lattice of size n less that n? 2) Is there a constant c such that bdim(P) < c for any planar poset P?
 09.03.2017 16:15 Mateusz Twaróg, Łukasz Majcher Combinatorial library core Presentation and discussion on core functionalities of the c++ combinatorial library. introduction to classes representing graphs, graph traversing algorithm templates and simple GUI.
 26.01.2017 16:15 Wojciech Kruk, Maciej Woźniak A few open problems We mentioned the following open problems in graph theory and discrepancy theory: 1. Erdos discrepancy problem 2. Hoang - Reed conjecture 3. Seagull problem - a consequence of Hadwiger's conjecture
 19.01.2017 Paweł Petecki Akademia Górniczo-Hutnicza Symmetry breaking polynomial Let G be a graph, and let Γ= Aut G. A coloring c of G is symmetry-breaking if for every non-identity automorphism φ in Γ, there is some vertex v of G such that c(v)≠c(φ(v)). There has been a lot of work on the minimum number of colors in a symmetry-breaking coloring of G. We discuss here a different problem: counting the number of k-colorings that are symmetry breaking. The tool, as is frequently the case for problems such as this one, is Möbius inversion. To solve this problem we define symmetry breaking polynomial ψG. For positive integer k (number of colors), ψG(k) is the number of k-colorings that break all non-trivial symmetries of the graph G.
 22.12.2016 16:15 Łukasz Majcher, Jan Szczepaniec Convex p-partitions of bipartite graphs A set of vertices X of a graph G is convex if no shortest path between two vertices in X contains a vertex outside X. We prove that for fixed p ≥ 1, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
 15.12.2016 Anna Kobak Open problems in graph theory concerning minors. We mentioned following open problems in graph theory: Hadwiger's Conjecture Seagull Conjecture Jorgensen's Conjecture Unfriendly partitions and a few more conjectures concerning minors.
 08.12.2016 Zygmunt Łenyk Rendezvous on the line. This is one of a handful of rendezvous problems where two players must find one another in a certain structured domain. In line case, players are placed on the line with distance 2, without knowing neither on which side is their partner, nor the direction of the line. I'll concentrate on the symmetric case where players must follow a specific (but maybe mixed) strategy. The conjecture is that best expected time of meeting two players equals 4.25.
 01.12.2016 Patryk Urbański Coloring Ordinary Maps, Maps of Empires and Maps of the Moon A short review of generalized map coloring problems: Heawood's empire coloring problem in the plane - 6M colors are sufficient to color a map of empires each consisting of at most M connected regions. Earth-Moon map coloring Mathematics Magazine Vol. 66, No. 4 (Oct., 1993), pp. 211-226problem - it is known that the chromatic number of thickness-2 graphs is between 9 and 12. It is an open problem to find the exact value. Coloring Ordinary Maps, Maps of Emipres, and Maps of the Moon. Joan P. Hutchinson. Mathematics Magazine. Vol. 66, No. 4 (Oct., 1993), pp. 211-226.
 01.12.2016 Mateusz Twaróg Second Neighborhood via First Neighborhood in Digraphs Second Neighborhood via First Neighborhood in Digraphs. Guantao Chen, Jian Shen, Raphael Yuster. Annals of Combinatorics. June 2003, Volume 7, Issue 1, pp 15–20.
 24.11.2016 Wojciech Łopata Several open problems from game theory, graph theory and combinatorics. I'll briefly introduce the audience to two unrelated areas: book embedding and mechanism design, and walk through some open problems in those areas. Wikipedia: Book embedding Wikipedia: Mechanism design
 17.11.2016 Paweł Kubiak Succinct Data Structures
 10.11.2016 Grzegorz Bukowiec On more variants of the Majority Problem
 03.11.2016 Gabriel Jakóbczak Proper orientations of some types of graphs Let G be a simple graph. We say that orientation of graph G is proper if for every pair of adjacent veritces u and v their indegrees are different. It was proved by Mieczysław Borowiecki, Jarosław Grytczuk and Monika Pilśniak that for every simple graph exists its proper orientation. Now we can define the proper orientation number of graph G as the minimum of the maximum indegree, taken over all proper orientations of G. We show that for some classes of bipartite graphs their proper orientation number is less than or equal to 6. We also show that this parameter is at most 4 for graphs which are trees and proof of that fact leads to a polynomial-time algorithm of finding proper orientation of such graphs. Fiachra Knox, Sebastián González Hermosillo de la Maza, Bojan Mohar, and Cláudia Linhares Sales.  Proper Orientations of Planar Bipartite Graphs.  pages 2-6, sep 2016.
 27.10.2016 Magdalena Gargas The geometry of nesting problems: A tutorial
 20.10.2016 Helena Borak Exact algorithms for the two-dimensional strip packing problem with and without rotations We propose exact algorithms for the two-dimensional strip packing problem (2SP) with and without 90 degree rotations. We first focus on the perfect packing problem (PP), which is a special case of 2SP, wherein all given rectangles are required to be packed without wasted space, and design branch-and-bound algorithms introducing several branching rules and bounding operations. A combination of these rules yields an algorithm that is especially efficient for feasible instances of PP. We then propose several methods of applying the PP algorithms to 2SP. Our algorithms succeed in efficiently solving benchmark instances of PP with up to 500 rectangles and those of 2SP with up to 200 rectangles. They are often faster than existing exact algorithms specially tailored for problems without rotations.
 13.10.2016 Krzysztof Barański Level-Oriented Two-Dimensional Packing Algorithms The paper includes an overview of several algorithms, their complexities and approximation ratios solving two-dimensional strip packing problem: 1) First-Fit Decreasing Height (FFDH) - time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof] 2) Next-Fit Decreasing Height (NFDH) - time complexity: O(nlgn), approximation ratio: <= 17/10 OPT(I) + 1 [with proof] 3) Best-Fit Decreasing Height (BFDH), Bottom-Left (BL), Steinberg's algorithm, Split-Fit (SF)
 06.10.2016 Bartłomiej Bosek A new variant of the game of cops and robber The talk presents a joint work of Jarosław Grytczuk, Joanna Sokół, Małgorzata Śleszyńska-Nowak. 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,d2,…,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 localize 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.
 27.01.2016 Michał Dyrek The Linear Arboricity of Graphs A linear forest is a forest in which each connected component is a path. The linear arboricity la(G) of a graph G is the minimum number of linear forests whose union is the set of all edges of G. The linear arboricity conjecture asserts that for every simple graph G with maximum degree D, la(G) <= [(D+1)/2].   Although this conjecture received a considerable amount of attention, it has been proven only for D <= 6, D = 8, D = 10 and the best known general upper bound for la(G) is la(G) <= [3D/5] for even D and la(G) <= [(3D + 2)/5] for odd A. Here we prove that for every e > 0 there is a D_0 so that for every G with maximum degree D > D_0, la(G) <= (1/2 + e) * D. To do this, we first prove the conjecture for every G with an even maximum degree D and with girth g > 50*D.   N. Alon, The Linear Arboricity of Graphs
 20.01.2016 Pola Kyzioł Matching in regular and almost regular graphs I present an O(n^2*log n)-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2*log n) time if the difference between the maximum degree and the minimum degree is less than r.
 13.01.2016 Piotr Bejda Perfect matchings in O(n log n) time in regular bipartite graphs In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bi-partite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m*sqrt(n)). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost and Schirra). In a recent line of work by Goel, Kapralov and Khanna the O(m) time algorithm was improved first to O'(min(m, n^2.5/d)) and then to O'(min(m,n^2/d)). It was also shown that the latter algorithm is optimal up to polylogarithmic factors among all algorithms that use non-adaptive uniform sampling to reduce the size of the graph as a first step. In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, an d is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for any deterministic algorithm. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log2 n) time, with O(m) pre-processing time; this gives a simple O(m + mn log2 n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix. A. Goel and M. Kapralov and S. Khanna, Perfect matchings in O n log n time in regular bipartite graphs
 16.12.2015 Krzysztof Kleiner Online Dual Edge Coloring of Paths and Trees Extending the results presented on the preceding seminar, we study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. For paths, we consider k=2, and for trees, we consider any k>=2. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit. L. M. Favrholdt, J. W. Mikkelsen, Online Dual Edge Coloring of Paths and Trees
 09.12.2015 Mateusz Twaróg On-Line Edge-Coloring with a Fixed Number of Colors We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and 1/2 , and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than 4/7 -competitive. If the graphs are all k-colorable, any fair algorithm is at least 1/2 -competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large. M. Favrholdt, N. Nielsen, On-Line Edge-Coloring with a Fixed Number of Colors, Algorithimca 35 (2), 176-191, 2003
 02.12.2015 Helena Borak Linear Extensions of N-free Orders We consider the number of linear extensions of an N-free order P. We give upper and lower bounds on this number in terms of parameters of the corresponding arc diagram. We propose a dynamic programming algorithm to calculate the number. The algorithm is polynomial if a new parameter called activity is bounded by a constant. The activity can be bounded in terms of parameters of the arc diagram. Stefan Felsner , Thibault Manneville, Linear Extensions of N-free Orders, Order 32 (2), 147-155, 2015
 18.11.2015 Leszek Jakub Kania Improved Bounds for Online Preemptive Matching When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight.  The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms. L. Epstein, A. Levin, D. Segev, O. Weimann, Online Preemptive Matching, arXiv 2012
 04.11.2015 Jakub Cieśla Computing Tree-Depth Faster Than 2^n A connected graph has tree-depth at most k if it is a subgraph of the clusure of a rooted tree whose height is at most k. The autors give an algorithm which for a given n-vertex graph G, in time O(1.9602^n) computes the tree-depth of G. The algorithm is based on combinatorial results revealing the structure of minimal rooted trees whose closures contain G. F. V. Fomin, A. C. Giannopoulou, M. Pilipczuk, Computing Tree-Depth Faster Than 2^n, Algorithmica 73 (1), 202-216, 2015
 28.10.2015 Karol Banyś Fast Algorithm for Partial Covers in Words In this article autors introduce a new notion of α-partial cover, which can be viewed as a relaxed variant of cover, that is, a factor covering at least α positions in w. They develop a data structure of O(n) size (where n=|w|) that can be constructed in O(nlogn) time which they apply to compute all shortest α-partial covers for a given α. They also employ it for an O(nlogn)-time algorithm computing a shortest α-partial cover for each α=1,2,…,n. Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski , Wojciech Rytter, Tomasz Waleń, Fast Algorithm for Partial Covers in Words, Algorithmica 73 (1), 217-233, 2015
 21.10.2015 Paweł Kubiak Lower bounds for dynamic algorithms In my presentation I will discus some elementary dynamic problems (Single source reachability and Dynamic diameter) and then I will present interesting reduction from this problems to Orthogonal Vectors Problems. These reductions imply that if it would be possible to solve SSR in O(m^(1-ε)) or do 1.3 approximation of DD in O(m^(2-ε)) then SETH will be refuted. Amir Abboud, Popular Conjectures and Dynamic Problems, 2015
 14.10.2015 Katarzyna Janocha Conditional hardness and equivalences for graph problems Some graph problems (such as such as APSP, negative triangle, distance product or radius) do not have any known solutions better then the naive ones. We show subquadraic and subcubic reductions between them, proving that in case of finding a faster algorithm for any of the problems would be equivalent of reducing the complexity of each of them. We separate algorithms for sparse and dense graphs and focus on basic methods for both classes.
 07.10.2015 Zygmunt Łenyk Hardness for Easy Problems (overview) Introduction into a young branch of algorithmics. We discuss why we are stuck during developing fast algorithms to some well-known problems. Problems in P and suitable reductions form equivalence classes of problems, inside which improving asymptotic time of any of them would automatically improve the rest. At the bottom of these classes lie problems such as: 3SUM, all-pairs-shortest-paths, orthogonal vectors. Their complexities are guarded by strong conjectures which, if proven wrong, would revoke widely believed conjectures such as SETH.   Amir Abboud, Arturs Backurs, Piotr Indyk and Virginia V. Williams, Hardness for easy problems - An introduction, 2015
 20.01.2015 Maciej Poleski An online version of Rota's basis conjecture Rota's basis conjecture states that in any square array of vectors whose rows are bases of a fixed vector space the vectors can be rearranged within their rows in such a way that afterwards not only the rows are bases, but also the columns. We discuss an online version of this conjecture, in which the permutation used for rearranging the vectors in a given row must be determined without knowledge of the vectors further down the array. The paper contains surprises both for those who believe this online basis conjecture at first glance, and for those who disbelieve it.   References:Guus P. Bollen, Jan Draisma, An online version of Rota's basis conjecture, Journal of Algebraic Combinatorics, October 2014
 13.01.2015 Helena Borak Variants of Hat Guessing Games Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat they are wearing by looking at the colors of the hats worn by some of the other players. In this paper we consider several variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worst-case analysis of deterministic hat-guessing problems with a finite number of players.   References:S.Butler, M.T.Hajiaghayi, R.D.Kleinberg, T.Leighton, Hat Guessing Games
 16.12.2014 Marcin Dziaduś Five-list-coloring of planar graphs Let G be a plane graph with outer cycle C, let u,v be vertices of C and let (L(x):x in V(G)) be a family of sets such that |L(u)|=|L(v)|=2, L(x) has at least three elements for every vertex x of C \ {u,v} and L(x) has at least five elements for every vertex x of G \ V(C). We prove a conjecture of Hutchinson that G has a proper coloring f such that f(x) belongs to L(x) for every vertex x of G.   References:Luke Postle, Robin Thomas, Five-list-coloring graphs on surfaces I. Two lists of size two in planar graphs, Journal of Combinatorial Theory, Series B
 09.12.2014 Karol Banyś Online Load Balancing and Correlated Randomness This paper looks at online load balancing, in a setting where each job can only be served by a subset of the servers. The subsets are revealed only on arrival, and can be arbitrary. The cost of an allocation is the sum of cost for each server, which in turn is a convex increasing function of the number of jobs allocated to it. There are no departures.   References:S. Moharir, S. Sanghavi. Online Load Balancing and Correlated Randomness. 50th Annual Allerton Conference, 2012U. Vazirani V. Vazirani A. Mehta, A. Saberi. Adwords and generalized on-line matching. Proceedings of FOCS, 2005
 02.12.2014 Andrzej Dorobisz Random Walks that Find Perfect Objects and the Lov´asz Local Lemma We give an algorithmic local lemma by establishing a sufficient condition for the uniform random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's entropic method proof of the Lov´asz Local Lemma (LLL) for satisfiability and completely bypasses the Probabilistic Method formulation of the LLL. In particular, our method works when the underlying state space is entirely unstructured. Similarly to Moser's argument, the key point is that algorithmic progress is measured in terms of entropy rather than energy (number of violated constraints) so that termination can be established even under the proliferation of states in which every step of the algorithm (random walk) increases the total number of violated constraints.   References:Dimitris Achlioptas, Fotis Iliopoulos, Random Walks that Find Perfect Objects and the Lovasz Local Lemma, FOCS 2014
 25.11.2014 18.11.2014,Jakub Brzeski Markov Chains and Random Walks on Graphs References:D. Aldous and J. A. Fill, Reversible Markov Chains and Random Walks on Graphs, monograph, 2014.L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 353–397, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
 04.11.2014 Jakub Cieśla Finding All Maximally-Matchable Edges in a Bipartite Graph We consider the problem of finding all maximally-matchable edges in a bipartite graph G = (V, E), i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time O(n + m) (where n = |V| and m = |E|). Hence, the time complexity of finding all maximally-matchable edges reduces to that of finding a single maximum matching.   References:T. Tassa, Finding all maximally-matchable edges in a bipartite graph, Theoret. Comput. Sci. 423 (2012), 50–58.
 28.10.2014 Marcin Ziemiński Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated random walk on a modified graph to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. We also show that randomization is crucial for obtaining o(nd) time algorithms by establishing an (nd) lower bound for any deterministic algorithm.   References:A. Goel, M. Kapralov, S. Khanna, Perfect matchings in O(n log n) time in regular bipartite graphs, Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC'10), 39–46, ACM, New Yo
 21.10.2014 Patryk Mikos Maximum Matching in Regular and Almost Regular Graphs An O(n^2*log(n))-time algorithm that finds a maximum matching in a regular graph with n vertices. More generally, the algorithm runs in O(r*n^2 log n) time if the difference between the maximum degree and the minimum degree is less than r. This running time is faster than applying the fastest known general matching algorithm that runs in O(√nm)-time for graphs with m edges, whenever m = ω(rn1.5 log n).   References:R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66 (2013), no. 1, 87–92.
 14.10.2014 07.10.2014,Bartłomiej Bosek Incremental algorithm on bipartite graphs The talk presents the jont work of Bartłomiej Bosek, Darek Leniowski, Piotr Sankowski, and Anna Zych. We investigated the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i.e., after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation.   References:Bartłomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych. Online bipartite matching in offline time. In Proceedings of the 55th Symposium on Foundations of Computer Science, FOCS14, pp. 384-393, 2014.