V zimním semestru 2004/2005 se seminář koná pravidelně (modulo svátky) v pátek od 12:55 v posluchárně S7. Seminář vedou Martin Mareš a Robert Šámal.

Kombinatorický seminář (DMI022)
je seminář pro studenty 2.-5. ročníku, zaměřený na řešení jednoduchých (ale
často dosud nevyřešených) úloh z kombinatoriky a příbuzných oborů, jako je
třeba teorie grafů a kombinatorická geometrie. Podstatnou součástí semináře je
rovněž četba a referování odborných článků účastníky semináře. Každoročně je
pro studenty Kombinatorického semináře pořádána **Jarní
škola kombinatoriky**.

8. 10. | úvodní seminář, rozdávání článků etc. | |

15. 10. | Eva Ondráčková | Trojúhelníky v grafu a jeho doplňku |

22. 10. | Jan Kadlec | Golayovy a jiné kódy |

29. 10. | Martin Cetkovský | Improved bounds for the chromatic number of a graph |

5. 11. | Tomáš Valla | Sokoban is PSPACE-complete |

12. 11. | Josef Cibulka | A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. |

19. 11. | Jan Hladký | Fisher's Theorem. |

26. 11. | Alexandr Kazda | Rozlišující číslo hyperkrychlí |

3. 12. | Jan Kynčl | Separating thickness from geometric thickness |

10. 12. | Marek Tesař | McKay et al: Acyclic digraphs and eigenvalues of (0,1)-matrices. a možná i další |

17. 12. | Vánoční | seminář |

7. 1. | Martin Tancer | O L(2,1)-obarvení, ostrovech a dírách |

- Vida Dujmović
and David R. Wood.
Three-dimensional grid drawings with sub-quadratic volume.
In Towards a theory of geometric graphs, volume 342 of
Contemp. Math., pages 55–66. Amer. Math. Soc., Providence, RI,
2004.
(PostScript, 12 pages, 223991 bytes)
A three-dimensional grid drawing of a graph is a placement of the vertices at distinct points with integer coordinates, such that the straight line-segments representing the edges are pairwise non-crossing. A O(n

^{3/2}) volume bound is proved for three-dimensional grid drawings of graphs with bounded degree, graphs with bounded genus, and graphs with no bounded complete graph as a minor. The previous best bound for these graph families was O(n^{2}). These results (partially) solve open problems due to Pach, Thiele, and Toth [Graph Drawing 1997] and Felsner, Liotta, and Wismath [Graph Drawing 2001]. - Edita Ričanyová and
Martin Škoviera.
Fano colourings of cubic graphs and the fulkerson conjecture.
(PDF, 154249 bytes)
A Fano colouring is a colouring of the edges of a cubic graph by points of the Fano plane such that the colours of any three mutually adjacent edges form a line of the Fano plane. It has recently been shown by Holroyd and Skoviera (J. Combin. Theory Ser. B, to appear) that a cubic graph has a Fano colouring if and only if it is bridgeless. In this paper we prove that six, and conjecture that four, lines of the Fano plane are sufficient to colour any bridgeless cubic graph. We establish connections of our conjecture to other conjectures concerning bridgeless cubic graphs, in particular to the well-known conjecture of Fulkerson about the existence of a double covering by 1-factors in every bridgeless cubic graph.

- Walter Stromquist.
Packing 10 or 11 unit squares in a square.
Electron. J. Combin., 10, 2003.
(PostScript, 11 pages, 2869549 bytes)
Let s

_{n}be the side of the smallest square in to which it is possible pack n unit squares. We show that s_{10}= 3.707 and that s_{11}>= 3.789. We also show that an optimal packing of 11 unit squares with orientations limited to 0 or 45 degrees has side 3.886. These results prove Martin Gardner's conjecture that n = 11 is the first case in which an optimal result requires a non-45 packing. - Umesh Vazirani.
Gabber-galil expander construction.
(PostScript, 6 pages, 77103 bytes)
Expanders have a wide variety of uses in theoretical computer science. Most notably, they have been used to create spectacular pseudorandom generators. It is not difficult to demonstrate that expanders exist by a counting argument (i.e., the probabilistic method). Our goal today is to give an explicit construction, due to Gabber and Galil.

- Rui Xu and Cun-Quan
Zhang.
Nowhere-zero 3-flows in squares of graphs.
Electron. J. Combin., 10:Research Paper 5, 8 pp. (electronic),
2003.
(PostScript, 8 pages, 192218 bytes)
Summary: "It was conjectured by Tutte that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we give a complete characterization of graphs whose squares admit nowhere-zero 3-flows and thus confirm Tutte's 3-flow conjecture for the family of squares of graphs."

- Maria
Axenovich and Dmitri Fon-Der-Flaass.
On rainbow arithmetic progressions.
Electron. J. Combin., 11:Research Paper 1, 7 pp. (electronic),
2004.
(zamluveno pro Maroše Vrance).
(PostScript, 7 pages, 153737 bytes)
Consider natural numbers {1, dots ,n } colored in three colors. We prove that if each color appears on at least (n + 4)/6 numbers then there is a three-term arithmetic progression whose elements are colored in distinct colors. This variation on the theme of Van der Waerden s theorem proves the conjecture of Jungic et al.

- Bill Bogstad and
Lenore J. Cowen.
The distinguishing number of the hypercube.
Discrete Math., 283(1-3):29–35, 2004.
(zamluveno pro Sašu Kazdu).
(PDF, 212111 bytes)
Summary: "The distinguishing number of a graph G is the minimum number of colors for which there exists an assignment of colors to the vertices of G so that the group of color-preserving automorphisms of G consists only of the identity. It is shown, for the d-dimensional hypercubic graphs H

_{d}, that D(H_{d})=3 if d in {2,3} and D(H_{d})=2 if d geq 4. It is also shown that D(H_{d}^{2})=4 for d in {2,3} and D(H_{d}^{2})=2 for d geq 4, where H_{d}^{2}denotes the square of the d-dimensional hypercube. This solves the distinguishing number for hypercubic graphs and their squares." - Derek G. Corneil.
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs.
Discrete Appl. Math., 138(3):371–379, 2004.
(zamluveno pro Josefa Cibulku).
(PDF, 214806 bytes)
A unit interval graph (uig) is a graph whose vertices can be put in one-to-one correspondence with unit length intervals of the real line such that two vertices are adjacent if and only if the corresponding intervals intersect. It is known that a graph is uig if and only if there is an ordering of the vertex set such that the closed neighborhood of any vertex is consecutive. Using this characterization the author presents a simple linear time algorithm for uig recognition. In comparison with the known linear time algorithms for the latter problem the proposed algorithm is very simple to implement. The main part of the algorithm consists in one call of the Lexicographical Breadth First Search procedure and two calls of a special variant of it.

- Joseph
Culberson.
Sokoban is
PSPACE-complete.
(zamluveno pro Toma Vallu).
It is shown that the popular puzzle Sokoban can be used to emulate a linear bounded automata (finite tape Turing Machine (TM)). In particular, a construction is given that has a solution if and only if the corresponding Turing Machine on its input halts in the accept state. Further, if the TM halts and accepts, then the pusher will make Θ(n+t(n)) moves and pushes, where n is the number of symbols on the input tape, and t(n) is the number of transitions made by the TM during its computation. This construction shows that the puzzles are PSPACE-complete, solving the open problem stated in [1].

- Anna de Mier and
Marc Noy.
A solution to the tennis ball problem.
(zamluveno pro Honzu Hladkého).
(PostScript, 9 pages, 168838 bytes)
We present a complete solution to the so-called tennis ball problem, which is equivalent to counting lattice paths in the plane that use North and East steps and lie between certain boundaries. The solution takes the form of explicit expressions for the corresponding generating functions. Our method is based on the properties of Tutte polynomials of matroids associated to lattice paths. We also show how the same method provides a solution to a wide generalization of the problem.

- David Eppstein.
Separating thickness from geometric thickness.
In Towards a theory of geometric graphs, volume 342 of
Contemp. Math., pages 75–86. Amer. Math. Soc., Providence, RI,
2004.
(zamluveno pro Honzu Kynčla).
(PostScript, 12 pages, 219928 bytes)
We show that graph-theoretic thickness and geometric thickness are not asymptotically equivalent: for every t, there exists a graph with thickness three and geometric thickness at least t.

- David C. Fisher.
Squaring a tournament: a proof of Dean's conjecture.
J. Graph Theory, 23(1):43–48, 1996.
(zamluveno pro Mareka Tesaře).
(PDF, 967260 bytes)
The square of a tournament T is the digraph T

^{2}obtained by adding arcs between pairs of nodes of directed distance two. The author proves the following conjecture of N. Dean: Every tournament T has a node whose outdegree in T^{2}is at least twice that in T. Reviewed by K. Jay Bagga - S. Louis
Hakimi and Edward F. Schmeichel.
Improved bounds for the chromatic number of a graph.
J. Graph Theory, 47:217–225, 2004.
(zamluveno pro Martina Cetkovského).
(PDF, 99568 bytes)
Given an edge-cut (V

_{1},V_{2}) in a graph G together with colorings of V_{1}and V_{2}, what is the least number of colors in a coloring of G which ''respects'' the colorings of V_{1}and V_{2}? - Gyula O. H. Katona,
Richard Mayer, and Wojbor A. Woyczynski.
Length of sums in a Minkowski space.
In Towards a theory of geometric graphs, volume 342 of
Contemp. Math., pages 113–118. Amer. Math. Soc., Providence,
RI, 2004.
(zamluveno pro Michala Zerolu).
(PDF, 293413 bytes)
Let C be a centrally symmetric compact convex body in R

^{2}whose center is the origin. It is proved that if none of the elements a_{1}, a_{2}, a_{3}in R^{2}are inside C then not all the sums ai + aj (i ne j) can be inside C. - Peter Keevash and
Benny Sudakov.
Packing triangles in a graph and its complement.
J Graph Theory, 47:203–216, 2004.
(zamluveno pro Evu Ondráčkovou).
(PDF, 129937 bytes)
How few edge-disjoint triangles can there be in a graph G on n vertices and in its complement G? This question was posed by P. Erdos, who noticed that if G is a disjoint union of two complete graphs of order n/2 then this number is n

^{2}/12 + o(n^{2}). Erdos conjectured that any other graph with n vertices together with its complement should also contain at least that many edge-disjoint triangles. In this paper, we show how to use a fractional relaxation of the above problem to prove that for every graph G of order n, the total number of edge-disjoint triangles contained in G and G is at least n^{2}/13 for all sufficiently large n. This bound improves some earlier results. We discuss a few related questions as well. - Brendan D. McKay,
Frédérique E. Oggier, Gordon F. Royle, N. J. A. Sloane, Ian M.
Wanless, and Herbert S. Wilf.
Acyclic digraphs and eigenvalues of (0,1)-matrices.
J. Integer Seq., 7(3):Article 04.3.3, 5 pp. (electronic), 2004.
(zamluveno pro Mareka Tesaře).
Ukazuje se, že každá (0,1) matice mající kladná reálná vlastní čísla jednoznačně určuje acyklický orientovaný graf.

Kombinatorický seminář 2002-2003 [an error occurred while processing this directive]