[an error occurred while processing this directive]

# Kombinatorický seminář

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.

## Program

 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

## Články k referování

### Volné články

• 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(n3/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(n2). 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 sn be the side of the smallest square in to which it is possible pack n unit squares. We show that s10 = 3.707 and that s11 >= 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."

### Zamluvené články

• 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 Hd, that D(Hd)=3 if d in {2,3} and D(Hd)=2 if d geq 4. It is also shown that D(Hd2)=4 for d in {2,3} and D(Hd2)=2 for d geq 4, where Hd2 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 .

• 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 T2 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 T2 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 (V1,V2) in a graph G together with colorings of V1 and V2, what is the least number of colors in a coloring of G which ''respects'' the colorings of V1 and V2?

• 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 R2 whose center is the origin. It is proved that if none of the elements a1, a2, a3 in R2 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 n2/12 + o(n2). 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 n2/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.

## Historie semináře

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