# Poprzednie referaty

 17.06.2021 17:00 Szymon Salabura Optymalizacja Kombinatoryczna The Fixing Block Method in Combinatorics on Words A word is repetitive if it contains two consecutive identical blocks. A sequence is non-repetitive up to mod r if each of its mod k (1⩽k⩽r) subsequences is non-repetitive. Let L be a language of non-repetitive (up to mod r) words. In this seminar, we are going to take a look at fixing blocks - a special kind of suffixes preventing words of L to have an extension in L. Using the fixing blocks method we are going to show some interesting properties of such languages. We also outline a method of attack for more complex problems. (the seminar will only be online)
 17.06.2021 16:15 Wojciech Węgrzynek Optymalizacja Kombinatoryczna Non-repetetive words: ages and essences The age of an infinite word will be the set of all its finite subwords, it's essence will be the set of all finite subwords occurring infinitely many times. The language L{121,323} is the language of all square-free infinite words, such that they don’t have 121 or 323 as subwords. It turns out if we consider the equivalence relations on L{121,323} in respect to the ages and the essences we will get an uncountable cardinality of equivalence classes and 1 equivalence class respectively. (the seminar will only be online)
 16.06.2021 16:15 Krzysztof Turowski Informatyka Teoretyczna Degree Distribution of Dynamic Graphs Generated by a Duplication-Divergence Models We analyze the structure of dynamic graphs generated from duplication models in which a new vertex selects an existing vertex and copies some of its neighbors and then we add some random divergence. We analyze various graph parameters like mean degree, number of open triangles, number of triangles, number of vertices of degree k or maximum degree in a graph generated from such models. We provide asymptotic analysis of expected values and tail behavior of these parameters. We also point to further extensions of this approach towards computing symmetries in these graphs and algorithms for graph compression.   Joint work with Philippe Jacquet, Alan Frieze and Wojciech Szpankowski
 10.06.2021 17:00 Bartosz Wodziński Optymalizacja Kombinatoryczna Zarankiewicz's Problem and some related results In 1951, Kazimierz Zarankiewicz posed a problem asking for the largest possible number of edges in a bipartite graph that has a given number of vertices (n) and has no complete bipartite subgraphs of a given size. Although solved for some specific cases, it still remains open in general. It led to some interesting results in extremal graph theory, such as Kővári–Sós–Turán theorem which gives an upper bound for this problem. During the seminar, I will discuss several problems related to forbidding subgraphs, from easy up to unsolved ones. I will also show their connection with some geometric problems such as creating a maximum number of unit distances between n points on a plane. (the seminar will only be online)
 10.06.2021 16:15 Michał Zwonek Optymalizacja Kombinatoryczna Polyomino Tilings A polyomino is a subset of R2 formed by a strongly connected union of axis-aligned unit squares centered at locations on the square lattice Z2. Let T = {T1,T2,...} be an infinite set of finite simply connected closed sets of R2. Provided the elements of T have pairwise disjoint interiors and cover the Euclidean plane, then T is a tiling and the elements of T are called tiles. Provided every Ti ∈ 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. (the seminar will only be online)
 09.06.2021 16:15 Paweł Rzążewski Warsaw University of Technology Informatyka Teoretyczna Treewidth of graphs with forbidden induced subgraphs 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.
 08.06.2021 09:00 Bartosz Walczak Informatyka Teoretyczna Coloring polygon visibility graphs and their generalizations 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
 02.06.2021 16:15 Marthe Bonamy Université de Bordeaux Informatyka Teoretyczna Graph recolouring 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.
 27.05.2021 17:00 Jan Mełech Optymalizacja Kombinatoryczna Rödl Nibble For positive integers r
 27.05.2021 16:15 Krzysztof Pióro Optymalizacja Kombinatoryczna Decomposing planar graphs into graphs with degree restrictions Given a graph G, its (d,h)-decomposition is a partition of a set of edges of this graph into a d-degenerate graph and a graph with maximum degree at most h. We will study (d,h)-decomposability of planar graphs and consider the problem of finding minimum hd such that every planar graph is (d,hd)-decomposable. Since every planar graph is 5-degenerate, we will consider only the case of d less than 5. (the seminar will only be online)
 26.05.2021 Piotr Kawałek Informatyka Teoretyczna Constant depth circuits 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, ACC and CC. The most important challenges and some open problems are to be discussed.
 20.05.2021 17:00 Maciej Nemś Optymalizacja Kombinatoryczna Ant Colony Optimization Ant Colony Optimization algorithms are part of swarm intelligence approach to solving problems. They are inspired by behavior of ants. After finding a desired destination ants leave pheromones on the way back to the colony. This way all ants can detect the scent and decide to go in the direction suggested by pheromone trail. ACO is based on this concept and involves multi-agent computation. Communication between agents is done by changing the stimuli for all agents, to make a certain action. This is similar to ants leaving pheromones. Presentation will include basic concept of Ant Colony Optimization and an example of solving a well known problem using it. I will also present a formalization of ACO into a metaheuristic for combinatorial optimization problems. Presentation will end with talk about current state of ACO, its limitation and possible future. (the seminar will only be online)
 20.05.2021 16:15 Wojciech Buczek Optymalizacja Kombinatoryczna Woodall’s conjecture Woodall’s conjecture tells us, that any directed cut with at least k edges has at least k disjoint dijoins. Set of edges D is a dijoin if and only if the digraph (V, E ∪ D-1) is strongly connected. We will say about the linear programming formulation of this problem, equivalent and related problems to it, and some partial results by Shrijver, Lee and Wakabayashi, and Meszaros. We will also show counterexamples to a generalized version of the conjecture. (the seminar will only be online)
 19.05.2021 16:15 Paweł Idziak Informatyka Teoretyczna Modular circuits satisfiability of intermediate complexity 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
 13.05.2021 16:15 Vladyslav Rachek, Ruslan Yevdokymov Optymalizacja Kombinatoryczna An Introduction to the Discharging Method via Graph Coloring The discharging method is a technique that can be used to show that some global properties of a graph imply the existence of local structures. Then, we can sometimes show, that such structures imply that the graph has another global property. The discharging method is thus a "connector" between global properties of a graph (via local properties, e.g. having subgraphs or minors). In the first part of the presentation, we talk about the structure and coloring of sparse and plane graphs. Typical statements will sound like "If there is some global degree bound, then the chromatic number is somehow bounded" (the seminar will only be online)
 12.05.2021 16:15 Grzegorz Gutowski Informatyka Teoretyczna Filling blanks in matrices to avoid singularity: progress report 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.
 06.05.2021 17:00 Marcin Serwin Optymalizacja Kombinatoryczna Aanderaa-Karp-Rosenberg conjecture The conjecture deals with queries on graph. More concretely given property of a graph (such as connectedness or non-emptiness) we may ask whether it is possible to recognize a graph with this property without querying all of its edges. It turns out that for many properties it is indeed not possible to do so in a deterministic manner for all graphs. The Aanderaa–Karp–Rosenberg conjecture states that any non-trivial monotone graph property cannot be determined by a deterministic algorithm with less than n(n-1)/2 queries. Such graph properties are called evasive, thus this conjecture is sometimes called evasiveness conjecture. (the seminar will only be online)
 06.05.2021 16:15 Krzysztof Potępa Optymalizacja Kombinatoryczna Orienting Fully Dynamic Graphs with Worst-Case Time Bounds In the edge orientation problem, one is asked to orient edges of a given graph such that the out-degrees of vertices are bounded by some function. In the fully dynamic variant, we want to process arbitrary edge insertions and deletions in an online fashion. We will show an algorithm for graphs with bounded arboricity that achieves logarithmic out-degree bound and supports updates in O(log n) worst-case time. (the seminar will only be online)
 05.05.2021 16:15 Louis Esperet Université Grenoble Alpes Informatyka Teoretyczna Universal graphs and labelling schemes 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 2n/4+o(n)). I will also show how to construct isometric-universal graphs of size 3n+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.
 29.04.2021 16:15 Mateusz Kaczmarek Optymalizacja Kombinatoryczna On triangles in Kr-minor free graphs There is a close connection between minors of the graph and a lower bound on such number k that each edge (or vertex) belongs to at least k triangles. One of the most interesting classes of minors is the class of complete graphs Kr. In the paper 'On triangles in Kr-minor free graphs', Boris Albar and Daniel Gonçalves take a closer look at this class of graphs. Based on their work I will present some interesting results regarding this connection and show how it correlates with Hadwiger's conjecture. (the seminar will only be online)
 28.04.2021 16:15 Daniel Kráľ Masaryk University in Brno Informatyka Teoretyczna Quasirandom combinatorial structures 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.
 22.04.2021 16:15 Bartłomiej Jachowicz Optymalizacja Kombinatoryczna Acyclic coloring of graphs with fixed maximum degree An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted as a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. Known problem in this area is to find an upper bound for an acyclic chromatic number for graphs with a fixed maximum degree. One of the first papers on this topic is Hocquard's article "Graphs with maximum degree 6 are acyclically 11-colorable". The proofing technique from his work has been used in many later papers that show similar bounds for graphs with fixed maximum grades. (the seminar will only be online)
 21.04.2021 16:15 Paweł Gawrychowski University of Wrocław Informatyka Teoretyczna Fully Dynamic Longest Increasing Subsequence 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(ϵ−5). 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(n2/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
 15.04.2021 16:15 Piotr Mikołajczyk Optymalizacja Kombinatoryczna Thomassen's choosability argument revisited The Hadwiger Conjecture states that if a graph G does not contain a clique on t vertices as a minor, then G is (t-1)-colorable. For low values of t (<7) it was already shown that this claim is actually true. Currently, the best-known upper bound on the chromatic number of Kt-minor-free graphs is O(ct*sqrt(log(t))) and the proof follows from a degeneracy argument. Unfortunately, this approach cannot be exploited further. However, by revisiting Thomassen's reasoning from '94 we can try to prepare the ground for a new way of attacking the Hadwiger Conjecture based on graph choosability. For that, we will take a look at a new proof of a theorem that every K5-minor-free graph is 5-choosable. (the seminar will only be online)
 14.04.2021 16:15 Michał Seweryn Informatyka Teoretyczna Dimension of posets with k-outerplanar cover graphs 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(k3). As a consequence, we show that every poset with a planar cover graph and height h has dimension O(h3). This improves the previously best known bound of O(h6) by Kozik, Micek and Trotter. Joint work with Maximilian Gorsky https://arxiv.org/abs/2103.15920
 08.04.2021 16:15 Jędrzej Kula Optymalizacja Kombinatoryczna Combinatorial Nullstellensatz Proposed by Noga Alon in 1999 an algebraic technique inspired by Hilbert’s Nullstellensatz. Despite being an observation about roots of a polynomial in n variables, it finds a usage in numerous fields - from Combinatorial Number Theory to Graph Theory. The theory itself is simple, but can be used in ingenious ways - appearing even as almost a necessary step to solve a problem during the 2007 IMO competition. During this time slot I will present a theorem and prove it with as I believe a simpler proof constructed by Mateusz Michałek, that is using a basic induction idea over a polynomial degree. Finally we will again follow the original N. Alon paper to see applications of a theorem in the graph coloring problems and some more. Noga Alon. Combinatorial Nullstellensatz. Combinatorics Probability and Computing, 8 (1999), 7-29. (manuscript) Mateusz Michałek. A short proof of Combinatorial Nullstellensatz. American Mathematical Monthly, 117 (2010), 821-823. (arXiv:0904.4573) Tomasz Kochanek. Combinatorial Nullstellensatz. (2012) (pl). manuscript. Jędrzej Kula. Combinatorial Nullstellensatz. slides. (2021). (the seminar will only be online)
 07.04.2021 16:15 Mikołaj Bojańczyk University of Warsaw Informatyka Teoretyczna Recognisable languages over monads Algebraic language theory originated in the study of regular languages via semigroups, instead of automata. The advantage of the semigroup approach is a richer structural theory, e.g. Green’s theory or the Factorisation Forest Theorem. (In contrast, the structural analysis of automata seldom goes beyond such elementary notions as “cycle” or “connected component”.) In this talk, I will discuss a more abstract view on semigroups, as Eilenberg-Moore algebras over the monad of finite words (aka the list monad in programming languages). Using this abstract view, by changing the monad, one can get the appropriate notion of “semigroup” for objects beyond finite words, e.g. trees or graphs. Sometimes, even theorems can be proved using this abstract view.   This talk is based on the draft monograph  https://arxiv.org/pdf/2008.11635.pdf
 31.03.2021 16:15 Andrzej Dorobisz Informatyka Teoretyczna Local Computation Algorithms for Coloring of Uniform Hypergraphs 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 21-α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
 25.03.2021 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Local Dimension of Planar Poset In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, leading naturally to the questions as to whether either Boolean dimension or local dimension is bounded for the class of planar posets. The question for Boolean dimension was first posed by Nešetril and Pudlák in 1989 and remains unanswered today. The concept of local dimension is quite new, introduced in 2016 by Ueckerdt. In just the last year, researchers have obtained many interesting results concerning Boolean dimension and local dimension, contrasting these parameters with the classic Dushnik-Miller concept of dimension, and establishing links between both parameters and structural graph theory, path-width and tree-width in particular. Here we show that local dimension is not bounded on the class of planar posets. Our proof also shows that the local dimension of a poset is not bounded in terms of the maximum local dimension of its blocks, and it provides an alternative proof of the fact that the local dimension of a poset cannot be bounded in terms of the tree-width of its cover graph, independent of its height. This is a joint work with Jarosław Grytczuk and W.T. Trotter. Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter. Local Dimension is Unbounded for Planar Posets. arXiv, pages 1-12, 2017. (the seminar will only be online)
 24.03.2021 16:15 Marcin Pilipczuk University of Warsaw Informatyka Teoretyczna Recent progress in understanding H-free graphs for H being a path or a subdivided claw 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.
 18.03.2021 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna The 1/3 - 2/3 conjecture A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field. (the seminar will only be online)
 17.03.2021 16:15 Stefan Felsner Technische Universität Berlin Informatyka Teoretyczna Combinatorics of Pseudocircle Arrangements 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.
 11.03.2021 16:15 Jędrzej Hodor Optymalizacja Kombinatoryczna Polynomial Treedepth Bounds in Linear Colorings Centered graph coloring is graph coloring, such that for every connected subgraph, this subgraph contains a vertex with a unique color (we call such a vertex center). Linear coloring is coloring, such that every path has a center. We denote by cen(G) and lin(G) respectively, a minimal number of colors needed. It is obvious that lin(G) ≤ cen(G). What about the other direction? Authors of the paper show that cen ≤ f(lin), where f is a polynomial of the degree 190. Moreover, the authors conjecture that cen ≤ 2 lin for every graph. What is interesting, we don't know how to prove such abound even for trees. Luckily, for some classes of graphs, we can do better than 190-poly. During the seminar, I will present results for simple classes of graphs and I will try to sketch the general proof. In particular, I will present a cubic bound for interval graphs. The proof in the paper is incorrect, but I and dr Micek managed to fix it. Finally, I will present our new result for graphs with bounded path width. (the seminar will only be online)
 10.03.2021 16:15 Bartosz Walczak Informatyka Teoretyczna Approximating Pathwidth for Graphs of Small Treewidth 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 Ω(kc) 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.
 04.03.2021 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Majority choosability of digraphs One of the variations of coloring a graph is assigning colors to vertices such that for each vertex v, at most half of the neighbors of v have the same color as v. Such coloring is called majority coloring of the graph. The goal is to color the graph as a majority with the fewest possible colors. During the presentation, various variants of this problem, historical results, the latest results as well as still intriguing hypotheses will be discussed. Among other things, the results of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented. (the seminar will only be online)
 25.02.2021 16:15 Kamil Kropiewnicki Optymalizacja Kombinatoryczna Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programming We study the problem of learning a linear model to set the reserve price in an auction, given contextual information, in order to maximize expected revenue from the seller side. First, we show that it is not possible to solve this problem in polynomial time unless the Exponential Time Hypothesis fails. Second, we present a strong mixed-integer programming (MIP) formulation for this problem, which is capable of exactly modeling the nonconvex and discontinuous expected reward function. More broadly, we believe this work offers an indication of the strength of optimization methodologies like MIP to exactly model intrinsic discontinuities in machine learning problems. This presentation might be of interest for, among the others, the participants of the Algorithmic Game Theory course as it presents the modern approach for maximizing revenue in second-price auctions. (the seminar will only be online)
 28.01.2021 17:00 Rafał Burczyński Optymalizacja Kombinatoryczna Bollobás-Eldridge-Catlin Conjecture on graph packing Let G1, G2 be n-vertex graphs. We say that they pack if they are edge-disjoint subgraphs of a complete graph on n vertices. The Bollobás-Eldridge-Catlin conjecture states that if (Δ(G1) + 1) (Δ(G2) + 1) < n + 1, then G1 and G2 pack. During the seminar, we will take a look at current results related to this problem, i.e. classes of graphs for which it has been proven as well as similar conjectures stemming from it. (the seminar will only be online)
 28.01.2021 16:15 Weronika Lorenczyk Optymalizacja Kombinatoryczna The Cap Set Conjecture The cap set problem asks how large can a subset of Z/3Zn be and contain no lines or, more generally, how can large a subset of Z/pZn be and contain no arithmetic progression. The problem was open until 2016 when its basic version was solved. During the lecture, we'll see the motivation for thinking about this. It appears there are some interesting applications of this result in combinatorics, geometry, and even board games. (the seminar will only be online)
 21.01.2021 17:00 Bartosz Wodziński Optymalizacja Kombinatoryczna Graph Removal Lemma Let H be a graph on h vertices. The Graph Removal Lemma states that for any ε > 0, there exists a constant δ(ε, H) > 0 such that for any n-vertex graph G with fewer than δnh subgraphs isomorphic to H, it is possible to eliminate all copies of H by removing at most εn2 edges from G. It has several important consequences in number theory, discrete geometry, graph theory, and computer science. During the seminar, I will discuss this lemma and its extensions. I will also tell about some of its applications, such as graph property testing and Szeremedi's Theorem proof. (the seminar will only be online)
 21.01.2021 16:15 Artur Kasymov Optymalizacja Kombinatoryczna Machine learning in Combinatorial Optimization Machine learning has already leaked almost all areas. What about Combinatorial Optimization? At this seminar, I will present basic ML concepts and methods in CO: Where you can add ML black box in your algorithm? Can heuristics be compared to ML? What are the recent achievements? (the seminar will only be online)
 20.01.2021 12:15 Weronika Loreńczyk Podstawy Informatyki The Fractal Dimension of SAT Formulas by Carlos Ansotegui, Maria Bonet , Jesus Giraldez-Cru and Jordi Levy Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there is not a precise definition of the notion of structure. Recently, there have been some attempts to analyze this structure in terms of complex networks, with the long-term aim of explaining the success of SAT solving techniques, and possibly improving them. We study the fractal dimension of SAT instances with the aim of complementing the model that describes the structure of industrial instances. We show that many industrial families of formulas are self-similar, with a small fractal dimension. We also show how this dimension is affected by the addition of learnt clauses during the execution of SAT solvers.
 14.01.2021 17:00 Bruno Pitrus Optymalizacja Kombinatoryczna Seven trees in one: objects of categories as complex numbers Consider the following absurd argument concerning planar, binary, rooted, unlabelled trees. Every such tree is either the trivial tree or consists of a pair of trees joined together at the root, so the set T of trees is isomorphic to 1+T². Pretend that T is a complex number and solve the quadratic T = 1+T² to find that T is a primitive sixth root of unity and so T⁶ = 1. Deduce that T⁶ is a one-element set; realize immediately that this is wrong. Notice that T⁷ = T is, however, not obviously wrong, and conclude that it is therefore right. In other words, conclude that there is a bijection T⁷ ≅ T built up out of copies of the original bijection T ≅ 1+T²: a tree is the same as seven trees. (the seminar will only be online)
 14.01.2021 16:15 Krzysztof Pióro Optymalizacja Kombinatoryczna Gallai’s conjecture A path decomposition of a graph G is a collection of edge-disjoint paths of G that covers the edge set of G. Gallai (1968) conjectured that every connected graph on n vertices admits a path decomposition of cardinality at most ⌈n/2⌉. Gallai’s Conjecture has been verified for many classes of graphs. In this seminar, we will cover some of these graph classes. (the seminar will only be online)
 13.01.2021 12:14 Maciej Nemś Podstawy Informatyki Regular Matching and Inclusion on Compressed Tree Patterns with Context Variables by Iovka Boneva, Joachim Niehren, and Momar Sakho We study the complexity of regular matching and inclusion for compressed tree patterns extended by context variables. The addition of context variables to tree patterns permits us to properly capture compressed string patterns but also compressed patterns for unranked trees with tree and hedge variables. Regular inclusion for the latter is relevant to certain query answering on Xml streams with references.
 07.01.2021 16:15 Szymon Żak Optymalizacja Kombinatoryczna Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes In this seminar, I will cover general ideas that stand behind Aleph protocol. Aleph is a leaderless, fully asynchronous, Byzantine fault tolerant consensus protocol for ordering messages exchanged among processes. It is based on a distributed construction of a partially ordered set and the algorithm for reaching a consensus on its extension to a total order. (the seminar will only be online)
 17.12.2020 17:00 Jan Mełech Optymalizacja Kombinatoryczna Hamiltonian paths/cycles in vertex-transitive/symmetric graphs Graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on the vertices and edges surrounding it. In 1969, Lovasz conjectured that every finite connected vertex-transitive graph has Hamiltonian path. Moreover, up to now there are currently only five known connected vertex-transitive graphs not containing Hamiltonian cycle. In this seminar we will focus also on some other weaker variants of Lovasz conjecture related to other interesting class of graphs that encode the abstract structures of a groups - Cayley graphs. (the seminar will only be online)
 17.12.2020 16:15 Mateusz Kaczmarek Optymalizacja Kombinatoryczna From linear lambda terms to rooted trivalent maps Recent work on the combinatorics of the linear lambda term shows that it has various connections to the theory of graph surfaces (maps). Based on paper  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. (the seminar will only be online)
 16.12.2020 12:15 Weronika Loreńczyk - canceled Podstawy Informatyki The Fractal Dimension of SAT Formulas by Carlos Ansotegui, Maria Bonet , Jesus Giraldez-Cru and Jordi Levy Modern SAT solvers have experienced a remarkable progress on solving industrial instances. Most of the techniques have been developed after an intensive experimental process. It is believed that these techniques exploit the underlying structure of industrial instances. However, there is not a precise definition of the notion of structure. Recently, there have been some attempts to analyze this structure in terms of complex networks, with the long-term aim of explaining the success of SAT solving techniques, and possibly improving them. We study the fractal dimension of SAT instances with the aim of complementing the model that describes the structure of industrial instances. We show that many industrial families of formulas are self-similar, with a small fractal dimension. We also show how this dimension is affected by the addition of learnt clauses during the execution of SAT solvers.
 10.12.2020 17:00 Wojciech Buczek Optymalizacja Kombinatoryczna Inscribed square problem Let C be a Jordan curve. We say that polygon P is inscribed in C if all vertices of P belong to C. In the inscribed square problem we ask if every Jordan curve admits an inscribed square. It's also known as "Toeplitz’s conjecture" or the "Square peg problem". In this seminar, we will show some equivalent problems to this conjecture and focus on special cases of the Jordan curves. (the seminar will only be online)
 10.12.2020 16:15 Bartłomiej Jachowicz Optymalizacja Kombinatoryczna Parameterized by treewidth algorithms for Hamiltonian Cycle The Hamiltonian Cycle problem is one of the oldest and most common NP-complete problems. It consists of checking whether in a given graph there is a cycle visiting each vertex exactly once. I will present a parameterized algorithm based on graph tree decomposition. Assuming that a nice tree decomposition of the width k is known at the input Hamiltonian cycle problem can be solved in a time 2(O(k))n(O(1)). (the seminar will only be online)
 10.12.2020 14:15 Jacek Salata, Krzysztof Ziobro Algorytmika A New Upper Bound for Separating Words
 09.12.2020 12:14 Katarzyna Król Podstawy Informatyki A Lower Bound of the Number of Rewrite Rules Obtained by Homological Methods by Mirai Ikebuchi It is well-known that some equational theories such as groups or boolean algebras can be defined by fewer equational axioms than the original axioms. However, it is not easy to determine if a given set of axioms is the smallest or not. Malbos and Mimram investigated a general method to find a lower bound of the cardinality of the set of equational axioms (or rewrite rules) that is equivalent to a given equational theory (or term rewriting systems), using homological algebra. Their method is an analog of Squier’s homology theory on string rewriting systems. In this paper, we develop the homology theory for term rewriting systems more and provide a better lower bound under a stronger notion of equivalence than their equivalence. The author also implemented a program to compute the lower bounds.
 03.12.2020 17:00 Michał Zwonek Optymalizacja Kombinatoryczna Approximate Distance Oracles Given a finite metric space (V,d), an approximate distance oracle is a data structure which, when queried on two points u,v∈V, returns an approximation to the actual distance between u and v which is within some bounded stretch factor of the true distance. The first work in this area was done by Mikkel Thorup and Uri Zwick, they devised an oracle with construction time being O(kmn(1/k)) and with the space complexity of O(kn(1+1/k)). The achieved stretch, that is the measure of how accurate the answer by the approximate oracle will be, is bounded by (2k-1). The query time is O(k), this has been subsequently improved to O(log n) by Wulff-Nilsen and to O(1) by Shiri Chechik. (the seminar will only be online)
 03.12.2020 16:15 Wojciech Grabis Optymalizacja Kombinatoryczna Double-critical graph conjecture A connected graph G is called double-critical if the chromatic number of G decreases by two if any two adjacent vertices of G are removed. In 1966, Erdős and Lovász conjectured that the only double-critical n-chromatic graph is the complete graph on n vertices. During the seminar, I will present what has been verified about the conjecture. (the seminar will only be online)
 03.12.2020 14:15 Rafał Kilar, Szymon Salabura Algorytmika Tetris is NP-hard even with O(1) rows or columns
 02.12.2020 12:14 Wojciech Węgrzynek Podstawy Informatyki The repetition threshold for binary rich words by James Currie, Lucas Mol and Narad Rampersad A word of length n is rich if it contains n nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word with critical exponent  \$2 + \Sqrt{2}/2\$ ( = 2.707) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is \$2 + \Sqrt{2}/2\$ ). In this article, we give a structure theorem for infinite binary rich words that avoid 14/5-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is \$2 + \Sqrt{2}/2\$  , as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets.
 26.11.2020 17:00 Krzysztof Potępa Optymalizacja Kombinatoryczna Erdős–Hajnal conjecture A well-known theorem of Erdős states that there exists a graph on n vertices, with no clique or independent set of a size larger than O(log n). The Erdős–Hajnal conjecture says it is very different if we consider families of graphs defined by forbidden induced subgraphs. Specifically, it is conjectured that for every graph H, there exists a constant δ(H) such that every H-free graph G has either a clique or independent set of size |V(G)|δ(H). We will discuss some classes of graphs for which the conjecture has been proven, as well as weaker theorems that hold for all graphs. (the seminar will only be online)
 26.11.2020 16:15 Marcin Serwin Optymalizacja Kombinatoryczna (m,n)-cycle cover conjectures An (m,n)-cycle cover is a covering of a graph consisting of m cycles such that every edge is covered exactly n times. For positive integers m, n it is natural to ask what family of graphs have (m,n)-cycle covers. The answers are known for some values, but for many others, they are conjectured or totally open. (the seminar will only be online)
 26.11.2020 14:15 Jan Mełech, Michał Zwonek Algorytmika On the Fine-Grained Complexity of Parity Problems
 25.11.2020 12:14 Wojtek Grabis Podstawy Informatyki (Optimal) Duplication is not Elementary Recursive by Andrea Asperti, Paolo Coppola and Simone Martini In 1998 Asperti and Mairson proved that the cost of reducing a lambda-term using an optimal lambda-reducer (a la L´evy) cannot be bound by any elementary function in the number of shared-beta steps. We prove in this paper that an analogous result holds for Lamping’s abstract algorithm. That is, there is no elementary function in the number of shared beta steps bounding the number of duplication steps of the optimal reducer. This theorem vindicates the oracle of Lamping’s algorithm as the culprit for the negative result of Asperti and Mairson. The result is obtained using as a technical tool Elementary Affine Logic.
 19.11.2020 14:15 Łukasz Selwa, Juliusz Wajgelt Algorytmika Compact Distributed Certification of Planar Graphs
 18.11.2020 12:14 Michał Zwonek Podstawy Informatyki A Confluent Rewriting System Having No Computable, One-Step, Normalizing Strategy by JAKOB GRUE SIMONSEN A full and finitely generated Church-Rosser term rewriting system is presented that has no computable onestep, normalizing strategy; the system is both left- and right-linear. The result provides a negative answer to a question posed by Kennaway in 1989: Number 10 on the List of Open Problems in Rewriting.
 12.11.2020 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Harmonious Coloring of Hypergraphs A harmonious coloring of a k-uniform hypergraph H is a vertex coloring such that no two vertices in the same edge share the same color, and each k-element subset of colors appears on at most one edge. The harmonious number h(H) is the least number of colors needed for such a coloring. We prove that k-uniform hypergraphs of bounded maximum degree Δ satisfy h(H) = O(k√k!m), where m is the number of edges in H which is best possible up to a multiplicative constant. Moreover, for every fixed Δ, this constant tends to 1 with k → ∞. We use a novel method, called entropy compression, that emerged from the algorithmic version of the Lovász Local Lemma due to Moser and Tardos. This is joint work with Sebastian Czerwinski, Jarosław Grytczuk, and Paweł Rzazewski. (the seminar will only be online)
 12.11.2020 14:15 Dzianis Pivavarau, Dominik Wielgórski Algorytmika Explicit two-deletion codes with redundancy matching the existential bound
 05.11.2020 16:15 Piotr Mikołajczyk Optymalizacja Kombinatoryczna Polynomial algorithms for CFGs via semiring embeddings A few years ago M. Might et al. published somehow unusual approach to parsing context-free grammars by using derivative operator. Later it was proven, that its worst case complexity is polynomial, putting it on a par with other classical approaches. We introduce an elegant generalization to this method by a generic algorithm parametrized with a semiring. Depending on the chosen algebra we can obtain polynomial algorithms for problems like parsing, recognizing or counting parse trees for CFGs. (the seminar will only be online)
 05.11.2020 14:15 Bartłomiej Jachowicz, Mateusz Kaczmarek Algorytmika Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
 04.11.2020 12:14 Przemysław Simajchel Podstawy Informatyki COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS by IGOR PAK The paper gives a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.
 29.10.2020 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Majority choosability of digraphs One of the variations of coloring a graph is assigning colors to vertices such that for each vertex v, at most half of the neighbors of v have the same color as v. Such coloring is called majority coloring of the graph. The goal is to color the graph as a majority with the fewest possible colors. During the presentation, various variants of this problem, historical results, the latest results as well as still intriguing hypotheses will be discussed. Among other things, the results of joint cooperation with Marcin Anholcer, Jarosław Grytczuk, and Gabriel Jakóbczak will be presented. (the seminar will only be online)
 29.10.2020 14:15 Lech Duraj Algorytmika Range queries and triangles
 28.10.2020 12:14 CANCELED Podstawy Informatyki COMPLEXITY PROBLEMS IN ENUMERATIVE COMBINATORICS by IGOR PAK The paper gives a broad survey of recent results in Enumerative Combinatorics and their complexity aspects.
 22.10.2020 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna Conjecture 1/3 - 2/3 A given pair of two incomparable elements x, y in poset P is called balanced if, of all line extensions P, the element x lies above y by at most 2/3 and on at least 1/3 of all extensions of the poset P. The 1/3 - 2/3 conjecture says that any poset that is not linear has a balanced pair. The talk presents basic definitions and an overview of the most important results in this field. (the seminar will only be online)
 22.10.2020 14:15 Marcin Serwin, Wojciech Buczek Algorytmika A Double-Exponential Lower Bound for the Distinct Vectors Problem
 21.10.2020 12:15 Piotr Mikołajczak Podstawy Informatyki Asymptotic Approximation by Regular Languages by Ryoma Sin’ya This paper investigates a new property of formal languages called REG-measurability where REG is the class of regular languages. Intuitively, a language L is REG-measurable if there exists an infinite sequence of regular languages that “converges” to L. A language without REG-measurability has a complex shape in some sense so that it can not be (asymptotically) approximated by regular languages. We show that several context-free languages are REG-measurable (including languages with transcendental generating function and transcendental density, in particular), while a certain  simple deterministic context-free language and the set of primitive words are REG-immeasurable in a strong sense.
 15.10.2020 16:15 Vladyslav Rachek Optymalizacja Kombinatoryczna Small weak epsilon-nets Let P be a set of n points in R2, ε > 0. A set of points Q is called a weak ε-net for P with respect to a family S of objects (e.g. axis-parallel rectangles or convex sets) if every set from S containing more than εn points of P contains a point from Q. Let R be the family of all axis-parallel rectangles in R2 and εRk be the smallest real number such that for any P there exists a weak εRk-net of size k. The work by Aronov et al. suggests that the inequality εRk ≤ 2/(k+3) may hold. In this talk we present the complete proofs of this inequality for k=1,...,5 and prove that this bound is tight for k=1,2,3. Besides, it is not clear how to construct optimal nets. Langerman conjectured that k-point 2/(k+3)-nets can be chosen from some speciffc set of points which are the intersections of grid lines, where the grid is of size k×k. We give counterexamples to this conjecture for nets of size 3 through 6. Vladyslav Rachek. Small weak epsilon-nets in families of rectangles. Bachelor's Thesis. Jagiellonian University. 2020. 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. Vladyslav Rachek. On small weak epsilon-nets for axis-parallel rectangles. slides. 2020. (the seminar will only be online)
 15.10.2020 14:15 Krzysztof Pióro, Krzysztof Potępa Algorytmika Modular Subset Sum W problemie Modular Subset Sum dane są liczba naturalna m, n-elementowy multizbiór S liczb całkowitych z zakresu od 0 do m-1 oraz liczba t, dla której chcemy rozstrzygnąć, czy istnieje podzbiór S, który się do niej sumuje modulo m.   Przedstawimy własne algorytmy rozwiązujące powyższy problem. Wszystkie z nich będą sprowadzały problem Modular Subset Sum do problemu tekstowego. Na początku przedstawimy prosty algorytm działający w czasie O(n + m*log2(m)) wykorzystujący haszowanie i drzewa przedziałowe. Następnie pokażemy jak poprawić jego złożoność do O(n + m*log(m)). Na końcu zaprezentujemy w pełni deterministyczny wariant algorytmu działający w czasie O(n + m*log(m)*α(m)).
 14.10.2020 12:15 Jędrzej Hodor Podstawy Informatyki Bijective link between Chapoton’s new intervals and bipartite planar maps by Wenjie Fang In 2006, Chapoton defined a class of Tamari intervals called “new intervals” in his enumeration of Tamari intervals, and he found that these new intervals are equienumerated with bipartite planar maps. We present here a direct bijection between these two classes of objects using a new object called “degree tree”. Our bijection also gives an intuitive proof of an unpublished equi-distribution result of some statistics on new intervals given by Chapoton and Fusy.
 08.10.2020 16:15 Bartłomiej Bosek Optymalizacja Kombinatoryczna From the 1-2-3 Conjecture to the Riemann Hypothesis A series of open (and solved) problems will be presented at the seminar, starting with the 1-2-3 Conjecture and ending with the Riemann Hypothesis. (the seminar will only be online)
 08.10.2020 12:00 Patryk Mikos Informatyka Teoretyczna Geometric and weight constraints in Online Interval Coloring PhD defense - room 0004
 10.06.2020 17:00 Bartosz Wodziński Optymalizacja Kombinatoryczna On the unique games conjecture For many hard problems, instead of solving them directly, we need good approximation algorithms. Apart from good their time complexity and decent approximation factor guarantee, we would like to know whether they achieve the best possible approximation ratio (assuming P ≠ NP) possible. Unfortunately, for many NP-complete problems, there is a huge gap between best-known approximation ratio and the ratio that is proved to be unachievable in polynomial time. For instance, for Vertex Cover problem, we don't know any algorithm having a better ratio than 2, and it has been proved in 2005 that it is impossible to get a better ratio than ~1.36. As an attempt to fill in this gap, in 2002, the so-called Unique Games Conjecture was formulated by Khot. It states that having a (1-𝜀)-satisfiable instance of Unique Label Cover problem, it is NP-hard to find a solution satisfying even epsilon fraction of constraints. Assuming it, we are able to prove many tight inapproximability results, for example, it implies that Goemans-Williamson Algorithm for Max-Cut problem achieves the best possible approximation rate. It also follows that we cannot get any better ratio than 2 in the case of Vertex Cover problem. The Unique Games Conjecture is an unusual open problem since the academic world is about evenly divided on whether it is true or not. During the seminar, I will cover this conjecture in more details giving more examples of its influence and presenting recent progress in order to prove it. (the seminar will only be online)
 10.06.2020 16:15 Gabriela Czarska Optymalizacja Kombinatoryczna The Lonely Runner Conjecture Abstract. Suppose that k runners having different constant speeds run laps on a circular track of unit length. The Lonely Runner Conjecture states that, sooner or later, any given runner will be at distance at least 1/k from all the other runners. We prove that with probability tending to one, a much stronger statement holds for random sets in which the bound 1/k is replaced by 1/2 − ε. The proof uses Fourier analytic methods. We also point out some consequences of our result for colouring of random integer distance graphs. (the seminar will only be online)