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

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.

Konferencja Studencka na AGH
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.

Barłomiej Bosek
Coloring shift-chain hypergraphs
Jarosław Grytczuk
On some graph coloring problems
Wojciech Samotij
Tel Aviv University
How does a typical finite metric space look like?
Jarosław Grytczuk
On some problems in combinatorial number theory
Michał Farnik
Jagiellonian University
Hat guessing game on sparse graphs
Steven Chaplick, Universitat Wurzburg
Intersection Graphs of Non-crossing Paths
Grzegorz Bukowiec
Thue Games
Gabriel Jakóbczak
Additive chromatic number of several graph families
Jarosław Grytczuk
Pattern avoiding coloring of the plane
Jarosław Grytczuk
Higher order arboricity of graphs
Patryk Mikos
Complexity of GKS communication game
Jarosław Grytczuk
Coloring graphs with many colors on cycles
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.
Mateusz Michałek
IM PAN, Warszawa, Freie Universitaet, Berlin
Tensors and algorithms for matrix multiplication
Jarosław Grytczuk
The Log-rank Conjecture
Jarosław Grytczuk
Localization games on graphs II
Jarosław Grytczuk
Localization games on graphs
Adam Polak
The Evasiveness Conjecture II
Adam Polak
The Evasiveness Conjecture I
Adam Gągol
Jagiellonian University
On the Lonely Runner Problem II
Adam Gągol
On the Lonely Runner Problem I
Gabriel Jakóbczak
The chromatic number of the plane
Jarosław Grytczuk
The Sensitivity Conjecture
Adam Polak
Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
Teodor Jerzak
Buffon's needle
Grzegorz Gutowski
Avoiding Facial Repetitions
Jakub Cieśla
Hat Guessing Games
Jarosław Grytczuk
Ramsey Theory on the Integers
Jarosław Grytczuk
Problems and results in combinatorial number theory
Grzegorz Guśpiel
Homomorphisms of Edge-coloured Graphs
Piotr Kawałek
Monotone broadcast digraphs
Patryk Mikos
A hats game puzzle and generalized covers
Dorota Kapturkiewicz
Monotone paths in bounded degree graphs
Michał Seweryn
Multiple intersection of set systems
Adam Gągol
Ternary pattern avoidance in partial words
Wojciech Lubawski
On-line arboricity of graphs
Piotr Szafruga
Coloring unit disk graphs
Jarosław Grytczuk
Nonrepetitive coloring of the plane
Maciej Gawron
Twins in Words and Permutations
Wojciech Lubawski
Rota basis conjecture for sparse paving matroids
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.  
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.  
Michał Masłowski
Maximizing the number of nonnegative subsets
Grzegorz Guśpiel
Block partitions of sequences
Grzegorz Gutowski
Coloring 3-colorable graphs on-line
Adam Gągol
Application of probabilistic method in some colourings of bounded path-width graphs
Michał Zmarz
Playing nonrepetitive games
Karol Kosiński
A generalization of Thue freeness for partial words
Jaroslaw Grytczuk
Three variations on the theme of Szemeredi
Marcin Dziaduś
Coloring intersection graphs of pseudo-discs
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.  
Andrzej Dorobisz
The game Grundy number of graphs
Wojciech Lubawski
Delay colorings of matroids
21.11.2013,Grzegorz Gutowski
The weak 3-flow conjecture and the weak circular flow conjecture
Robert Obryk
Network routing as a multiparty game with asynchronous moves
Karol Kosiński
On some properties of (strongly) non-repetitive sequences
Wiktor Kuropatwa
Distortion-colouring of cubic bipartite multigraphs
Jakub Kozik
Random Greedy Coloring of Uniform Hypergraphs
Dawid Ireno
The Cinderella Game on Holes and Anti-holes
Jarosław Grytczuk
Fractions, Continued and Egyptian
I will present some problems and results on continued fractions and Egyptian fractions.  
Jakub Brzeski
The universal and canonically colored sequences
Marcin Dziaduś
The Caccetta-Haggkvist Conjecture and Additive Number Theory
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.  
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.  
Piotr Wójcik
On algebraic invariants of geometric graphs; the Colin de Verdiere number.
Michał Lasoń
New challenges in Matroid Theory
Michał Sapalski
Oblivious Collaboration
Szymon Borak
Domination Game
Robert Obryk
Topological structure of asynchronous computability
Grzegorz Gutowski
Nonrepetitive colourings of planar graphs with O(log n) colours
Bartosz Zaleski (UAM)
The Neighbourhood Conjecture
Grzegorz Gutowski
The List Coloring Conjecture for planar graphs
Jarosław Grytczuk
Perspectives in the Online Ramsey Theory
Maciej Kalkowski (UAM)
Irregularity strength in distributed model
Jarek Grytczuk
Strong chromatic index of graphs
Paweł Wanat
The seating couples problem
Jarosław Grytczuk
Old and new challenges in Thue theory
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 :)  
[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
Michał Sapalski
Finding minimum-weight (undirected) spanning tree for process networks
Agnieszka Łupińska
On square-free permutations
Agnieszka Paszek
Zen puzzle garden is NP-complete
Jarosław Grytczuk
Lonely runner graphs
Adam Polak
Distributed graph coloring II
Adam Polak
Distributed graph coloring
Robert Obryk
A near-optimal cardinality estimation algorithm
Andrzej Pezarski
On-line clique covering of interval graphs II
Andrzej Pezarski
On-line clique covering of interval graphs
Jarosław Grytczuk
Coloring problems for graphs and matroids
Bartłomiej Bosek
Coloring gcd-graphs
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.  
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.  
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:  
Paweł Dłotko
Forman's discrete Morse theory + applications
Andrzej Kisielewicz, Krzysztof Przesławski (UZ)
On the structure of tilings of Euclidean space by unit cubes -- around (disproved) Keller's conjecture
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.  
Jakub Przybyło (AGH)
Can colour-blind distinguish three-colour pallets? Yes they can!
SeminariumAAK 05.04.2012
Piotr Skowron (UW)
Selective complexity issues of elections
Paweł Petecki
Hamiltonian decompositions of k-uniform hypergraphs
Arkadiusz Pawlik
Coloring intersection graphs of segments in the plane
Paweł Petecki
Hamiltonian decompositions of k-uniform hypergraphs
Zbigniew Lonc (PW)
Constructions of asymptotically shortest k-radius sequences
Monika Pilśniak (AGH)
Graph coloring for color blind persons
Jarosław Grytczuk
Multidimensional necklace splitting
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.  
Piotr Micek
Choice number versus its on-line counterpart
SeminariumAAK 24.11.2011
Grzegorz Gutowski
On-line choice number
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.  
Arkadiusz Pawlik
On the Albertson Crossing Conjecture
Andrzej Grzesik
Flag algebras for beginners
SeminariumAAK 20.10.2011
Wiktor Żelazny
Fictional coloring of graphs
Jarosław Grytczuk
Lucky labelings of planar graphs
Jakub Przybyło (AGH)
Proper edge colourings with different color paletts on adjacent vertices - algorithms based on Combinatorial Nullstellensatz
Paweł Rzążewski (Politechnika Warszawska)
Exact algorithms for L(2,1)-coloring problem
Paweł Petecki (AGH)
Grasshopper jumping in both directions
Marek Grabowski (UW)
Nowhere 0 mod p graph colorings
Wiktor Żelazny
More on additive colorings of graphs
A. Nilli
On the chromatic number of random Cayley graphs
Marek Markiewicz
On the recursive sequence of Ulas
SeminariumAAK 14.04.2011
Jarosław Grytczuk
How to color a graph
Jarosław Grytczuk
Random runners are very lonely
SeminariumAAK 24.03.2011
Michał Lasoń
Mr. Paint and Mrs. Correct are doing it on matroids
Przemysław Mazur
Multiple recurrence and arithmetic progressions
Michał Farnik
Cuts, Graphons, and Szemeredi Regularity Lemma
Michał Farnik
Graphons, cut norm, and distance
SeminariumAAK 20.01.2011
Marcin Witkowski
Nonrepetitive sequences up to (mod k)
Arkadiusz Pawlik
Coloring geometric intersection graphs
Michał Zmarz
Graph layouts and nonrepetitive colorings
Leszek Horwath
On-line conflict-free coloring of intervals
Piotr Szafruga
On-line nonrepetitive games
Marek Adrian
Covering systems of congruences; an application of the number-theoretic local lemma
Grzegorz Gutowski
Fractional list coloring of graphs
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.  

Canceled due to Jarosław Duda's PhD defence

Open problem ob-session
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.  
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.  
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.  

Zofia Miechowicz
University of Grunberg
Game chromatic number of Cartesian product graphs
Leszek Horwath
Online preemptive weighted scheduling
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.  
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
SeminariumAAK 15.04.2010
In view of an alternative event:,cntnt01,detail,0&cntnt01articleid=37&cntnt01returnid=92&hl=pol  
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.  
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.  
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.  
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.  
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.  
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.  
Jarosław Grytczuk
Big-line-big-clique conjecture
Jarosław Grytczuk
My favorite four color problems
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.  
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.  
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.  
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.  
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.  
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.  
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.  
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.  
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.  
Mateusz Michałek
Counting homologies
Jarek Grytczuk
Mr. Paint and Mrs. Correct
Andrzej RucińskiUAM Poznań
2nd Discrete Integration Meeting & SSAK
Kampus AGH, budynek B7, sala 1.9, godzina 16:00.  
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.  
Bieńkowski et al., Collecting Weighted Items from a Dynamic Queue, SODA '09
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)).  
Bartłomiej Bosek i Tomasz Krawczyk
Coloring numbers of co-comparability graphs
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).  
Stefan Felsner
Sampling from distributive lattices - the Markov chain approach
Edward Szczypka
Thue games and the Lovasz local lemma
Edward Szczypka
Local lemma strikes again
Jarosław Grytczuk
Chips on graphs; five easy pieces
Referat odbędzie się w sali 0089.  
Maciej Ulas
Experimental mathematics in action
Wykład odbędzie się w sali 0089.  
Andrzej Grzesik
On a problem of chinese secretary
Wiktor Żelazny
Some graph labeling results
Mateusz Michałek
Cherries in the Tropics
Bartosz Walczak
Schnyder trees and grid embeddings of planar graphs
Michał Lasoń
On zero-sum problems
Jarosław Grytczuk
Complexity and packing
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.  
Jarosław Grytczuk
Graph coloring games
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.  
H.A. Kierstead, A.V. Kostochka, Efficient graph packing via game coloring
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.  
Lech Duraj
Interval chromatic number of planar graphs
Grzegorz Gutowski
Bisection of colored trees
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.  
Andrzej Holubowicz
Reconstruction of sequences
Wiktor Żelazny
Bisection of trees
Tomasz Schoen (UAM)
On a problem of Konyagin
Piotr Szafruga
On k-critical n-chromatic graphs
Jan Jeżabek
Degree constraint subgraphs
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.  
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.  
Sebastian Czerwiński (UZ)
All the lonely runners
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.  
Lech Duraj
Solution of the Angel problem
Katarzyna Grygiel
On the chromatic number and independence number of hypergraph products
Leszek Horwath
Multicolored forests in bipartite decompositions of graphs
Grzegorz Gutowski
Finding disjoint paths in expanders deterministically and online
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.  
Filip Sokołowski
Unprovability of the 3n+1-conjecture
Dawid Kopiec
Piercing d-intervals
Andrzej Grzesik
Solution of the EKG conjecture
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.  
Wiktor Żelazny
On graphs represented by colored intervals
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.  
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.  
Arkadiusz Pawlik
Tverberg's theorem
Bartosz Walczak
Two theorems of Schnyder
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.  
Jan Jeżabek
Solution of the Stanley-Wilf conjecture
Tomasz Jurkiewicz
Aztec Diamond Theorem
Maciej Adamczyk
Huffman coding
Michał Staromiejski
On a theorem of Hasse
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.  
A. Björner, Topological methods. Handbook of combinatorics, Vol. 1, 2, 1819--1872, Elsevier, Amsterdam, 1995.
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.  
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.  
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.  
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.  
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.
Jarek Grytczuk
Games and sequences
This will be a survey talk presenting a collection of open problems on combinatorial games and integer sequences.  
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?  
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.  
N. Alon, Ranking tournaments, SIAM J. Discrete Math. 20 (2006), 137-142.
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.  
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.
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.  
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.
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.  
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.  
Jarosław Grytczuk
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.  
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)