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

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

(the seminar will only be online)

...

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

The notion of treewidth and tree decompositions plays a central role in the study of graphs with forbidden minors. Besides structural characterizations, the property of having boundedtreewidth, or a tree decomposision with certain "nice" properties, can be used algorithmically. However, until very recently, there were very few results that allowed to analyze the treewidth of graphs that exclude certain induced subgraphs. Indeed, a large clique has large treewidth, but is H-free for any graph H which is not a clique. It turns out that some intresting relations between the two worlds can be found if we additionally put some restrictions on vertex degrees - either just by bounding the maximum degree, or, in some cases, by bounding the degeneracy.

During the talk we will discuss some results of this flavor. In particular, we will show that

• graphs of bounded degeneracy that exclude all cycles of length at least t have bounded treewidth;
• graphs of bounded degree that exclude a fixed subdivision of the claw admit a certain type of an "*induced* grid/wall theorem": they either contain the line graph of a big subdivided wall as an *induced subgraph*, or have bounded treewidth.

Based on the joint work with Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and with Abrishami, Chudnovsky, and Dibek.

The visibility graph of a polygon P is formed by the pairs of vertices u and v of P such that the segment uv is disjoint from the exterior of P. We show that the class of polygon visibility graphs is χ-bounded, thus answering a question by Kára, Pór, and Wood from 2005. Specifically, we prove the bound χ≤3⋅4^ω−1. We obtain the same bound for generalizations of polygon visibility graphs in which the polygon is replaced by a curve and straight-line segments are replaced by segments in a pseudo-line arrangement. The proof is carried through in the setting of ordered graphs. In particular, we show χ-boundedness of several classes of ordered graphs with excluded ordered substructures.

Joint work with James Davies, Tomasz Krawczyk, and Rose McCarty.

This is a part of Round the World Relay in Combinatorics organized by Oxford University.

Here is the full schedule: http://people.maths.ox.ac.uk/scott/relay.htm

And the zoom link for the whole event:

https://us02web.zoom.us/j/87593953555?pwd=UWl4eTVsanpEUHJDWFo3SWpNNWtxdz09

meeting id: 875 9395 3555
password: relay

Given a solution to a problem, we can try and apply a series of elementary operations to it, making sure to remain in the solution space at every step. What kind of solutions can we reach this way? How fast? This is motivated by a variety of applications, from statistical physics to real-life scenarios, including enumeration and sampling. In this talk, we will discuss various positive and negative results, in the special case of graph colouring.

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

We will overview the state-of-the-art results and techniques used in proofs of the lower bounds for constant depth circuits. We focus mostly on classes AC[0], ACC[0] and CC[0]. The most important challenges and some open problems are to be discussed.

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

In our paper [LICS'18] a generalization of Boolean circuits to arbitrary finite algebras was introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However nilpotent but not supernilpotent algebras have not been put on any side of this borderline.

This paper provides a broad class of examples, lying in this grey area, and show that, under the Exponential Time Hypothesis and Strong Exponential Size Hypothesis (saying that Boolean circuits need exponentially many modular counting gates to produce Boolean conjunctions of any arity), satisfiability over these algebras have intermediate complexity. We also sketch how these examples could be used as paradigms to fill the nilpotent versus supernilpotent gap in general.

Our examples are striking in view of the natural strong connections between circuits satisfiability and Constraint Satisfaction Problem for which the dichotomy was shown by Bulatov and Zhuk.

Joint work with Piotr Kawałek and Jacek Krzaczkowski

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

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

(the seminar will only be online)

Given an n-by-n generator matrix with entries being subsets of a fixed field we generate the set of all matrices with entries coming from the corresponding entries in the generator matrix. Such a set of matrices is strongly singular if each member is a singular matrix. In this talk I will survey natural generalizations and connections to other problems. In particular, I will describe algorithm by Geelen for  maximum rank matrix completion problem.

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

Given a graph class C, a graph G is universal for C if it "contains" all the graphs from C. As there are several notions of containment, there are several notions of universal graphs. In this talk I'll mention two versions:

• induced-universal graphs: here G contains all the graphs of C as induced subgraphs
• isometric-universal graphs: here G contains isometric copies of all the graphs from C (isometric means that the distances are preserved in the embedding)

Note that an isometric copy is an induced copy, so the second notion is stronger. These notions are closely related to the notion of labelling schemes in graphs. The goal is to assign labels to the vertices of each graph G from C such that upon reading the labels of any two vertices u and v, we know some properties of u and v in G (whether they are adjacent, or their distance, or whether u is reachable from v if G is a digraph). It turns out that minimizing the size of the labels is equivalent to constructing small universal graphs, at least in the case of induced-universal graphs. For isometric-universal graphs some additional work needs to be done.

I'll survey some recent progress in this area. In particular I'll show how to construct induced-universal graphs of almost optimal size for any hereditary class, using the regularity lemma. In particular this implies almost optimal reachabilty labelling schemes in digraphs and comparability labelling schemes in posets, and the construction of an almost optimal universal poset for the class of all n-element posets (of size 2^n/4+o(n)). I will also show how to construct isometric-universal graphs of size 3^n+o(n) for the class of all n-vertex graphs, answering a question of Peter Winkler.

Based on joint work with Marthe Bonamy, Cyril Gavoille, Carla Groenland, and Alex Scott.

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

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

(the seminar will only be online)

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is.

We will discuss quasirandom properties of other combinatorial structures, tournaments, permutations and Latin squares in particular, and present several recent results obtained using analytic tools of the theory of combinatorial limits.

The talk is based on results obtained with different groups of collaborators, including Timothy F. N. Chan, Jacob W. Cooper, Robert Hancock, Adam Kabela, Ander Lamaison, Taísa Martins, Roberto Parente, Samuel Mohr, Jonathan A. Noel, Yanitsa Pehova, Oleg Pikhurko, Maryam Sharifzadeh, Fiona Skerman and Jan Volec.

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

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

(the seminar will only be online)

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under

(i) inserting an element, and

(ii) deleting an element of an array.

In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/ϵ)^O(1/ϵ))-approximation of LIS under both operations with worst-case update time ~O(n^ϵ), for any constant ϵ>0. We exponentially improve on their result by designing an algorithm that maintains a (1+ϵ)-approximation of LIS under both operations with worst-case update time ~O(ϵ⁻⁵). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification.

While this essentially settles the complexity of the approximate version of the problem, the exact version seems more elusive. The only known sublinear solution was given very recently by Kociumaka and Seddighin [STOC 2021] and takes ~O(n^2/3) time per update. We show polynomial conditional lower bounds for two natural extensions of this problem: weighted LIS and LIS in any subarray.

Joint work with Wojciech Janczewski

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

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

(the seminar will only be online)

In 2015, Felsner, Trotter, and Wiechert showed that posets with outerplanar cover graphs have bounded dimension. We generalise this result to posets with k-outerplanar cover graphs. Namely, we show that posets with k-outerplanar cover graph have dimension O(k³). As a consequence, we show that every poset with a planar cover graph and height h has dimension O(h³). This improves the previously best known bound of O(h⁶) by Kozik, Micek and Trotter.

Joint work with Maximilian Gorsky

https://arxiv.org/abs/2103.15920

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

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

(the seminar will only be online)

We present a progress on local computation algorithms for two coloring of k-uniform hypergraphs. We focus on instances that (for a parameter α) satisfy strengthened assumption of Local Lemma of the form 2^1-αk(Δ+1)e<1, where Δ is the bound on the maximum edge degree of the hypergraph. We discuss how previous works on the subject can be used to obtain an algorithm that works in polylogarithmic time per query for α up to about 0.139. Then, we present a procedure that, within similar bounds on running time, solves wider range of instances by allowing α to be at most about 0.227.

Joint work with Jakub Kozik

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

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

(the seminar will only be online)

Graph classes excluding a path or a subdivided claw as an induced subgraph are so far mysterious: on one hand, beside some corner cases, they do not seem to have any good structural description, but on the other hand, a number of combinatorial problems - including Maximum Independent Set (MIS) - lack an NP-hardness proof in these graph classes, indicating a possible hidden structure that can be used algorithmically. Furthermore, graphs excluding a fixed path as an induced subgraph were one of the earliest examples of a chi-bounded graph class, with an elegant proof technique dubbed the Gyarfas' path argument. In the recent years the progress accelerated, leading to, among other results, (a) a quasi-polynomial-time algorithm for MIS in graphs excluding a fixed path as an induced subgraph, (b) a QPTAS for MIS in graphs excluding a subdivided claw as an induced subgraph, (c) the proof of the Erdos-Hajnal property in graph classes excluding a fixed forest and its complement. In the talk, I will survey these results, showing the role of the Gyarfas' path argument in most (all?) of them, and outline research directions for the future.

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

(the seminar will only be online)

In this talk we survey results for pseudocircle arrangements. Along the way we present several open problems. Among others we plan to touch the following topics:

 * The taxonomy of classes of pseudocircle arrangements.
 * The facial structure with emphasis on triangles and digons.
 * Circularizability.
 * Coloring problems for pseudocircle arrangements.

The talk includes work of Grünbaum, Snoeyink, Pinchasi, Scheucher, myself, and others.

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

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

(the seminar will only be online)

We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t √ log t). This is the first algorithm to achieve an f(t)-approximation for some function f.

Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth Ω(k^c) has treewidth at least k or contains a subdivision of a complete binary tree of height k.

Our main technical algorithm takes a graph G and some (not necessarily optimal) tree decomposition of G of width t' in the input, and it computes in polynomial time an integer h, a certificate that G has pathwidth at least h, and a path decomposition of G of width at most (t'+1)h+1. The certificate is closely related to (and implies) the existence of a subdivision of a complete binary tree of height h. The approximation algorithm for pathwidth is then obtained by combining this algorithm with the approximation algorithm of Feige, Hajiaghayi, and Lee (STOC'05) for treewidth.

Joint work with Carla Groenland, Gwenaël Joret, and Wojciech Nadara.

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

In 1977, Gerd Wegner proved that the square of cubic planar graphs is 8-colorable. He conjectured that his bound can be improved - the chromatic number of G² 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 χ(G²) ≤ 9D-19, for planar graphs with D ≥ 5. Agnarsson and Halldorson showed that for every planar graph G with maximum degree D ≥ 749, χ(G²) ≤ [9D / 5] + 2. Van den Heuvel and McGuinness (2003) showed that χ(G²) ≤ 2D + 25, Bordin (2002) proved that χ(G²) ≤ [9D / 5] + 1, if D ≥ 47, and Molloy and Salavatipour (2005) proved χ(G²) ≤ [5D / 3] + 78, moreover, χ(G²) ≤ [5D / 3] + 25 if D ≥ 241. Moreover, conjecture is confirmed in the case of outerplanar graphs and graphs without K₄ minor.

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

(the seminar will only be online)

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

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

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

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

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

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

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

(the seminar will only be online)

Let P be a set of n points in R². 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 ²/₃ n points of P must also contain q. It is a well-known fact that a centerpoint always exists and the constant ²/₃ 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)

The aim of this pearl is to solve the following well-known problem that appears in many puzzle books, for example Levitin & Levitin (2011) and Bellos (2016), usually for the particular case n=12.

There are n coins, all identical in appearance, one of which may be fake. The fake coin, if it exists, is either lighter or heavier than the fair coins, but it is not known which, nor by how much. Given is a balance with two pans but no weights. Equal number of coins can be placed on each pan and weighed. There are three possible outcomes: the left-hand pan may be lighter than the right-hand pan, or of equal weight, or heavier. Design a recipe for determining the minimum number of weighings guaranteed to determine the fake coin, if it exists, and whether it is lighter or heavier than the others.

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)

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

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

(the seminar will only be online)

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.

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.

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.

The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory and algorithmics. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs, a positive real ε and a positive integer d, in any n-vertex graph G in the class, there are disjoint vertex subsets A and B with |A|=Ω(n) and |B|=Ω(n^1-ε) such that in the d-th power of G, either there is no edge between A and B, or there are all possible edges between A and B.

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.

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.

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.

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.

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.

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.

The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(n^ω) time algorithms, for ω<2.373. On the other hand, the (min,+)-product, which is at the heart of APSP, is widely conjectured to require cubic time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems, e.g. the (min,max)-product, the min-witness product, APSP in directed unweighted graphs. The best runtimes for these "intermediate" problems are all O(n^(3+ω)/2). A similar phenomenon occurs for convolution problems.

Can one improve upon the running times for these intermediate problems? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way?

We make progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and min-witness product can be reduced to both the (min,max)-product and a variant of the monochromatic triangle problem. We also show that a natural convolution variant of monochromatic triangle is equivalent to the famous 3SUM problem. As this variant is in O(n^3/2) time and 3SUM is in O(n²) time, our result gives the first fine-grained equivalence between natural problems of different running times.

Joint work with Andrea Lincoln and Virginia Vassilevska Williams.

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.

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.

Gry parzystości to gry pomiędzy dwoma graczami (zwyczajowo Even oraz Odd) na grafie skierowanym G = (V, E). Gracze przesuwają między wierzchołkami wirtualny token, tworząc ścieżkę. Wierzchołki grafu są etykietowane liczbami naturalnymi i każdy z nich jest przypisany do jednego gracza, który decyduje w jakim kierunku zostanie wykonany ruch z tego wierzchołka. Celem każdego z graczy jest wybranie takiej strategii, że przy nieskończonej grze (ścieżce), najwyższa nieskończenie wiele razy powtarzająca się etykieta będzie odpowiednio parzysta bądź nieparzysta.

Problem gry parzystości jest deterministyczny, to znaczy dla każdego wierzchołka jeden z graczy posiada strategię wygrywającą. Rekurencyjny algorytm Zielonki rozwiązuje grę parzystości w czasie wykładniczym. Istnieje jednak algorytm działający w czasie quasi-wielomianowym, czyli 2^{O((log(n))^c)} dla pewnego, ustalonego c.

W trakcie prezentacji omówiony zostanie schemat nowej wersji algorytmu, przeprowadzona analiza jego złożoności oraz przedstawiony dowód poprawności zwracanego przez niego wyniku.

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on n vertices with an O(n⁴) time delay between the output of two consecutive graphs. We improve their algorithm and achieve O(n³ log n) time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all n up to 15 (previous best was 12).

In the design of complex systems, model-checking and satisfiability arise as two prominent decision problems. While
model-checking requires the designed system to be provided in advance, satisfiability allows to check if such a system even exists. With very few exceptions, the second problem turns out to be harder than the first one from a complexity-theoretic standpoint. In this paper, we investigate the connection between the two problems for a non-trivial fragment of Strategy Logic (SL, for short). SL extends LTL with first-order quantifications over strategies, thus allowing to explicitly reason about the strategic abilities of agents in a multi-agent system. Satisfiability for the full logic is known to be highly undecidable, while model-checking is non-elementary.

The SL fragment we consider is obtained by preventing strategic quantifications within the scope of temporal operators. The resulting logic is quite powerful, still allowing to express important game-theoretic properties of multi-agent systems, such as existence of Nash and immune equilibria, as well as to formalize the rational synthesis problem. We show that satisfiability for such a fragment is PSPACE-COMPLETE, while its model-checking complexity is 2EXPTIME-HARD. The result is obtained by means of an elegant encoding of the problem into the satisfiability of conjunctive-binding first-order logic, a recently discovered decidable fragment of first-order logic.

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.

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.

Problem Izomorfizmu Poddrzew zadaje pytanie, czy dane drzewo zawarte jest w innym danym drzewie. Ten problem o zasadniczym znaczeniu dla algorytmiki jest badany już od lat 60. ubiegłego wieku. Podkwadratowe algorytmy znane są dla niektórych wariantów, np. drzew uporządkowanych, ale nie w ogólnym przypadku.

Poprzez redukcję z problemu Wektorów Ortogonalnych pokażemy, że prawdziwie podkwadratowy algorytm dla Izomorfizmu Poddrzew przeczy SETH. Dodatkowo pokażemy, że to samo ograniczenie dolne utrzymuje się również w przypadku ukorzenionych drzew o logarytmicznej wysokości. W opozycji do niego zaprezentujemy również podkwadratowy algorytm randomizowany dla drzew o stałym stopniu i logarytmicznej wysokości.

Redukcja korzysta z nowych "gadżetów drzewowych", które prawdopodobnie przydadzą się w przyszłości w wyznaczaniu ograniczeń dolnych opartych na SETH dla problemów na drzewach. Algorytmy opierają się na znanych wynikach o złożoności randomizowanych drzew decyzyjnych.

The density D(G) of a graph G is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of G. For a class F of graphs, the value D(F) is the supremum of densities of graphs in F.

A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1,...,k. A function from the vertex set of one k-edge-colored graph to another is a homomorphism if the endpoints of any edge are mapped to two different vertices connected by an edge of the same color. Given a class F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to H. Such graphs are known to exist exactly for classes F of graphs with acyclic chromatic number bounded by a constant. The minimum number of vertices in a k-uniform graph for a class F is known to be Ω(k^D(F)) and O(k^d), where d is the ceiling of D(F) (result obtained in 2015 with Gutowski), and has been conjectured to be ϴ(k^D(F)).

In this talk, I will present a construction of a k-universal graph on O(k^d) vertices for any rational bound d on the density D(F). It follows that if D(F) is rational, the minimum number of vertices in a k-universal graph for F is indeed ϴ(k^D(F)).

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

We prove that every intersection graph of axis-parallel rectangles in the plane with clique number ω has chromatic number O(ω log ω), which is the first improvement of the original O(ω²) bound of Asplund and Grünbaum from 1960. As a consequence, we obtain a polynomial-time O(log log n)-approximation algorithm for Maximum Weight Independent Set in axis-parallel rectangles, improving the previous best approximation ratio of O(log n/log log n).

Joint work with Parinya Chalermsook.

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.

A classic result of Erdős and Pósa (1965) states that for every graph G and every integer k, either G has k vertex-disjoint cycles, or G has a set of O(k log k) vertices meeting all cycles. The usual way of proving this theorem is through the so-called frame technique. In this talk I will describe another equally simple way of proving the theorem, using a ball packing argument. Then I will describe some applications of this method, including to the variant where only cycles of length at least l are considered.

Joint work with Henning Bruhn, Wouter Cames van Batenburg, and Arthur Ulmer.

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.

We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as Geometric k-Cut, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n⁴ log³ n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2−4/3k)-approximation algorithm.

Joint work with Panos Giannopoulos, Maarten Löffler, and Günter Rote. Presented at ICALP 2019.

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

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

Tematem pracy jest problem znalezienia automatu skończonego rozróżniającego dwa łańcuchy o możliwie najmniejszej liczbie stanów. Autorzy pokazują, że dla łańcuchów ograniczonych przez długość n istnieje automat akceptujący tylko jeden z łańcuchów o O(n^2/5 * log^3/5n) stanach, co dla przypadku, gdy łańcuchy na wejściu są równej długości jest najlepszym znanym ograniczeniem.

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

The Turán number ex(n, H) is the maximum number of edges that an H-free graph on n vertices can have. This quantity is well studied for graphs with chromatic number greater than 2, but the problem of determining it for all bipartite graphs remains open. A generalization of the Turán number, namely, the maximum possible number of copies of a graph T in an H-free graph on n vertices, denoted by ex(n, T, H), is recently attracting a lot of attention. In particular, the problem of determining ex(n, C₅, C₃), posed by Erdős in 1984, was completely solved in the last few years with the use of the flag algebras method.

In this talk, we will show an elementary proof that ex(n, C_k, C_k−2) = (n/k)^k + o(n^k) for any odd k > 5.

Joint work with Andrzej Grzesik.

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.

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.

Let 𝒞 and 𝒟 be hereditary graph classes. Consider the following problem: given a graph G ∈ 𝒟, find a largest, in terms of the number of vertices, induced subgraph of G that belongs to 𝒞. We prove that it is solvable in 2^o(n) time, where n is the number of vertices of G, if the following conditions are satisfied:

• the graphs in 𝒞 are sparse, i.e., they have linearly many edges in terms of the number of vertices;
• the graphs in 𝒟 admit balanced separators of size governed by their density, e.g., O(Δ) or O(√m), where Δ and m denote the maximum degree and the number of edges, respectively; and
• the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph.

This leads, for example, to the following corollaries for specific classes 𝒞 and 𝒟:

• a largest induced forest in a P_t-free graph can be found in 2^Õ(n2/3) time, for every fixed t; and
• a largest induced planar graph in a string graph can be found in 2^Õ(n3/4) time.

Joint work with Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, and Erik Jan van Leeuwen.

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.

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.

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.

Listing and counting triangles in sparse graphs are well-studied problems. For a graph with m edges, Björklund et al. gave an O(m^1.408) algorithm which can list up to m triangles. The exact exponent depends on the exponent omega in matrix multiplication, and becomes 4/3 if omega=2. Pătraşcu proved that an algorithm faster than O(m^4/3) would imply a sub-quadratic algorithm for 3-SUM, which is considered unlikely.

In our work we consider a variant of triangle problem asking to determine for every edge the number of triangles which contains that edge. We prove that this problem is no easier than listing up to m triangles, although it still admits an algorithm of the same O(m^1.408) complexity. We also propose a natural class of range query problems, including for example the following problem: given a family of ranges in an array, compute the number of inversions in each of them. We prove that all the problems in this class are equivalent, under one-to-polylog reductions, to counting triangles for each edge. In particular the time complexities of these problems are the same up to polylogarithmic factors.

This is joint work of Lech Duraj, Krzysztof Kleiner, Adam Polak and Virginia Vassilevska-Williams.

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.

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.

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.

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.

Graph colorings and online algorithms on graphs constitute the key fragments of the algorithmic graph theory. Specifically, the subject of this study will be a presentation of the results concerning

• different variants of coloring of graphs and partially ordered sets,
• online coloring of partially ordered sets,
• incremental matchings of bipartite graphs.

The first part of the talk will concern different aspects of the coloring problem as well as different evidential techniques. The presented results concern majority choosability of digraphs, harmonious coloring of hypergraphs and semi-uni conjecture of product of two posets. The next part of presentation will concern online chain partitioning of posets. There will be presented a full characterization of the class of posets, for which the number of colors (chains) used by first-fit is a function of width, i.e. best offline solution. This part will also present two different subexponential online algorithm for the online chain partitioning problem. The last part will concern the incremental matching problem in bipartite graphs. There will be presented an incremental algorithm that maintains the maximum size matching in total time equal the running time of one of the fastest offline maximum matching algorithm that was given by Hopcroft and Karp. Moreover, I will show an analysis of the shortest augmenting path algorithm.

This is joint work with Marcin Anholcer, Jarosław Grytczuk, Sebastian Czerwiński, Paweł Rzążewski, Stefan Felsner, Kolja Knauer, Grzegorz Matecki, Tomasz Krawczyk, H. A. Kierstead, Matthew Smith, Dariusz Leniowski, Piotr Sankowski, Anna Zych-Pawlewicz.

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.

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.

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 Ω(2^n/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.1812ⁿ) on the graphs in this family. This scaling is currently the best known.

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.

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.

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.

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

Praca przedstawia randomizowany algorytm obliczający maksymalny przepływ. Dla sieci przepływowej o n wierzchołkach i m krawędziach, czas wykonania jest O(nm + n²(log n)²) z prawdpodobieństwem co najmniej 1 - 2^-sqrt(nm). Algorytm jest zawsze poprawny i w najgorszym przypadku działa w czasie O(nm log n). Czynnik randomizujący składa się tylko z zastosowania losowych permutacji do list sąsiedztwa wierzchołków na początku algorytmu.

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.

A widely investigated subject in combinatorial geometry, originating from Erdős, is the following: given a point set P of cardinality n in the plane, how can we describe the distribution of the determined distances, e.g., determine the maximum number of unit distances, the maximum number of minimum/maximum distances, the minimum number of distinct distances? This has been generalized in many directions by taking point sets in a certain (not necessarily Euclidean) metric space and studying the distribution of certain configurations — and a whole theory emerged.

In this talk I propose the following problem variant: consider planar line arrangements of n lines, and determine the maximum number of unit/maximum/minimum area determined by these lines. We prove that the order of magnitude for the maximum occurrence of unit area lies between n² and n^2+1/4. This result is strongly connected to both additive combinatorial results and Szemerédi-Trotter type results. Next we show a tight bound for the maximum number of minimum area triangles. Finally we discuss a graph theoretic approach for the maximum number of maximum area triangles and present a recursive lower bound.

Joint work with Gábor Damásdi, Leo Martínez-Sandoval and Dániel T. Nagy.

Jan Derbisz, Promotor: dr hab. Tomasz Krawczyk
Wykorzystanie matroidów w algorytmach.

Pola Kyzioł, Promotor: dr hab. Tomasz Krawczyk
Cut & Count technique and its application to NP.-compelete graph problems that require connectivity

Krzysztof Maziarz, Promotor: prof. dr hab. Jacek Tabor
Evolutionary-Neural Hybrid Agents for Architecture Search

Jakub Nowak, Promotor: prof. dr hab. Jacek Tabor
Application of functional image representation

Grzegorz Jurdziński, Promotor: dr Piotr Micek
Głębokie sieci neuronowe w rozpoznawaniu mowy
 

We study the amount of consistency (measured by relational width) needed to solve the CSP parametrized by first-order expansions of countably infinite homogeneous graphs, that are, the structures first-order-definable in a homogeneous graph containing the edge relation E, the relation N that holds between different vertices not connected by an edge and the equality. We study our problem for structures that additionally have bounded strict width, i.e., establishing local consistency of an instances of the CSP not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. It is known that with every countably infinite homogeneous graph G the finite unique minimal set S of finite graphs is associated such that some finite H is an induced substructure of G if and only if there is no H' in S such that H' embeds into H.

Our main result is that structures under consideration have relational width exactly (2,L) where L is the maximal size of a forbidden subgraph in S, but not smaller than 3. It implies, in particular, that the CSP parametrized by such structures may be solved in time O(n^m) where n is the number of variables and m is the maximum of L and the arities of relations in the signature, while strict width l ensures time O(n^l+1). Furthermore, since L may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures, in which case, if finite, relational width is always at most (2,3). 

Finally, we show that certain maximally tractable constraint languages with a first-order definition in a countably infinite homogeneous graph whose CSPs are already known to be solvable in polynomial time by other algorithms may be also solved by establishing consistency. Thus, providing an alternative algorithm for already studied problems.

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.

The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated longest common subsequence (LCS). For LCIS, as well as for LCS, there is an O(n²) algorithm and a SETH-based quadratic lower bound. Both the algorithm and the proof of the bound are, however, quite different for LCIS.

For LCS, there is also the Masek-Paterson O(n²/log n) algorithm. Its technique (the 'four Russians trick') does not seem to work for LCIS in any obvious way, so a natural question arises: does any sub-quadratic algorithm exist for Longest Common Increasing Subsequence problem?

We answer this question positively, presenting a O(n²/log^an) algorithm for some a>0. The algorithm is not based on memorizing small inputs (often used for logarithmic speedups, including LCS), but rather utilizes a new technique, bounding the number of significant symbol matches between the two sequences.

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.

Prezentowana przez nas praca przedstawia nowe obserwacje, które pozwoliły autorom dowieść poprawności dwóch znanych algorytmów (Hu-Tuckera i Garsi-Wachs) na konstrukcję optymalnych drzew utrzymujących porządek leksykograficzny. Omówimy uogólnioną wersję algorytmu Garsi-Wachs wraz z przejrzystym i łatwym do zilustrowania dowodem, który pomaga również w zrozumieniu podejścia Hu-Tuckera.

Let G be a graph with maximum degree d. We show a randomized procedure that colors the edges of G so that:

• every two adjacent edges get two different color;
• edges of every cycle get at least three different colors.

Such a coloring is called an acylic edge-coloring of G. The minimum number of colors in an acyclic edge coloring of G is called the acylic index of G. It is conjectured that acylic index of G is at most d+2. We are able to prove that our coloring procedure succeeds for roughly 3.97d colors (improving on a previous result that used 4d colors).

This is joint work with Jakub Kozik and Xuding Zhu.

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.

One of the important topics in the information theory of non-sequential random data structures such as trees, sets, and graphs is the question of entropy: how many bits on average are needed to describe the structure. Here we consider dynamic graphs generated by a duplication model in which a new vertex selects an existing vertex and copies all of its neighbors. We provide asymptotic formulas for entopies for both labeled and unlabeled versions of such graphs and construct compression algorithms matching these bounds up to two bits. Moreover, as a side result, we were able to derive asymptotic expansions of expected value of f(X) for functions of polynomial growth, when X has beta-binomial distribution - which in turn allowed to obtain e.g. asymptotic formula the entropy for a Dirichlet-multinomial distribution.

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.

Dostając zbiór n dodatnich liczb całkowitych, problem Modular Subset Sum polega na sprawdzeniu czy istnieje podzbiór, który sumuje się do zadanego t modulo dana liczba całkowita m. Jest to naturalne uogólnienie problemu Subset Sum (m=+∞), który silnie łączy się z addytywną kombinatoryką i kryptografią.

Niedawno zostały opracowane efektywne algorytmy dla przypadku niemodularnego, działające w czasie blisko-liniowym pseudo-wielomianowym. Jednak dla przypadku modularnego najlepszy znany algorytm (Koiliaris'a i Xu) działa w czasie Õ(m^5/4).

W tej pracy prezentujemy algorytm działający w czasie Õ(m), który dopasowuje się do warunkowego ograniczenia dolnego opartego na SETH. W przeciwieństwie do większości poprzednich wyników związanych z problemem Subset Sum, nasz algorytm nie korzysta z FFT. Natomiast, jest zdolny zasymulować "podręcznikowe" programowanie dynamiczne znacznie szybciej, używając pomysłów ze Szkicowania Liniowego. Jest to jedna z pierwszych aplikacji technik bazujących na szkicowaniu, by osiągnąć szybki algorytm dla problemów kombinatorycznych w modelu offline.

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.

Gunrock is a CUDA library for graph-processing designed specifically for the GPU. It uses a high-level, bulk-synchronous, data-centric abstraction focused on operations on a vertex or edge frontier. Gunrock achieves a balance between performance and expressiveness by coupling high performance GPU computing primitives and optimization strategies with a high-level programming model that allows programmers to quickly develop new graph primitives with small code size and minimal GPU programming knowledge.

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.

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.

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(n²) 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.

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.

Computational approach to the problem of solving equation, began with the question of David Hilbert. He asked, if there exists an algorithm, that decides wheather given Diophantine equation has a solution or not.  Yuri Matiyasevich proved this problem to be undecidable.  An analogy for decidability in finite realms is tractability. During the talk, we introduce the notion of PolSat problem for finite algebras and discuss the results for the wide class of algebraic structures.

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.

Odległość edycyjna to jeden ze sposobów zmierzenia jak bardzo dwa ciągi znaków są do siebie podobne. Polega on na zliczeniu minimalnej liczby operacji wstawienia, usunięcia lub zmienienia znaku na inny, wymaganej aby przekształcić jedno słowo w drugie. W tej pracy autorzy skupili się na problemie złożoności obliczeniowej aproksymowania odległości edycyjnej pomiędzy parą słów.

Problem wyznaczenia dokładnej odległości edycyjnej może być rozwiązany za pomocą klasycznego algorytmu dynamicznego działającego w kwadratowym czasie. W 2010 roku Andoni, Krauthgamer i Onak przedstawili działający w czasie prawie liniowym, algorytm aproksymujący odległość edycyjną z polilogarytmicznym czynnikiem aproksymacji. W 2014 Backurs i Indyk pokazali, że dokładny algorytm działający w czasie O(n^(2-δ))implikowałby szybki algorytm dla SAT i fałszywość silnej hipotezy o czasie wykładniczym (SETH). Ponadto, ostatnio w 2017, Abboud i Backurs pokazali, że istnienie algorytmu aproksymującego odległość edycyjną w czasie prawdziwie podkwadratowym z czynnikiem aproksymacji 1 + o(1) implikowałoby fałszywość paru hipotez dotyczących złożoności obwodów boolowskich (circuit complexity). To poddaje w wątpliwość aproksymowalność odległości edycyjnej z dokładnością do czynnika stałego w czasie prawdziwie podkwadratowym.

W tej pracy autorzy jednak odpowiedzieli twierdząco na to pytanie, przedstawiając bardzo ciekawy algorytm aproksymujący odległość edycyjną, z stałym czynnikiem aproksymacji i dowodząc, że jego czas działania jest ograniczony od góry przez Õ(n^(2−2/7)).

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.

We show that every 3-connected graph which contains many disjoint 2xn-grid minors, contains a 2x(n+1)-grid-minor. We use this result in a qualitative structure theorem for graphs without large 2xn grids.

This is a result from a joint paper with Tony Huynh, Gwenaël Joret, Piotr Micek and Paul Wollan

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.

We give very short and simple proofs of the following statements: Given a 2-colorable 4-uniform hypergraph on n vertices,

1) It is NP-hard to color it with log^delta n colors for some delta>0.

2) It is quasi-NP-hard to color it with O({log^{1-o(1)} n}) colors.

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={v₁,v₂,...,v_k} and then Robber picks a vertex u but keeps it in a secret. Then Cop asks Robber for a vector D_u(B)=(d₁,₂,...,d_k) whose components d_i=d_G(u,v_i), 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.

This note is about encoding Turing machines into the lambda -calculus. The encoding we show is interesting for two reasons:

1. Weakly strategy independent : the image of the encoding is a very small fragment of the lambda - calculus, that we call the deterministic lambda -calculus det. Essentially, it is the CPS (continuation-passing style) lambda -calculus restricted to weak evaluation (i.e., not under abstractions). In det every term has at most one redex, and so all weak strategies collapse into a single deterministic evaluation strategy, because there are no choices between redexes to be made. The important consequence of this property is that every weak evaluation strategy then allows to simulate Turing machines,as well as any strong strategy reducing weak head redexes (or even only weak head redexes) first.

2. Linear overhead: the simulation is very efficient, when taking the number of beta-steps as the time cost model for the deterministic lambda -calculus. The simulation in det indeed requires a number of beta-steps that is linear in the number of transitions of the encoded Turing machine, which is the best possible overhead. Therefore, not only all weak strategies simulate Turing
machines, but they all do it efficiently.

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

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

The class of unit interval graphs has at least 3 equivalent definitions:

• intersection graphs of unit-length intervals,
• intersection graphs of intervals such that no interval properly contains any other interval,
• K_1,3-free chordal graphs.

We ask whether the competitive ratio in the online unit-interval graph coloring with bandwidths depends on the chosen graph representation.

Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d \geq 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schutzenberger representation for context-free languages,
we present a new conversion from context-free languages into 2-limited automata.

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.

Based on the paper
Induced subgraphs of graphs with large chromatic number. III. Long holes
by Maria Chudnovsky, Alex Scott and Paul Seymour

a proof of a 1985 conjecture of Gyarfas that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ

will be presented.

A coarse description of a set A \subset \omega  is a set D \subset \omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputable information can be effectively recovered from all coarse descriptions of a given set A, especially when A is effectively random in some sense. We show that if A is 1-random and B is computable from every coarse description D of A, then B is K-trivial, which implies that if A is in fact weakly 2-random then B is computable. Our main tool is a kind of compactness theorem for cone-avoiding descriptions, which also allows us to prove the same result for 1- genericity in place of weak 2-randomness. In the other direction, we show that if A \leq_T \emptyset is a 1-random set, then there is a noncomputable c.e. set computable from every coarse description of A, but that not all K-trivial sets are computable from every coarse description of some 1-random set.

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.

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.

The main aim of the article is to give a simple and conceptual account for the correspondence (originally described by Bodini, Gardy, and Jacquot) between \alpha equivalence classes of closed linear lambda terms and isomorphism classes of rooted trivalent maps on compact oriented surfaces without boundary, as an instance of a more general correspondence between linear lambda terms with a context of free variables and rooted trivalent maps with a boundary of free edges. We begin by recalling a familiar diagrammatic representation for linear lambda terms, while at the same time explaining how such diagrams may be read formally as a notation for endomorphisms of a reflexive object in a symmetric monoidal closed (bi)category. From there, the “easy” direction of the correspondence is a simple forgetful operation which erases annotations on the diagram of a linear lambda term to produce a rooted trivalent map. The other direction views linear lambda terms as complete invariants of their underlying rooted trivalent maps, reconstructing the missing information through a Tutte-style topological recurrence on maps with free edges. As an application in combinatorics, we use this analysis to enumerate bridgeless rooted trivalent maps as linear lambda terms containing no closed proper subterms, and conclude by giving a natural reformulation of the Four Color Theorem as a statement about typing in lambda calculus.

We propose a new, worst-case cubic-time, generalized parsing algorithm for all context-free languages, based on computing the relations between configurations and transitions in a recursive transition network. The algorithm represents such relations using abstract data types, and for their specific (non-canonical) implementations behaves analogously to generalized LL, Left-Corner, or LR. It features a clean mathematical formulation, and can easily be implemented using only immutable data structures.

In the Simply Typed lambda calculus Statman investigates the reducibility relation between types: for types freely generated using \arrow and a single ground type 0, define A \leq B if there exists a lambda definable injection from the closed terms of type A into those of type B. Unexpectedly, the induced partial order is the (linear) well-ordering (of order type) \omega + 4.

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

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

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

The hiring problem has been recently introduced by Broder et al. in last year’s ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and decisions to hire or discard them must be taken on the fly. The goal is to maintain a good rate of hiring while improving the “average” quality of the hired staff. We provide here an alternative formulation of the hiring problem in combinatorial terms. This combinatorial model allows us the systematic use of techniques from combinatorial analysis, e. g., generating functions, to study the problem.

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.

Solving equations  is one of the oldest and well known mathematical problems which for centuries was the driving force of research in algebra. Let us only mention Galois theory, Gaussian elimination or Diophantine Equations. If we consider  equations over the ring of integers it is the famous 10th Hilbert Problem on Diophantine Equations, which has been shown to be undecidable. In finite realms such a problem is  obviously decidable in nondeterministic polynomial time.

The talk is intended to present the latest achievements in searching structural algebraic conditions a finite algebra A has to satisfy in order to have a polynomial time algorithm that decides if an equation of polynomials over A has a solution. We will also present the results on  the polynomial  equivalence problem in which we ask whether two polynomials over  a finite algebra describe the same function.

This is joint work with Paweł M. Idziak and Piotr Kawałek..

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

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.

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

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

For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of {1, …, n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k + 1, k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k ≥ 3, the odd graph K(2k + 1, k) has a Hamilton cycle. Its construction is based on constructing a spanning tree in a suitably defined hypergraph on Dyck words. As a byproduct, it provides an alternative proof of the so-called middle levels theorem, originally proved by Mütze in 2014.

Joint work with Torsten Mütze and Jerri Nummenpalo (arXiv:1711.01636).

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

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

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

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, compressed sensing, 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, geometric perspective on this problem, and some new approach to rotation invariants for this purpose.

Slides: https://tinyurl.com/y74nx2t6

We prove the conjecture of Seymour (1993) that for every apex-forest H1 and outerplanar graph H2 there is an integer p such that every 2-connected graph of pathwidth at least p contains H1 or H2 as a minor.

This is joint work with Tony Huynh, Gwenaël Joret, and David R.Wood.

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.

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.

In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one by one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized O(log²n) replacements per insertion, where n is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for any replacement strategy, almost matching the Ω(log n) lower bound.

The previous best known strategy achieved amortized O(√n) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014].

Based on the paper:

Online bipartite matching with amortized O(log²n) replacements

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.

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^*(c^k), the best one for now being O^*(3.592^k).

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 k_u and k_l, decide whether there is a minimum vertex cover in G with at most k_u vertices in U and at most k_l 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.26^k_u+k_l +(k_u +k_l)|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.

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.

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) = max_S⊆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.

In convex integer programming, various procedures have been developed to strengthen convex relaxations of sets of integer points.  On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies.  On the other hand, various methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization.

We propose a new efficient method that interpolates between these two approaches.  Our procedure strengthens any convex set containing a set of 0/1-points S, by exploiting certain additional information about S.  Namely, the required extra information will be in the form of a Boolean formula defining the target set S.  The strengthened relaxation is obtained by ''feeding'' the convex set into the formula defining S.
As one result, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems.

This is joint work with Samuel Fiorini and Stefan Weltge.

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 {G^r : 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.

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 adm_r(G), col_r(G), and wcol_r(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.

• Conditional lower bounds for k-mismatch pattern matching
• Faster algorithms for subset sum
• Complexity of 3-coloring for graphs with excluded k-paths

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.

On-line interval coloring was studied by Kierstead and Trotter. They presented an algorithm with competitive ratio 3,and showed a construction which implies that there is no algorithm with competitive ratio strictly less than 3. However, their construction in asymptotic case requires intervals with possibly unbounded length.

We are interested in a variant of the on-line interval coloring problem in which all intervals have lenght between 1 and L. We show that as L tends to infinity the asymptotic competitive ratio tends to 5/2. Moreover we show that for L=1+epsi there is no algorithm with competitive ratio less than 5/3 and for L=2+epsi there is no algotihm with competitive ratio less than 7/4.

Finally, we want to know how the asymptotic competitive ratio changes as a function of L.

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.

The purpose of my talk is to discuss several problems related to coloring and construction of appropriate representation for partially ordered sets (also posets) and graph classes derived from posets. In these problems, we will assume the following two scenarios:

in the first scenario, an algorithm receives a poset element one after another. For each new element added, the algorithm takes an irrevocable decision (assigns a color or extends a current representation) just after this element is presented (algorithms that work under such conditions are called on-line).

in the second scenario, an algorithm receives an incomparability graph of some poset and a representation of some parts of this graph, and its task is to check whether this partial representation can be extended to a representation of the whole graph that is appropriate for the considered class of graphs.

In the context of on-line algorithms, we focus our attention on two problems: partitioning posets into chains, which is a special case of on-line coloring of incomparability graphs, and embedding posets into d-dimentional space R^d.

In the context of extending partial representations problems, we are interested in graph classes whose representations introduce a natural order on vertices of these graphs.

We focus our attention on:

• function graphs that are intersection graphs of continuous functions [0,1] → R,

• permutation graphs that are intersection graphs of linear functions [0,1] → R,

• trapezoid graphs that are intersection graphs of trapezoids spanned between two fixed parallel lines containing the bases of these trapezoids.

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.

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.

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.

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.

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.

Short presentantion of the book Logic of Provability by George Boolos.

The recent breakthrough paper by Calude et al. has given the first algorithm for solving parity games in quasipolynomial time, where previously the best algorithms were mildly subexponential. We devise an alternative quasi-polynomial time algorithm based on progress measures, which allows us to reduce the space required from quasi-polynomial to nearly linear. Our key technical tools are a novel concept of ordered tree coding, and a succinct tree coding result that we prove using bounded adaptive multi-counters, both of which are interesting in their own right.

Based on the paper:
Succinct progress measures for solving parity games,
by Marcin Jurdziński and Ranko Lazić

This study arises from the following question: what is the proportion of tautologies of the given length n among the number of all FO relational sentences of length n? We investigate the simplest language with a fixed signature σ = {r}, where r is a binary relation symbol. The model with four logic symbols and an universal quantifier lead us to discover an unexpected result - the fraction of valid sentences is always greater than a fixed constant and therefore the density, if exists, is positive. The main theorem is derived from the analysis of structural properties of FO formulae, which themselves bear strict resemblance to structural properties of λ-terms.

The talk is based on the paper by Ben Adida with the same title [1]. In addition, we recall ElGamal encryption scheme and zero-knwoledge proofs.

Voting with cryptographic auditing, sometimes called open-audit voting, has remained, for the most part, a theoretical endeavor. In spite of dozens of fascinating protocols and recent ground-breaking advances in the field, there exist only a handful of specialized implementations that few people have experienced directly. As a result, the benefits of cryptographically audited elections have remained elusive.

We present Helios, the first web-based, open-audit voting system. Helios is publicly accessible today: anyone can create and run an election, and any willing observer can audit the entire process. Helios is ideal for on-line software communities, local clubs, student government, and other environments where trustworthy, secret-ballot elections are required but coercion is not a serious concern. With Helios, we hope to expose many to the power of open-audit elections.

References

[1] Ben Adida, Helios: Web-based Open-Audit Voting, Proceedings of the 17th Conference on Security Symposium, 2008, pp. 335-348

• Noah Kravitz, Stefan Steinerberger Ulam Sequences and Ulam Sets

We propose a Ramsey theory for binary trees and prove that for every r-coloring of "strong copies" of a small binary tree in a huge complete binary tree T, we can find a strong copy of a large complete binary tree in T with all small copies monochromatic. As an application, we construct a family of graphs which have tree-chromatic number at most 2 while the path-chromatic number is bounded. This construction resolves a problem posed by Seymour.

Joint work with Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros, Heather Smith, Libby Taylor, and Tom Trotter.

Motivated by a connection to vertex-distinguishing colorings, we initiate the study of a new graph covering parameters: The k-strong induced arboricity. For a graph G and a positive integer k, a k-strong induced forest F in G is an induced forest in which every component has at least k edges. An edge in G is called k-valid if it is contained in at least one k-strong induced forest. The k-strong induced arboricity f_k(G) is the smallest number m such that all k-valid edges of G can be covered with m k-strong induced forests in G.

We demonstrate that the k-strong induced arboricity is not monotone, neither in k, nor under taking subgraphs or even induced subgraphs. In particular we construct 2-degenerate graphs G with f_k(G)≤ 3 and f_k+1(G) arbitrarily large. Focusing on the supremum f_k(C) of f_k(G) among all graphs G from a given graph class C, we prove that f_k(G) is finite whenever C is of bounded expansion. For the class C of planar graphs we prove that f_k(C) is 8,9 or 10. Moreover we give necessary and sufficient conditions for f₁(C) to be finite in terms of r-shallow minors of graphs in C, a notion recently introduced by Nešetřil and Ossona de Mendez.

This is based on joint work with Maria Axenovich, Philip Dörr, Daniel Gonçalves, and Jonathan Rollin.

We briefly introduce the definition of fully homomorphic encryption and describe the two main problems on which are based latest FHE schemes: The LWE/Ring-LWE and AGCD problems. We discuss their advantages and the relations between them. We present the definition of bootstrapping and investigate the FHE scheme based on the AGCD problem as published in [1].

References

[1] J. H. Cheon, D. Stehlé, Fully Homomorphic Encryption over the Integers Revisited, EUROCRYPT'10 Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques, pp. 24--43.

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties:

1) A induces a subgraph of G of treewidth O(√k log k), and

2) for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2^{O(√k log2 k)}n^O(1))⁻¹, where n is the number of vertices of G.

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound 2^{O(√k log2 k)}n^O(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k-Path, Weighted k-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. We also provide a similar statement for graph classes of polynomial growth.

In the talk I will first focus on the background and motivation, and then highlight the main ideas of the proof by sketching the proof for the case of graph classes of polynomial growth. Based on joint work with Fedor Fomin, Daniel Lokshtanov, Dániel Marx, Michał Pilipczuk, and Saket Saurabh: http://arxiv.org/abs/1604.05999 and http://arxiv.org/abs/1610.07778.

The talk is divided into two parts. In the first part we briefly introduce Fully Homomorphic Encryption and a presentation of a classic example described in [1]. In the second part, we bring up a subject of partially homomorphic encrytpion schemes over finite fields, presented in [2].

References:

[1] C. Gentry, Computing Arbitrary Functions of Encrypted Data, 2008 (pdf)
[2] J. Liu, L. Chen and S. Mesnager, Partially homomorphic encryption schemes over finite fields, 2016 (pdf)

The Longest Common Increasing Subsequence problem is a variant of classic Longest Common Subsequence problem, which can be solved in quadratic time with a simple dynamic programming algorithm. During the talk we will show a reduction from the Orthogonal Vectors problem to the Longest Common Increasing Subsequence problem which proves that the latter cannot be solved in strongly subquadratic time unless the SETH is false.

Simple modifications of the reduction prove that the problem for k sequences cannot be solved in O(n^k-ε) time, that the same lower bounds apply to the Longest Common Weakly Increasing Subsequence, and that the assumption of SETH can be replaced with a weaker statement about satisfiability of non-deterministic branching programs.

A packing polynomial is a polynomial that maps the set N^2 of lattice points with nonnegative coordinates bijectively onto N. Cantor constructed two quadratic packing polynomials, and Fueter and Polya proved analytically that the Cantor polynomials are the only quadratic packing polynomials.
The purpose of this paper is to present a beautiful elementary proof of Vsemirnov of the Fueter-Polya theorem. It is a century-old conjecture that the Cantor polynomials are the only packing polynomials on N^2.

We show that a family of quantum authentication protocols introduced in FOCS 2002 can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this family of protocols, i.e., there exists an adversarial strategy to obtain all non-recycled bits. Previous works recycled less key and only gave partial security proofs, since they did not consider all possible distinguishers (environments) that may be used to distinguish the real setting from the ideal secure quantum channel and secret key resource.

References:

[1] Christopher Portmann, Quantum Authentication with Key Recycling (pdf)

1. Mihai Patrascu , Mikkel Thorup, Planning for Fast Connectivity Updates, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.263-271, October 21-23, 2007

Distributed cryptographic protocols such as Bitcoin and Ethereum use the block chain to synchronize a global log of events between nodes in their network. Previous research has shown that the mechanics of the block chain and block propagation are constrained: if blocks are created at a high rate compared to their propagation time in the network, many conflicting blocks are created and performance suffers greatly.
Inclusive Block Chain Protocol is a alternative structure consists of a directed acyclic graph of blocks to the chain that allows for operation at much higher rates. It is showed that with this system the advantage of highly connected miners is greatly reduced. On the negative side, attackers that attempt to maliciously reverse transactions can try to use the forgiving nature of the DAG structure to lower the costs of their attacks.

References:
[1] Lewenberg Y., Sompolinsky Y., Zohar A., Inclusive Block Chain Protocols. In: Böhme R., Okamoto T. (eds) Financial Cryptography and Data Security, 2015. Lecture Notes in Computer Science, vol 8975. Springer, Berlin, Heidelberg (pdf)

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.

The talk is based on the paper with the same title by Rosario Gennaro, Craig Gentry and Bryan Parno.

Verifiable Computation enables a computationally weak client to "outsource" the computation of a function F on various inputs x₁, ..., x_k to one or more workers. The workers return the result of the function evaluation, e.g., y_i = F(x_i), as well as a proof that the computation of F was carried out correctly on the given value x_i. The verification of the proof should require substantially less computational effort than computing F(x_i) from scratch.

We present a protocol that allows the worker to return a computationally sound, non-interactive proof that can be verified in O(m) time, where m is the bit-length of the output of F. The protocol requires a one-time pre-processing stage by the client which takes O(|C|) time, where C is the smallest Boolean circuit computing F. Our scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the values x_i or y_i.

• A Note on Boolean Dimension of Posets, J. Nešetřil, P. Pudlák, Irregularities of Partitions, 137-140, 1989

Rozważany będzie problem istnienia wielomianowej bijekcji, najniższego stopnia, między N^k, a N. Przedstawione będą także problemy otwarte związane z tą tematyką.

Materiały do wystąpienia:

1) Elementarny dowód Twierdzenie Feuter-Polya (jedyny kwadratowy i bijektywny wielomian N^2->N to funkcja cantore'a) https://arxiv.org/abs/1512.08261

2) Praca, w której autorzy pokazują nieistnienie wielomianów 3 i 4 stopnia.  http://www.sciencedirect.com/science/article/pii/0022314X78900367

3) Praca podobnie tematyczna odnosząca się do problemu istnienia wielomianów bijektywnych z pewnego sektora N^2 w N. (To o czym wspomniałem na koniec, opis tego problemu jest też pod koniec w 1) ). Pod koniec pracy jest opisane 6 problemów otwartych związanych z tą tematyką. https://arxiv.org/abs/1305.2538

4) W podobnej tematyce. http://www.sciencedirect.com/science/article/pii/0022314X78900355
 

We study a class of graphs that have a special geometric representation. By a bar visibility representation of an undirected graph we mean a function that associates with each vertex of a graph a horizontal line segment in such a way, that between segments representing two ends of an edge there is a vertical strip (of visibility). In case of directed graphs, we additionally assume that the visibility is from the bottom to the top, that is the line segment representing the source of the edge is below the one for the target.

Graphs admitting such representations are well understood and can be recognized in linear time, both in the undirected and in the directed case. We work in a more subtle setting, where line segments are already associated with some vertices of a graph, and the question is if this can be extended to a bar visibility representation of an entire graph. We prove some results on complexity of this kind of problems.

This is joint work with Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk and Giuseppe Liotta. The manuscript is available here: https://arxiv.org/abs/1512.00174

Until recently, all the algorithms for computing discrete logarithm had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In this talk we'll discuss a heuristic algorithm that provides quasi-polynomial complexity for discrete logarithm in finite fields of small characteristic and that even for other cases still surpasses the Function Field Sieve method.

References:

[1] R. Barbulescu, P. Gaudry, A. Joux, E. Thomé, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic (pdf)

Rozważamy następujący problem: wierzchołki drzewa ponumerowane są kolejnymi liczbami naturalnymi, a dodatkowo w wierzchołku x leży skrzynka o numerze p(x), przy czym funkcja p jest permutacją zbioru {1,2,..,n}. Rozważamy chodzącego po drzewie robota, który może w danym momencie trzymać tylko jedną skrzynkę, może też podnieść napotkaną skrzynkę upuszczając aktualnie trzymaną. Celem robota jest posortować skrzynki (przenosząc każdą do wierzchołka o odpowiednim numerze), przechodząc po drzewie najkrótszą możliwą ścieżką. Praca D. Grafa podaje algorytm znajdujący taką ścieżkę w czasie O(n²) oraz dowód, że jeśli drzewo zastąpimy grafem planarnym, problem staje się NP-zupełny.