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 |
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].
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.
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.
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.
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."
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.
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."
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.
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].
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.
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.
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
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?
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.
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.
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]