Algorytmiczne Aspekty Kombinatoryki

prof. Jarosław Grytczuk

Modern Combinatorics is a fundamental area with many exciting topics of great importance in Computer Science. We will concentrate mainly on recent developments in Graph Coloring, Combinatorial Games, Ramsey Theory, Combinatorial Number Theory, Discrete Geometry, and Combinatorics on Words.
The seminar will run in two independent streams; one more focused on challenging open problems, the other more focused on methods. No special preparation is required from attendants but an "open brain".

Poprzednie referaty

 09.06.2016 Gwenaël Joret Université Libre de Bruxelles Improved Approximation Algorithms for Hitting 3-Vertex Paths We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Very recently, You, Wang, and Cao described a 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 7/3-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp constrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee. This is joint work with Samuel Fiorini and Oliver Schaudt.
 02.06.2016 http://wms.mat.agh.edu.pl/~knmd/index.php/i-konferencja-naukowa-knmd/harmonogram/ Konferencja Studencka na AGH
 19.05.2016 Miloš Stojaković University of Novi Sad Maker-Breaker games on random graphs Of all types of positional games, Maker-Breaker games are probably the most studied. We will survey the topic of Maker-Breaker games played on random graphs, where positional games on graphs meet some standard random graph models. The pace will be gentle, and we will not assume any particular prior knowledge on either positional games or random graphs.
 12.05.2016 Barłomiej Bosek Coloring shift-chain hypergraphs
 05.05.2016 Jarosław Grytczuk On some graph coloring problems
 28.04.2016 Wojciech Samotij Tel Aviv University How does a typical finite metric space look like?
 21.04.2016 Jarosław Grytczuk On some problems in combinatorial number theory
 14.04.2016 Michał Farnik Jagiellonian University Hat guessing game on sparse graphs
 07.04.2016 Steven Chaplick, Universitat Wurzburg Intersection Graphs of Non-crossing Paths
 31.03.2016 Grzegorz Bukowiec Thue Games
 17.03.2016 Gabriel Jakóbczak Additive chromatic number of several graph families
 03.03.2016 Jarosław Grytczuk Pattern avoiding coloring of the plane
 25.02.2016 Jarosław Grytczuk Higher order arboricity of graphs
 28.01.2016 Patryk Mikos Complexity of GKS communication game
 21.01.2016 Jarosław Grytczuk Coloring graphs with many colors on cycles
 14.01.2016 Michał Laosń IM PAN, Freie Universitat Berlin On the toric ideal of a matroid and related combinatorial problems When an ideal is defined only by combinatorial means, one expects to have a combinatorial description of its set of generators. An attempt to achieve this description often leads to surprisingly deep combinatorial questions. White's conjecture is an example. It asserts that the toric ideal associated to a matroid is generated by quadratic binomials corresponding to symmetric exchanges. In the combinatorial language it means that if two multisets of bases of a matroid have equal union (as a multiset), then one can pass between them by a sequence of symmetric exchanges. White's conjecture resisted numerous attempts since its formulation in 1980. We will discuss its relations with other open problems concerning matroids.
 07.01.2016 Mateusz Michałek IM PAN, Warszawa, Freie Universitaet, Berlin Tensors and algorithms for matrix multiplication
 17.12.2015 Jarosław Grytczuk The Log-rank Conjecture
 03.12.2015 Jarosław Grytczuk Localization games on graphs II
 26.11.2015 Jarosław Grytczuk Localization games on graphs
 19.11.2015 Adam Polak The Evasiveness Conjecture II
 12.11.2015 Adam Polak The Evasiveness Conjecture I
 05.11.2015 Adam Gągol Jagiellonian University On the Lonely Runner Problem II
 29.10.2015 Adam Gągol On the Lonely Runner Problem I
 22.10.2015 Gabriel Jakóbczak The chromatic number of the plane
 26.02.2015 Jarosław Grytczuk The Sensitivity Conjecture
 22.01.2015 Adam Polak Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
 15.01.2015 Teodor Jerzak Buffon's needle
 08.01.2015 Grzegorz Gutowski Avoiding Facial Repetitions
 18.12.2014 Jakub Cieśla Hat Guessing Games
 11.12.2014 Jarosław Grytczuk Ramsey Theory on the Integers
 04.12.2014 Jarosław Grytczuk Problems and results in combinatorial number theory
 27.11.2014 Grzegorz Guśpiel Homomorphisms of Edge-coloured Graphs
 20.11.2014 Piotr Kawałek Monotone broadcast digraphs
 13.11.2014 Patryk Mikos A hats game puzzle and generalized covers
 06.11.2014 Dorota Kapturkiewicz Monotone paths in bounded degree graphs
 30.10.2014 Michał Seweryn Multiple intersection of set systems
 21.10.2014 Adam Gągol Ternary pattern avoidance in partial words
 05.06.2014 Wojciech Lubawski On-line arboricity of graphs
 29.05.2014 Piotr Szafruga Coloring unit disk graphs
 15.05.2014 Jarosław Grytczuk Nonrepetitive coloring of the plane
 08.05.2014 Maciej Gawron Twins in Words and Permutations
 24.04.2014 Wojciech Lubawski Rota basis conjecture for sparse paving matroids
 10.04.2014 Wojciech Lubawski Graph arboricity and matroids on-line Kolorowanie krawędzi grafu nazwiemy poprawnym, jeśli zbiory jednokolorowe nie zawierają cykli. Wzorując się na przykładach z kolorowania wierzchołków grafu, rozważymy kilka różnych dwuosobowych gier, w których prezenter ujawnia część informacji o grafie, jak na przykład: należenie danej krawędzi do grafu, listę kolorów dozwolonych dla danej krawędzi grafu, zbiór krawędzi na których można użyć danego koloru itp., a algorytm ma za zadanie doprowadzić do poprawnego pokolorowania wszystkich krawędzi grafu. Liczbę kolorów zapewniającą algorytmowi strategię wygrywającą powiążemy z najmniejszą liczbą kolorów potrzebną do poprawnego pokolorowania off-line krawędzi grafu. Otrzymane wyniki uogólnimy do matroidów.
 03.04.2014 Michał Farnik Beyond the Shannon's Bound Let G=(V,E) be a multigraph of maximum degree D. The edges of G can be colored with at most 3D/2 colors by Shannon's theorem. We study lower bounds on the size of subgraphs of G that can be colored with D colors. Shannon's Theorem gives a bound of D|E|/floor(3D/2). However, for D=3, Kamiński and Kowalik showed that there is a 3-edge-colorable subgraph of size at least 7|E|/9, unless G has a connected component isomorphic to K_3+e (a K_3 with an arbitrary edge doubled). We extend this line of research by showing that G has a D-edge colorable subgraph with at least D|E|/(floor(3D/2)-1) edges, unless D is even and G contains D/2 K_3 or D is odd and G contains (D-1)/2 K_3+e. Moreover, the subgraph and its coloring can be found in polynomial time. Our results have applications in approximation algorithms for the Maximum k-Edge-Colorable Subgraph problem. For every even k>=4 we obtain a (2k+2)/(3k+2)-approximation and for every odd k>=5 we get a (2k+1)/3k-approximation. When 4<= k<= 13 this improves over earlier algorithms due to Feige et al. This is joint work with Łukasz Kowalik and Arkadiusz Socała.
 27.03.2014 Michał Masłowski Maximizing the number of nonnegative subsets
 20.03.2014 Grzegorz Guśpiel Block partitions of sequences
 13.03.2014 Grzegorz Gutowski Coloring 3-colorable graphs on-line
 06.03.2014 Adam Gągol Application of probabilistic method in some colourings of bounded path-width graphs
 27.02.2014 Michał Zmarz Playing nonrepetitive games
 23.01.2014 Karol Kosiński A generalization of Thue freeness for partial words
 16.01.2014 Jaroslaw Grytczuk Three variations on the theme of Szemeredi
 09.01.2014 Marcin Dziaduś Coloring intersection graphs of pseudo-discs
 19.12.2013 Jan Volec (University of Warwick) Compactness and finitely forcible graphons Graphons are limit objects that are associated with convergent sequences of graphs. Problems from extremal combinatorics led to a study of graphons determined by finitely many subgraph densities, which are referred to as finitely forcible graphons. In 2011, Lovasz and Szegedy asked several questions about the complexity of the topological space of so-called typical vertices of a finitely forcible graphon can be. In particular, they conjectured that the space is always compact. We disprove the conjecture by constructing a finitely forcible graphon such that the associated space of typical vertices is not compact. In fact, our construction actually provides an example of a finitely forcible graphon with the space which is even not locally compact. This is a joint work with Roman Glebov and Dan Kral.
 12.12.2013 Andrzej Dorobisz The game Grundy number of graphs
 05.12.2013 Wojciech Lubawski Delay colorings of matroids
 28.11.2013 21.11.2013,Grzegorz Gutowski The weak 3-flow conjecture and the weak circular flow conjecture
 14.11.2013 Robert Obryk Network routing as a multiparty game with asynchronous moves
 07.11.2013 Karol Kosiński On some properties of (strongly) non-repetitive sequences
 24.10.2013 Wiktor Kuropatwa Distortion-colouring of cubic bipartite multigraphs
 17.10.2013 Jakub Kozik Random Greedy Coloring of Uniform Hypergraphs
 10.10.2013 Dawid Ireno The Cinderella Game on Holes and Anti-holes
 03.10.2013 Jarosław Grytczuk Fractions, Continued and Egyptian I will present some problems and results on continued fractions and Egyptian fractions.
 13.06.2013 Jakub Brzeski The universal and canonically colored sequences
 06.06.2013 Marcin Dziaduś The Caccetta-Haggkvist Conjecture and Additive Number Theory
 23.05.2013 Wojciech Lubawski Lovasz's original proof of Kneser conjecture In the last thirty years algebraic topology has become an important tool in combinatorics. We will show a classical proof of Kneser conjecture in which the author related n-colorability of a graph with k-connectedness of a neighbourhood simplicial complex. If time permits we will show some other applications of algebraic topology in combinatorics.
 16.05.2013 Grzegorz Stachowiak (UWr) Counting and generating linear extensions I begin with the problem of computing two numbers related to a partial order: the number of linear extensions e(P) and the parity difference d(P). This second numer is the difference between the number of linear extensions being odd and even permutations. The number d(P) was considered because the condition d(P)=0,1 is a necessary for the existence of of an algorithm generating linear extensions by transpositions. Both e(P) and d(P) are comparability invariants. Computing both of them is #P-hard. I will describe two simple algorithms to compute e(P) for special classes of posets. I will also formulate necessary and sufficient conditions for the possibility of generating permutations of a multiset by adjacent transpositions.
 09.05.2013 Piotr Wójcik On algebraic invariants of geometric graphs; the Colin de Verdiere number.
 25.04.2013 Michał Lasoń New challenges in Matroid Theory
 18.04.2013 Michał Sapalski Oblivious Collaboration
 04.04.2013 Szymon Borak Domination Game
 28.03.2013 Robert Obryk Topological structure of asynchronous computability
 21.03.2013 Grzegorz Gutowski Nonrepetitive colourings of planar graphs with O(log n) colours
 14.03.2013 Bartosz Zaleski (UAM) The Neighbourhood Conjecture
 07.03.2013 Grzegorz Gutowski The List Coloring Conjecture for planar graphs
 28.02.2013 Jarosław Grytczuk Perspectives in the Online Ramsey Theory
 24.01.2013 Maciej Kalkowski (UAM) Irregularity strength in distributed model
 17.01.2013 Jarek Grytczuk Strong chromatic index of graphs
 10.01.2013 Paweł Wanat The seating couples problem
 03.01.2013 Jarosław Grytczuk Old and new challenges in Thue theory
 20.12.2012 Bartosz Walczak Optimal tree-grabbing Alice and Bob share an unrooted tree with non-negative weights assigned to the vertices, and play a game on it. In the first move, Alice cuts a leaf of the tree and scores its weight. Then, Bob and Alice alternate turns, in each move cutting a leaf of the remaining tree and adding its weight to their own score. Their goal in the game is to maximize their own final score. This game has been introduced in a joint paper with Micek , where we proved that Alice can guarantee herself at least 1/4 of the total weight of the tree, and conjectured that actually she can do at least 1/2. This conjecture has been proved by Seacrest and Seacrest . Now, an intriguing open problem is to devise a polynomial-time algorithm computing an optimal move at any position of the game. In this talk, I will share my thoughts of what such an algorithm may look like, and ask the audience for a proof of correctness or a counterexample :)   References: Piotr Micek, Bartosz Walczak, A graph-grabbing game, Combinatorics, Probability and Computing 20 (2011), 623-629 Deborah E. Seacrest, Tyler Seacrest, Grabbing the gold, Discrete Mathematics 312 (2012), 1804-1806
 13.12.2012 Michał Sapalski Finding minimum-weight (undirected) spanning tree for process networks
 06.12.2012 Agnieszka Łupińska On square-free permutations
 06.12.2012 Agnieszka Paszek Zen puzzle garden is NP-complete
 29.11.2012 Jarosław Grytczuk Lonely runner graphs
 22.11.2012 Adam Polak Distributed graph coloring II
 15.11.2012 Adam Polak Distributed graph coloring
 08.11.2012 Robert Obryk A near-optimal cardinality estimation algorithm
 25.10.2012 Andrzej Pezarski On-line clique covering of interval graphs II
 18.10.2012 Andrzej Pezarski On-line clique covering of interval graphs
 11.10.2012 Jarosław Grytczuk Coloring problems for graphs and matroids
 04.10.2012 Bartłomiej Bosek Coloring gcd-graphs
 14.06.2012 Michał Kukieła Algebraic topology applied to evasiveness of graph properties The evasiveness conjecture (also known as the Aanderaa-Karp-Rosenberg conjecture) states that any non-trivial monotone property P of graphs on a fixed set of n vertices (i.e. a property closed under removing edges) is evasive, which means that given an unknown graph G on the n vertices and allowed to ask whether a given edge belongs to G, we need in the worst case to ask about all possible n(n-1)/2 edges in order to determine whether G has the property P or not. In other words, P has decision tree complexity n(n-1)/2. I will discuss the classical paper of Jeff Kahn, Michael Saks and Dean Sturtevant that applies techniques of algebraic topology to this conjecture, proving it in the case when n is a prime power. If there is enough time left I shall give a short survey of some recent results in this area.
 31.05.2012 Karol Kosiński A regularity lemma and twins in words For a word S, let f(S) be the largest integer m such that there are two disjoints identical (scattered) subwords of length m. Let f(n,A) = min{f(S) : S is of length n, over alphabet A}. Here, it is shown that 2f(n,{0,1}) = n − o(n) using the regularity lemma for words. I.e., any binary word of length n can be split into two identical subwords (referred to as twins) and, perhaps, a remaining subword of length o(n). A similar result is proven for k identical subwords of a word over an alphabet with at most k letters.
 24.05.2012 Piotr Faliszewski (AGH) Clone Structures in Voters' Preferences In elections, a set of candidates ranked consecutively (though possibly in different order) by all voters is called a clone set, and its members are called clones. A clone structure is a family of all clone sets of a given election. In this paper we study properties of clone structures. In particular, we give an axiomatic characterization of clone structures, show their hierarchical structure, and analyze clone structures in single-peaked and single-crossing elections. We give a polynomial-time algorithm that finds a minimal collection of clones that need to be collapsed for an election to become single-peaked, and we show that this problem is NP-hard for single-crossing elections. Joint work with Edith Elkind and Arkadii Slinko, to be presented at 13th ACM Conference on Electronic Commerce. The paper is available at: http://home.agh.edu.pl/~faliszew/decloning.pdf
 17.05.2012 Paweł Dłotko Forman's discrete Morse theory + applications
 10.05.2012 Andrzej Kisielewicz, Krzysztof Przesławski (UZ) On the structure of tilings of Euclidean space by unit cubes -- around (disproved) Keller's conjecture
 26.04.2012 Gwenaël Joret Excluded Forest Minors and the Erdos-Posa Property A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdos-Posa property; namely, there exists a function f depending only on H such that, for every graph G and every positive integer k, either G has k vertex-disjoint subgraphs each containing H as a minor, or there exists a subset X of vertices of G with |X| \leq f(k) such that G - X has no H-minor. While the best function f currently known is super-exponential in k, a O(k log k) bound is known in the special case where H is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour, and Thomas on the pathwidth of graphs with an excluded forest-minor. In this talk I will sketch a proof that the function f can be taken to be linear when H is a forest. This is best possible in the sense that no linear bound exists if H has a cycle. Joint work with S. Fiorini and D. R. Wood.
 12.04.2012 Jakub Przybyło (AGH) Can colour-blind distinguish three-colour pallets? Yes they can!
 05.04.2012 Canceled SeminariumAAK 05.04.2012
 29.03.2012 Piotr Skowron (UW) Selective complexity issues of elections
 22.03.2012 Paweł Petecki Hamiltonian decompositions of k-uniform hypergraphs
 15.03.2012 Arkadiusz Pawlik Coloring intersection graphs of segments in the plane
 15.03.2012 Paweł Petecki Hamiltonian decompositions of k-uniform hypergraphs
 08.03.2012 Zbigniew Lonc (PW) Constructions of asymptotically shortest k-radius sequences
 01.03.2012 Monika Pilśniak (AGH) Graph coloring for color blind persons
 23.02.2012 Jarosław Grytczuk Multidimensional necklace splitting
 12.01.2012 Mateusz Nikodem O wierzchołkowej stabilności grafów Niech H będzie ustalonym grafem. Graf G nazywamy (H,k)-wierzchołkowo stabilnym jeśli G zawiera H nawet po usunięciu dowolnych k wierzchołków spośród V(G). Interesujące dla nas są grafy (H,k)-stabilne o możliwie małej liczbie krawędzi.
 01.12.2011 Piotr Micek Choice number versus its on-line counterpart
 24.11.2011 canceled SeminariumAAK 24.11.2011
 17.11.2011 Grzegorz Gutowski On-line choice number
 10.11.2011 Bartosz Walczak Outerplanar graph drawings with few slopes How many different edge slopes are necessary and sufficient to draw any outerplanar graph of degree Delta in the plane in the outerplanar way, that is, so that edges are non-crossing straight-line segments and all vertices lie on the outer face? We show that this number for Delta>3 is precisely Delta-1. This is joint work with Kolja Knauer and Piotr Micek.
 03.11.2011 Arkadiusz Pawlik On the Albertson Crossing Conjecture
 27.10.2011 Andrzej Grzesik Flag algebras for beginners
 20.10.2011 canceled SeminariumAAK 20.10.2011
 13.10.2011 Wiktor Żelazny Fictional coloring of graphs
 06.10.2011 Jarosław Grytczuk Lucky labelings of planar graphs
 09.06.2011 Jakub Przybyło (AGH) Proper edge colourings with different color paletts on adjacent vertices - algorithms based on Combinatorial Nullstellensatz
 02.06.2011 Paweł Rzążewski (Politechnika Warszawska) Exact algorithms for L(2,1)-coloring problem
 26.05.2011 Paweł Petecki (AGH) Grasshopper jumping in both directions
 19.05.2011 Marek Grabowski (UW) Nowhere 0 mod p graph colorings
 12.05.2011 Wiktor Żelazny More on additive colorings of graphs
 05.05.2011 A. Nilli On the chromatic number of random Cayley graphs
 28.04.2011 Marek Markiewicz On the recursive sequence of Ulas
 14.04.2011 canceled SeminariumAAK 14.04.2011
 07.04.2011 Jarosław Grytczuk How to color a graph
 31.03.2011 Jarosław Grytczuk Random runners are very lonely
 24.03.2011 canceled SeminariumAAK 24.03.2011
 17.03.2011 Michał Lasoń Mr. Paint and Mrs. Correct are doing it on matroids
 10.03.2011 Przemysław Mazur Multiple recurrence and arithmetic progressions
 03.03.2011 Michał Farnik Cuts, Graphons, and Szemeredi Regularity Lemma
 27.01.2011 Michał Farnik Graphons, cut norm, and distance
 20.01.2011 canceled SeminariumAAK 20.01.2011
 13.01.2011 Marcin Witkowski Nonrepetitive sequences up to (mod k)
 16.12.2010 Arkadiusz Pawlik Coloring geometric intersection graphs
 09.12.2010 Michał Zmarz Graph layouts and nonrepetitive colorings
 02.12.2010 Leszek Horwath On-line conflict-free coloring of intervals
 25.11.2010 Piotr Szafruga On-line nonrepetitive games
 18.11.2010 Marek Adrian Covering systems of congruences; an application of the number-theoretic local lemma
 04.11.2010 Grzegorz Gutowski Fractional list coloring of graphs
 28.10.2010 Karol Kosiński On some edit distance problems String edit distance is a minimum total cost of edit operations (inserting, deleting and changing letters) needed to receive one string from another. Edit distance problem can be also extendeded in many ways to rooted labeled trees. We will consider constrained variants of tree edit distance problem and related tree inclusion problem in order to show efficient solutions to some classes of mentioned trees. The seminar is based on my master's thesis.
 21.10.2010 Canceled due to Jarosław Duda's PhD defence
 14.10.2010 Open problem ob-session
 07.10.2010 Maciej Ulas Arithmetic properies of Stern polynomials We prove several theorems concerning arithmetic properties of Stern polynomials defined in the following way: $B_{0}(t)=0, B_{1}(t)=1, B_{2n}(t)=tB_{n}(t)$, and $B_{2n+1}(t)=B_{n}(t)+B_{n+1}(t)$. We study also the sequence $e(n)=\op{deg}_{t}B_{n}(t)$ and give many of its properties. This is joint work with Oliwia Ulas.
 10.06.2010 Andrzej Lembas Elections can be manipulated often Every non-trivial voting method between at least 3 alternatives can be strategically manipulated. Definitions of Social choice functions, manipulation, manipulation power. Main theorem: There exists a constant C>0 such that for every e>0, if f is a neutral social choice function among 3 alternatives for n voters, then the sum of probabilities manipulation power is >= Ce^2. Example.
 27.05.2010 Tibor SzaboFreie Universitat Berlin On minimal Ramsey graphs A graph G is called H-Ramsey if any two-coloring of the edges of G contains a monochromatic copy of H. An H-Ramsey graph is called H-minimal if no proper subgraph of it is H-Ramsey. Minimal Ramsey graphs were the subject of intensive research in the past four decades, going back to an innocent looking question of Erdos and Hajnal from the 60's concerning the existence of K_6-free K_3-Ramsey graphs. After an overview of the topic we concentrate on the minimum degree of H-minimal graphs, a problem initiated by Burr, Erdos, and Lovasz. We determine the smallest possible minimum degree of H-minimal graphs for numerous bipartite graphs H, including bi-regular bipartite graphs and forests. We also make initial progress for graphs of larger chromatic number. This represents joint work with Philipp Zumstein and Stefanie Zurcher.
 20.05.2010 cancelled
 13.05.2010 Zofia Miechowicz University of Grunberg Game chromatic number of Cartesian product graphs
 06.05.2010 Leszek Horwath Online preemptive weighted scheduling
 29.04.2010 Grzegorz Gutowski List Edge Colourings I will present the classical result of Galvin settling the famous list colouring conjecture for bipartite graphs. Some related problems and questions will be posed. Based on a paper of Borodin, Kostochka and Woodall.   References:O.V.Borodin, A.V.Kostochka, D.R.Woodall, List Edge and List Total Colourings of Multigraphs, Journal of Combinatorial Theory, Series B 71, pp. 184-204, 1997
 15.04.2010 canceled SeminariumAAK 15.04.2010 In view of an alternative event: http://www.ii.uj.edu.pl/index.php?mact=News,cntnt01,detail,0&cntnt01articleid=37&cntnt01returnid=92&hl=pol
 08.04.2010 Witold SzczechlaWarsaw University A solution for the three-colour hat guessing problem for cycles We consider the hat guessing problem for cycles. We prove that Bears win the 3-colour game on C_N if and only if N is divisible by 3, or N=4.
 25.03.2010 Mikołaj Pudo Geometry of solution space of random SAT In this talk, I will discuss the structure of satisfying assignments of a random k-SAT formula. We will be interested in the evolution of geometry of this space as constraints (clauses) are added. In particular I will show that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters.
 18.03.2010 Jarosław Grytczuk The Lovasz Local Lemma - satisfaction guaranteed I will present some recent spectacular applications of the local lemma for various problems in distinct areas of Mathematics and Computer Science. New directions for further research will be discussed.
 11.03.2010 Piotr Szafruga Algebraic proof of Brooks' theorem I will present proof of Brooks' theorem for list coloring using the algebraic method of Alon and Tarsi. This also shows that the Brooks' theorem remains valid in more general game coloring setting. Based on paper of Hladky, Kral and Schauz.
 04.03.2010 Michał Lasoń Algebraic methods in discrete analogs of the Kakeya problem I will prove the "joints" conjecture, which says that given N lines in space there are at most O(N^(3/2)) joints, that is points where at least three not coplanar lines intersect. Based on paper of Guth and Katz.
 25.02.2010 Wesley PegdenRutgers University Games where the Local Lemma works In this talk, I will discuss probabilistic proofs for the existence of winning strategies in sequence games where the goal is nonrepetitiveness. The technique involves a one-sided' generalization of the Local Lemma, which allows us to ignore the dependencies on future' events which would normally prevent this kind of proof from working. I will also discuss the extension of these results to graphs. Although many proofs about games are motivated by a probabilistic intuition, these results appear to represent the first successful applications of a Local Lemma to combinatorial games. If there is time, I will discuss an interesting (and frustrating!) game where this kind of approach has not yet succeeded.
 21.01.2010 Jarosław Grytczuk Big-line-big-clique conjecture
 07.01.2010 Jarosław Grytczuk My favorite four color problems
 17.12.2009 Przemysław Mazur Hat guessing game on graphs Suppose that n bears are standing on the n vertices of a graph G. Each of them can see only colleagues from the adjacent vertices. Suddenly, on every bear's head, a hat falls down in one of k available colors. Then, after a moment of looking around, each bear must write down the supposed color of its own hat (meanwhile they cannot communicate). The bears win the game if at least one of them correctly guesses the color of his hat. Otherwise they loose. The maximum number of hat colors for which the bears have a winning strategy on a graph G is called the bear number of G, denoted by mi(G). For instance, mi(C_4)=3, while mi(C_5)=2. We will present sveral results and conjectures on this fascinating game.
 10.12.2009 Andrzej Grzesik The chromatic sum of a graph The "chromatic sum" of a graph is the smallest sum of colors among all proper colorings with natural numbers. The "strength" of a graph is the minimum number of colors necessary to obtain its chromatic sum. Some existing problems and results about these parameters will be presented.
 03.12.2009 Mateusz NikodemAGH University of Science and Technology Foult-tolerant dominating sets Assume that each vertex of a graph G is the possible location for an "intruder" such as a thief, or some possible processor fault in a computer network. Consider a set S which is a subset of V(G). Assume that any s of S is able to detect an intruder at any vertex in its closed neighborhood N[s] with identifying the location in N[s]. We want to construct the set S such that an intruder will be detected in any vertex of G, even if k vertices of S are liars and l vertices of S are false-alarm makers. Some necessary and and sufficient conditions for such set S will be presented.
 26.11.2009 Tomasz DzidoUG Gdańsk Altitude of wheels, wheel-like graphs and some r-partite graphs In my talk I want to present definition, properties and all known results for Altitude of different graphs. In addition, I want to show some new results. I will consider Altitude of wheels and wheel-like graphs as fans, gear graphs and helms. Finally, I will present some values and bounds for Altitude of 2 i 3-partite graphs.
 19.11.2009 Michał Farnik Riemann-Roch versus chip-firing A finite graph can be viewed as a discrete analogue of a Riemann surface, or smooth complete complex curve. During my talk I will present some recent results using this analogy in the context of linear equivalence of divisors. In particular I will formulate a graph-theoretic analogue of the classical Riemann-Roch Theorem and show how to apply it to characterize the existence or non-existence of a winning strategy for a certain chip-firing game played on the vertices of a graph.
 05.11.2009 Hao LiUniversite de Paris-Sud Rainbow subgraphs in edge colored graphs Jest to kolejny wykład w ramach inicjatywy SSAK. Czas - 16:30, miejsce - kampus AGH (budynek B7, sala 1.9), obecność - obowiązkowa.
 29.10.2009 Paweł ŻylińskiUG Gdańsk Guarding grids and related graph problems The guards problem in grids is one of the art gallery problems and it was formulated by Ntafos in 1986. A grid P is a connected union of vertical and horizontal line segments; a grid may be thought of as an orthogonal polygon with holes, with very thin corridors. A point x in P can see point y in P if the line segment xy is a subset of P. A set of points S, being a subset of P, is a guard set for grid P if any point of P is seen by at least one guard in S. During my talk, I will present several variants of the problem, including cooperative guards, fault-tolerant guards, mobile guards, and the pursuit evasion problem, and discuss their relation to the well-known graph theory problems, e.g., matching, coloring, domination.
 22.10.2009 Dominik Kwietniak Combinatorial dynamics of one-dimensional maps Problems connected to one-dimensional dynamics are often expressed in the language of combinatorics. To solve them one deals mainly with permutations, graphs, etc. During this talk, an introduction to the subject will be presented. If time permits, some open problems, in which combinatorial approach might provide a solution, will be included.
 15.10.2009 Piotr Cieślik Set intersection, perfect graphs, and voting in agreeable societies When is agreement possible? An important aspect of group decision-making is the question of how a group makes a choice when individual preferences may differ. Clearly, when making a single group choice, people cannot all have their "ideal" preferences, i.e, the options that they most desire, if those ideal preferences are different. However, for the sake of agreement, people may be willing to accept as a group choice an option that is merely "close" to their ideal preferences.
 08.10.2009 Mateusz Michałek Counting homologies
 04.06.2009 Jarek Grytczuk Mr. Paint and Mrs. Correct
 28.05.2009 Andrzej RucińskiUAM Poznań 2nd Discrete Integration Meeting & SSAK Kampus AGH, budynek B7, sala 1.9, godzina 16:00.
 14.05.2009 Jan Jeżabek Collecting weighted items from a dynamic queue We consider the following problem: at each step some new weighted items are added to a dynamic queue (at any position) and some items from the front of the queue expire. We may collect one item at each step. Our objective is to maximize the total weight of collected items. For the analysis of this online problem we use the competitive ratio. It can be easily shown that the best possible competitive ratio is between (1 + sqrt(5)) / 2 = 1.618... and 2. We show better lower (1.632...) and upper (1.897...) bounds.   References:Bieńkowski et al., Collecting Weighted Items from a Dynamic Queue, SODA '09
 23.04.2009 Paweł Prałat Cleaning Regular Graphs with Brushes and Brooms A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most n(d+1)/4 brushes suffice, and prove that for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely n/4(d+o(d)).
 16.04.2009 Bartłomiej Bosek i Tomasz Krawczyk Coloring numbers of co-comparability graphs
 02.04.2009 Torsten Ueckerdt On Large Quadrant-Depth We consider a point set P of n points in the plane with no two points sharing the same x or y-coord. For any (a,b) in [0,1]x[0,1] a point p in P is called (a,b)-deep if there are two opposite quadrants Q1 and Q2 of p such that Q1 \cap P >= a*n and Q2 \ cap P >= b*n. Moreover the pair (a,b) is called feasible if every finite point set has an (a,b)-deep point. In this talk we present the set F of all feasible pairs (a,b).
 26.03.2009 Stefan Felsner Sampling from distributive lattices - the Markov chain approach
 19.03.2009 Edward Szczypka Thue games and the Lovasz local lemma
 12.03.2009 Edward Szczypka Local lemma strikes again
 05.03.2009 Jarosław Grytczuk Chips on graphs; five easy pieces Referat odbędzie się w sali 0089.
 26.02.2009 Maciej Ulas Experimental mathematics in action Wykład odbędzie się w sali 0089.
 15.01.2009 Andrzej Grzesik On a problem of chinese secretary
 08.01.2009 Wiktor Żelazny Some graph labeling results
 18.12.2008 Mateusz Michałek Cherries in the Tropics
 11.12.2008 Bartosz Walczak Schnyder trees and grid embeddings of planar graphs
 04.12.2008 Michał Lasoń On zero-sum problems
 27.11.2008 Jarosław Grytczuk Complexity and packing
 20.11.2008 Bartłomiej Bosek First fit algorithm for on-line chain partitioning problem On-line chain partititoning of orders can be viewed as the game between two-person between: Algorithm and Spoiler. The game is played in rounds. During each round Spoiler introduces a new point of an order with its comparability status to previously presented points while Algorithm gives it a color in such a way that the points with the same color form a chain. We consider the First Fit Algorithm (FFA) - it gives the first possible color to each introduced point. There is a relatively easy strategy for a Spoiler that forces FFA to use arbitrary many colors even on orders of width 2. We proved that if the game is played on orders of width w that do not contain k+k (two incomparable chains of height k) as subposet then FFA uses no more than 4kw^2 colors. Joint work with Tomasz Krawczyk and Edward Szczypka.
 13.11.2008 Jarosław Grytczuk Graph coloring games
 30.10.2008 Piotr Micek Efficient graph packing via game coloring Kierstead and Kostochka's abstract: The game coloring number gcol(G) of a graph G is the least k such that if two players take turns choosing the vertices of a graph then either of them can insure that every vertex has less than k neighbors chosen before it, regardless of what choices the other player makes. Clearly, gcol(G)<= DELTA(G)+1. Sauer and Spencer proved that if two graphs G_1 and G_2 on n vertices satisfy 2*DELTA(G_1)*DELTA(G_2)
 09.10.2008 Wiktor Żelazny Lucky labelings of graphs Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by L(G). Using algebraic methods we prove that L(G)≤k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that L(T)≤2 for every tree T, and L(G)≤3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that L(G)≤100 280245065 for every planar graph G. Nevertheless we offer a provocative conjecture that L(G)≤Chi(G) for every graph G.
 12.06.2008 Lech Duraj Interval chromatic number of planar graphs
 05.06.2008 Grzegorz Gutowski Bisection of colored trees
 29.05.2008 Artur Szymański (AGH) Strive for Photorealism - A Brief History of 3D Computer Graphics This will be a survey talk presenting a development of 3D computer graphics from its birth at MIT and UU in late 60' to present day. During this journey through time, we will outline a number of algorithms for shading and rendering (ray tracing, radiosity, photon mapping), as well as their application and influence on film industry.
 15.05.2008 Andrzej Holubowicz Reconstruction of sequences
 08.05.2008 Wiktor Żelazny Bisection of trees
 24.04.2008 Tomasz Schoen (UAM) On a problem of Konyagin
 10.04.2008 Piotr Szafruga On k-critical n-chromatic graphs
 27.03.2008 Jan Jeżabek Degree constraint subgraphs
 13.03.2008 Zofia Miechowicz (Zielona Góra) Rota's basis conjecture Suppose that each edge of the complete bipartite graph K_n,n is assigned arbitrarily a basis of the Euclidean n-dimensional vector space V. Is it true that we may choose one vector for each edge from its basis so that the vectors lying around each vertex formed a basis of V? The problem is due to Gian-Carlo Rota, a positive answer would be a far reaching strengthening of the famous Dinitz problem for latin squares. We will report on progress, modifications and intriguing connections of this fascinating conjecture.
 06.03.2008 Jan Jeżabek Four colors suffice to distinguish neighboors by multisets A proof of the following result will be presented: every connected graph with more than one edge has a 4-coloring of the edges such that no two adjacent vertices get the same multisets of colors. It is conjectured that the best possible constant is 3, even if colors are positive integers 1,2,3, and we wish to distinguish neighboors by sums rather than just multisets.
 21.01.2008 Sebastian Czerwiński (UZ) All the lonely runners
 14.01.2008 Karol Kosiński On the Parity of Exponents in the Factorization of n! It is shown that, for any k, there exist infinitely many positive integers n such that in the prime power factorization of n!, all first k primes appear to even exponents. This answers a question of Erdos and Graham ("Old and New Problems and Results in Combinatorial Number Theory", L'Enseignement Mathematique Imprimerie Kundia, Geneva, 1980). A few generalizations are provided as well.
 07.01.2008 Lech Duraj Solution of the Angel problem
 17.12.2007 Katarzyna Grygiel On the chromatic number and independence number of hypergraph products
 10.12.2007 Leszek Horwath Multicolored forests in bipartite decompositions of graphs
 03.12.2007 Grzegorz Gutowski Finding disjoint paths in expanders deterministically and online
 26.11.2007 Mikołaj Pudo Upper and lower bounds for satisfiability threshold The 3-SAT problem consists in determining if a boolean formula with 3 literals per clause is satisfiable. When the ratio between the number of clauses and the number of variables increases, a threshold phenomenon is observed: the probability of satisfiability appears in simulations to decrease sharply from 1 to 0 in the neighbourghood of a threshold value, conjectured to be close to 4.25. In my talk I will present approach to upper and lower bounds for the threshold's potential location based on urn models, and generating functions.
 19.11.2007 Filip Sokołowski Unprovability of the 3n+1-conjecture
 12.11.2007 Dawid Kopiec Piercing d-intervals
 05.11.2007 Andrzej Grzesik Solution of the EKG conjecture
 29.10.2007 Michał Zmarz Complexity of nonrepetitive colorings A coloring of a graph is "nonrepetitive" if no path contains two identical adjacent blocks. A resent result by Marx and Schaefer asserts that testing whether a given coloring is nonrepetitive is coNP-hard. However, if one restricts to blocks of length at most k then the problem becomes fixed-parameter tractable.
 22.10.2007 Wiktor Żelazny On graphs represented by colored intervals
 15.10.2007 Maciej Chociej A randomised scheme for geometrical algorithms An abstract, randomised scheme for structure creating algorithms can be used in solving many geometrical problems. One of those is obtaining a Delaunay triangulation of a given set of points. For a set P of points in a d-dimensional Euclidean space a Delaunay triangulation is a triangulation T(P) such that no point in P is inside the circum-hypersphere of any simplex in T(P). The general scheme and an exemplary Delaunay triangulation algorithm shall be presented with some foreword on other applications of the scheme and derandomization of resulting algorithms.
 08.10.2007 Jarek Grytczuk Invisible runners in finite fields I will present some results on the Lonely Runner Problem in a setting of finite fields, discuss connections to graph coloring, matroid flows, and view obstruction, and offer several new open problems.
 12.06.2007 Arkadiusz Pawlik Tverberg's theorem
 12.06.2007 Bartosz Walczak Two theorems of Schnyder
 15.05.2007 Andrzej Ruciński (UAM) Perfect matchings in uniform hypergraphs I will present a recent result, jointly with Rodl and Szemeredi, establsihing an exact degree threshold for the existence of a perfect matching in a $k$-uniform hypergraph. Some algorithmic aspects of this problem will be discussed in the lecture by Edyta Szymanska, next day on TCS seminar.
 08.05.2007 Jan Jeżabek Solution of the Stanley-Wilf conjecture
 08.05.2007 Tomasz Jurkiewicz Aztec Diamond Theorem
 17.04.2007 Maciej Adamczyk Huffman coding
 17.04.2007 Michał Staromiejski On a theorem of Hasse
 27.03.2007 Lech Duraj Elusive graph properties Let P be a fixed property of graphs (planarity, 3-colorability, connectedness, etc.). The following game is played by two players (Adam and Eve) on the vertex set V = {1,2,...,n}. In one round Adam asks a question of the form: "is there an edge between i and j?", and Eve answers: "yes" or "no". Adam's goal is to learn as quickly as possible whether the constructed graph will have property P, or not. Eve wants to keep Adam in uncertainty until the very last question. In this case she is a winner and property P is called "elusive". The main conjecture states that every non-trivial monotone graph property is elusive. The most impressive result so far confirms the conjecture when n is a prime power. The proof uses topological arguments.   References:A. Björner, Topological methods. Handbook of combinatorics, Vol. 1, 2, 1819--1872, Elsevier, Amsterdam, 1995.
 27.03.2007 Jarek Grytczuk Diophantine approximation, graph coloring, and the lonely runner problem Suppose n runners are running with constant speeds around a circle of circumference 1. A runner is "lonely" at moment t if there are no other runners within a circular distance 1/n from his/her actual position. Is it true that for every set of n different speeds a lonely runner always appears? This innocently looking question is open for more than six runners and has some intriguing connections to diophantine approximation and graph coloring.
 06.03.2007 Paweł Walter Splitting Necklaces Two thieves stolen a necklace with even number of beads in each of r colors. They want to split it so that each of them could get the same number of beads in each color. How many cuts are needed in the worst case? Clearly, if the necklace is open and beads in one color form a segment then r cuts are necessary. Curiously, this number is always sufficient, as can be proved using the Borsuk-Ulam theorem. The problem has continuous and multiple versions for which topological method is also applied.
 18.01.2007 Grzegorz Gutowski Kneser's Conjecture Let G(n,k) denotes a graph whose vertices are k-element subsets of {1,2,...,n}, with two vertices adjacent iff they are disjoint. It is easy to see that G(n,k) is (n-2k+2)-colorable, and Kneser conjectured that actually that many colors are needed. The conjecture was proved by Lovasz by using topological methods. A simple proof based on the Borsuk-Ulam theorem, found later by Barany, will be presented.
 17.01.2007 Jarosław Grytczuk Combinatorial applications of the Borsuk-Ulam theorem A set S of 3n points in general position (no four on a plane) is given in 3-dimensional space. Suppose the points are colored red, blue, and green so that there are exactly n points in each color. Can we partition the set S into n triangles so that 1) each triangle is multicolored (i.e. no two of its vertices have the same color), 2) no two triangles (considered as convex hulls of their vertices) intersect? The answer is yes, but the only known proof of this fact uses topological argument - the famous Borsuk-Ulam theorem, known also as the Ham Sandwich Theorem. We will present more of such unexpected applications of topology in combinatorics.   References:A. Björner, Topological methods. Handbook of combinatorics, Vol. 1, 2, 1819--1872, Elsevier, Amsterdam, 1995.Alon, Noga Nonconstructive proofs in combinatorics. Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990), 1421--1429, Math. Soc. Japan, Tokyo, 1991.
 20.12.2006 Jarek Grytczuk Games and sequences This will be a survey talk presenting a collection of open problems on combinatorial games and integer sequences.
 14.12.2006 Lech Duraj Firing chips on graphs Suppose each vertex v of a graph G is assigned with some number of chips c(v). If c(v) is at least the degree of v then v can be "fired", and in effect each neighbor of v will receive one chip from v. In this way initial configuration of chips evolves and may eventually reach a stable form in which no vertex can be fired. Many natural question can be asked: which configurations are eventually stable? How long it may take to reach a stable configuration? What properties has a (naturally defined) poset of configurations?
 13.12.2006 Przemysław Broniek Ranking tournaments For a given digraph D, let f(D) be the minimum number of edges whose reversal or removal turns D into an acyclic digraph. It was known for over thirty years that the problem of determining f(D) is NP-hard. Recently Noga Alon proved that it is NP-hard even for tournaments (that is complete oriented graphs). The proof makes use of the previous fact and pseudorandom properties of Paley tournaments.   References:N. Alon, Ranking tournaments, SIAM J. Discrete Math. 20 (2006), 137-142.
 30.11.2006 Andrzej Pezarski Chip firing games A pile of n chips occupies a vertex v of a long path. In one move of the game we split the pile into two equal parts and place them into neighbors of v (leaving one chip at v if n was odd). We repeat this move, each time choosing a vertex to be "fired" arbitrarily. The game ends if there is at most one chip on every vertex. Is it true that we always end with a stable configuration of chips? There are many variants of the game leading to iteresting and deep mathematical concepts.   References:A. Björner, L. Lovász, P.W. Shor, Chip-firing game on graphs, European J. Combin. 12 (1991) 283--291.A. Björner, L. Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992), no. 4, 305--328.G. Tardos, Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math. 1 (1988), no. 3, 397--398.R. Anderson, L. Lovász, P. Shor, J. Spencer, E. Tardos, and S. Winograd, Disks, balls, and walls: Analysis of a combinatorial game, Amer. Math. Monthly 96 (1989), pp. 481-- 493.
 29.11.2006 Piotr Micek Dice, boxes, and majority tournaments Suppose we have 2k-1 linear orders of a finite set V. A k-majority tournament T on V is defined so that u dominates v in T iff u lies above v in more than a half of the orders. Let F(k) be the maximum over all k-majority tournaments T of the size of a minimum dominating sets of T. Using geometric arguments, it can be proved that F(k) is finite for every k. For instance, it is not hard to show that F(2)=3, but this is the last exact value of F(k) determined so far.   References:N. Alon, G. Brightwell, H. A. Kierstead, A. V. Kostochka, P. Winkler, Dominating sets in k-majority tournaments, J. Combin. Theory (ser. B), 96 (2006), 374-387.
 23.11.2006 Piotr Micek Trees, tournaments, and the Second Neighborhood Conjecture The second neighborhood conjecture states that every directed graph has a vertex v such that the number of vertices that can be reached from v by exactly two jumps (but not in one jump) along directed edges is at least as the number of its out-neighbors. Most probably this is true, but nobody could prove it, as yet. A simple proof will be presented that the conjecture holds for tournaments.
 22.11.2006 Jarosław Grytczuk The permanent lemma Let A be a square matrix of size n. The permanent lemma asserts that if per(A) is non-zero, then there is a vector X, whose components can be chosen from any prescribed sets of size 2, such that the vector AX is nowhere zero. This looks somewhat technical, but there are many combinatorial problems that can be expressed in this way. For instance, one can show that nonvanishing of permanents of certain matrices is equivalent to the Four Color Theorem.
 09.11.2006 Jarosław Grytczuk 123-conjecture Let G be a connected graph with at least three vertices. Suppose we assign one of the integers 1, 2, or 3 to each edge of G. In this way each vertex v in G obtains the sum of numbers lying on the edges incident to v. Such an assignment is proper if no two adjacent vertices have the same sum. Can we always do a proper assignment using just three numbers 1, 2, and 3? It is known that this can be done using 1, 2, …, 16, and that for almost every graph G, only 1 and 2 are sufficient. There are many related open questions.
 08.11.2006 Jarosław Grytczuk Nonrepetitive colorings of graphs A coloring of the vertices of a graph G is nonrepetitive if one cannot find a color pattern of the form AA on any simple path of G, where A is any sequence of colors. The minimum number of colors needed is the Thue chromatic number of G, denoted by T(G). It is known that T(G) is bounded for graphs of bounded maximum degree, bounded treewidth, and for graphs with forbidden planar minor. The major open problem is whether there exists a finite constant N (no matter how huge) such that T(G) is at most N for every planar graph G. There are lots of unexpected connections to other chromatic parameters, as well as plenty of related unsolved questions. (Joint work with Noga Alon)