Algorithmics Research Group

Theoretical Computer Science
Faculty of Mathematics and Computer Science
Jagiellonian University

Algorithmic Aspects of Combinatorics Seminar

Thursday: 16:15 - 18:00, room 117

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

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: www-tcs@tcs.uj.edu.pl