Theoretical Computer Science Faculty of Mathematics and Computer Science Jagiellonian University

 Algorithmics Research Group

 Algorithmic aspects of combinatorics Seminar Thursday: 16:15 - 18:00, room 0174 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”. table edited by: Jarosław Grytczuk
 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 [1], 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 [2]. 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:[1] Piotr Micek, Bartosz Walczak, A graph-grabbing game, Combinatorics, Probability and Computing 20 (2011), 623-629[2] 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 Paszek Zen puzzle garden is NP-complete 06.12.2012,Agnieszka Łupińska On square-free permutations 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 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 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 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 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 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 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 Szabo Freie 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 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 Szczechla Warsaw 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 Pegden Rutgers 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 Nikodem AGH 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ński UAM 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)

webmaster: