Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus
 
 
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 Dzido
    UG 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 Li
    Universite 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ński
    UG 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)<n then they pack, i.e., there is an embedding of G_1 into the complement of G_2. we improve this by showing that if (gcol(G_1)-1)*DELTA(G_2)+(gcol(G_2)-1)*DELTA(G_1)<n then G_1 and G_2 pack. To our knowledge this is the first application of coloring games to a non-game problem.  
    references:
  • H.A. Kierstead, A.V. Kostochka, Efficient graph packing via game coloring
  • 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)  
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl