 |
Discrete Mathematics & Theoretical Computer Science |
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
1. Distance graphs with maximum chromatic number
Let $D$ be a finite set of integers. The distance graph $G(D)$ has the set of integers as vertices and two vertices at distance $d ∈D$ are adjacent in $G(D)$. A conjecture of Xuding Zhu states that if the chromatic number of $G (D)$ achieves its maximum value $|D|+1$ then the graph has a clique of order $|D|$. We prove that the chromatic number of a distance graph with $D=\{ a,b,c,d\}$ is five if and only if either $D=\{1,2,3,4k\}$ or $D=\{ a,b,a+b,a+2b\}$ with $a \equiv 0 (mod 2)$ and $b \equiv 1 (mod 2)$. This confirms Zhu's conjecture for $|D|=4$.
Section:
Proceedings
2. Crooked Maps in Finite Fields
We consider the maps $f:\mathbb{F}_{2^n} →\mathbb{F}_{2^n}$ with the property that the set $\{ f(x+a)+ f(x): x ∈F_{2^n}\}$ is a hyperplane or a complement of hyperplane for every $a ∈\mathbb{F}_{2^n}^*$. The main goal of the talk is to show that almost all maps $f(x) = Σ_{b ∈B}c_b(x+b)^d$, where $B ⊂\mathbb{F}_{2^n}$ and $Σ_{b ∈B}c_b ≠0$, are not of that type. In particular, the only such power maps have exponents $2^i+2^j$ with $gcd(n, i-j)=1$. We give also a geometrical characterization of this maps.
Section:
Proceedings
3. Matroid matching with Dilworth truncation
Let $H=(V,E)$ be a hypergraph and let $k≥ 1$ and$ l≥ 0$ be fixed integers. Let $\mathcal{M}$ be the matroid with ground-set $E s.t. a$ set $F⊆E$ is independent if and only if each $X⊆V$ with $k|X|-l≥ 0$ spans at most $k|X|-l$ hyperedges of $F$. We prove that if $H$ is dense enough, then $\mathcal{M}$ satisfies the double circuit property, thus the min-max formula of Dress and Lovász on the maximum matroid matching holds for $\mathcal{M}$ . Our result implies the Berge-Tutte formula on the maximum matching of graphs $(k=1, l=0)$, generalizes Lovász' graphic matroid (cycle matroid) matching formula to hypergraphs $(k=l=1)$ and gives a min-max formula for the maximum matroid matching in the 2-dimensional rigidity matroid $(k=2, l=3)$.
Section:
Proceedings
4. Pebble Game Algorithms and (k,l)-Sparse Graphs
A multi-graph $G$ on n vertices is $(k,l)$-sparse if every subset of $n'≤n$ vertices spans at most $kn'-l$ edges, $0 ≤l < 2k$. $G$ is tight if, in addition, it has exactly $kn - l$ edges. We characterize $(k,l)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,l)$-pebble games. As applications, we use the pebble games for computing components (maximal tight subgraphs) in sparse graphs, to obtain inductive (Henneberg) constructions, and, when $l=k$, edge-disjoint tree decompositions.
Section:
Proceedings
5. On the Grone-Merris conjecture
Grone and Merris [GM94] conjectured that the Laplacian spectrum of a graph is majorized by its conjugate vertex degree sequence. We prove that this conjecture holds for a class of graphs including trees. We also show that this conjecture and its generalization to graphs with Dirichlet boundary conditions are equivalent.
Section:
Proceedings
6. The Windy Postman Problem on Series-Parallel Graphs
The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of traversal of an edge depends on the direction. Given an undirected graph $G$, we consider the polyhedron $O(G)$ induced by the linear programming relaxation of a well-known integer programming formulation of the problem. We say that $G$ is windy postman perfect if $O(G)$ is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. Eulerian graphs and trees are windy postman perfect. By considering a family of polyhedra related to $O(G)$, we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of [Win1987a].
Section:
Proceedings
7. Connected τ -critical hypergraphs of minimal size
A hypergraph $\mathscr{H}$ is $τ$ -critical if $τ (\mathscr{H}-E) < τ (\mathscr{H})$ for every edge $E ∈\mathscr{H}$, where $τ (\mathscr{H})$ denotes the transversal number of $\mathscr{H}$. It can be shown that a connected $τ$ -critical hypergraph $\mathscr{H}$ has at least $2τ (\mathscr{H})-1$ edges; this generalises a classical theorem of Gallai on $χ$ -vertex-critical graphs with connected complements. In this paper we study connected $τ$ -critical hypergraphs $\mathscr{H}$ with exactly $2τ (\mathscr{H)}-1$ edges. We prove that such hypergraphs have at least $2τ (\mathscr{H})-1$ vertices, and characterise those with $2τ (\mathscr{H})-1$ vertices using a directed odd ear decomposition of an associated digraph. Using Seymour's characterisation of $χ$ -critical 3-chromatic square hypergraphs, we also show that a connected square hypergraph $\mathscr{H}$ with fewer than $2τ (\mathscr{H})$ edges is $τ$ -critical if and only if it is $χ$ -critical 3-chromatic. Finally, we deduce some new results on $χ$ -vertex-critical graphs with connected complements.
Section:
Proceedings
8. A characterization of extremal graphs with no matching-cut
A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|≥\lceil 3(|V|-1)/2\rceil$ , and constructed a large class of immune graphs that attain this lower bound for every value of $|V(G)|$, called $ABC$ graphs. They conjectured that every immune graph that attains this lower bound is an $ABC$ graph. We present a proof of this conjecture.
Section:
Proceedings
9. Packing non-returning A-paths algorithmically
In this paper we present an algorithmic approach to packing A-paths. It is regarded as a generalization of Edmonds' matching algorithm, however there is the significant difference that here we do not build up any kind of alternating tree. Instead we use the so-called 3-way lemma, which either provides augmentation, or a dual, or a subgraph which can be used for contraction. The method works in the general setting of packing non-returning A-paths. It also implies an ear-decomposition of criticals, as a generalization of the odd ear-decomposition of factor-critical graph.
Section:
Proceedings
10. Structure of spaces of rhombus tilings in the lexicograhic case
Rhombus tilings are tilings of zonotopes with rhombohedra. We study a class of \emphlexicographic rhombus tilings of zonotopes, which are deduced from higher Bruhat orders relaxing the unitarity condition. Precisely, we fix a sequence $(v_1, v_2,\dots, v_D)$ of vectors of $ℝ^d$ and a sequence $(m_1, m_2,\dots, m_D)$ of positive integers. We assume (lexicographic hypothesis) that for each subsequence $(v_{i1}, v_{i2},\dots, v_{id})$ of length $d$, we have $det(v_{i1}, v_{i2},\dots, v_{id}) > 0$. The zonotope $Z$ is the set $\{ Σα _iv_i 0 ≤α _i ≤m_i \}$. Each prototile used in a tiling of $Z$ is a rhombohedron constructed from a subsequence of d vectors. We prove that the space of tilings of $Z$ is a graded poset, with minimal and maximal element.
Section:
Proceedings
11. An upper bound for the chromatic number of line graphs
It was conjectured by Reed [reed98conjecture] that for any graph $G$, the graph's chromatic number $χ (G)$ is bounded above by $\lceil Δ (G) +1 + ω (G) / 2\rceil$ , where $Δ (G)$ and $ω (G)$ are the maximum degree and clique number of $G$, respectively. In this paper we prove that this bound holds if $G$ is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph $G$ and produces a colouring that achieves our bound.
Section:
Proceedings
12. Improper colouring of (random) unit disk graphs
For any graph $G$, the $k$-improper chromatic number $χ ^k(G)$ is the smallest number of colours used in a colouring of $G$ such that each colour class induces a subgraph of maximum degree $k$. We investigate the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to extend results of [McRe99, McD03] (where they considered only proper colouring).
Section:
Proceedings
13. $K_{\ell}^{-}$-factors in graphs
Let $K_ℓ^-$ denote the graph obtained from $K_ℓ$ by deleting one edge. We show that for every $γ >0$ and every integer $ℓ≥4$ there exists an integer $n_0=n_0(γ ,ℓ)$ such that every graph $G$ whose order $n≥n_0$ is divisible by $ℓ$ and whose minimum degree is at least $(\frac{ℓ^2-3ℓ+1}{/ ℓ(ℓ-2)}+γ )n$ contains a $K_ℓ^-$-factor, i.e. a collection of disjoint copies of $K_ℓ^-$ which covers all vertices of $G$. This is best possible up to the error term $γn$ and yields an approximate solution to a conjecture of Kawarabayashi.
Section:
Proceedings
14. Mader Tools
The deep theorem of Mader concerning the number of internally disjoint H-paths is a very powerfull tool. Nevertheless its use is very difficult, because one has to deal with a very reach family of separators. This paper shows several ways to strengthen Mader's theorem by certain additional restrictions of the appearing separators.
Section:
Proceedings
15. Multigraph decomposition into multigraphs with two underlying edges
Due to some intractability considerations, reasonable formulation of necessary and sufficient conditions for decomposability of a general multigraph G into a fixed connected multigraph H, is probably not feasible if the underlying simple graph of H has three or more edges. We study the case where H consists of two underlying edges. We present necessary and sufficient conditions for H-decomposability of G, which hold when certain size parameters of G lies within some bounds which depends on the multiplicities of the two edges of H. We also show this result to be "tight" in the sense that even a slight deviation of these size parameters from the given bounds results intractability of the corresponding decision problem.
Section:
Proceedings
16. Degree-correlation of Scale-free graphs
Barabási and Albert [1] suggested modeling scale-free networks by the following random graph process: one node is added at a time and is connected to an earlier node chosen with probability proportional to its degree. A recent empirical study of Newman [5] demonstrates existence of degree-correlation between degrees of adjacent nodes in real-world networks. Here we define the \textitdegree correlation―-correlation of the degrees in a pair of adjacent nodes―-for a random graph process. We determine asymptotically the joint probability distribution for node-degrees, $d$ and $d'$, of adjacent nodes for every $0≤d≤ d'≤n^1 / 5$, and use this result to show that the model of Barabási and Albert does not generate degree-correlation. Our theorem confirms the result in [KR01], obtained by using the mean-field heuristic approach.
Section:
Proceedings
17. Density of universal classes of series-parallel graphs
A class of graphs $\mathcal{C}$ ordered by the homomorphism relation is universal if every countable partial order can be embedded in $\mathcal{C}$. It was shown in [ZH] that the class $\mathcal{C_k}$ of $k$-colorable graphs, for any fixed $k≥3$, induces a universal partial order. In [HN1], a surprisingly small subclass of $\mathcal{C_3}$ which is a proper subclass of $K_4$-minor-free graphs $(\mathcal{G/K_4)}$ is shown to be universal. In another direction, a density result was given in [PZ], that for each rational number $a/b ∈[2,8/3]∪ \{3\}$, there is a $K_4$-minor-free graph with circular chromatic number equal to $a/b$. In this note we show for each rational number $a/b$ within this interval the class $\mathcal{K_{a/b}}$ of $0K_4$-minor-free graphs with circular chromatic number $a/b$ is universal if and only if $a/b ≠2$, $5/2$ or $3$. This shows yet another surprising richness of the $K_4$-minor-free class that it contains universal classes as dense as the rational numbers.
Section:
Proceedings
18. Packing triangles in low degree graphs and indifference graphs
We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation guarantee known so far for these problems has ratio $3/2 + ɛ$, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver in 1989. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs.
Section:
Proceedings
19. Excluded subposets in the Boolean lattice
We are looking for the maximum number of subsets of an n-element set not containing 4 distinct subsets satisfying $A ⊂B, C ⊂B, C ⊂D$. It is proved that this number is at least the number of the $\lfloor \frac{n }{ 2}\rfloor$ -element sets times $1+\frac{2}{ n}$, on the other hand an upper bound is given with 4 replaced by the value 2.
Section:
Proceedings
20. Infinite limits and folding
We study infinite limits of graphs generated by the duplication model for biological networks. We prove that with probability 1, the sole nontrivial connected component of the limits is unique up to isomorphism. We describe certain infinite deterministic graphs which arise naturally from the model. We characterize the isomorphism type and induced subgraph structure of these infinite graphs using the notion of dismantlability from the theory of vertex pursuit games, and graph homomorphisms.
Section:
Proceedings
21. Finding a Strong Stable Set or a Meyniel Obstruction in any Graph
A strong stable set in a graph $G$ is a stable set that contains a vertex of every maximal clique of $G$. A Meyniel obstruction is an odd circuit with at least five vertices and at most one chord. Given a graph $G$ and a vertex $v$ of $G$, we give a polytime algorithm to find either a strong stable set containing $v$ or a Meyniel obstruction in $G$. This can then be used to find in any graph, a clique and colouring of the same size or a Meyniel obstruction.
Section:
Proceedings
22. NBC Complexes of Convex Geometries
We introduce a notion of a $\textit{broken circuit}$ and an $\textit{NBC complex}$ for an (abstract) convex geometry. Based on these definitions, we shall show the analogues of the Whitney-Rota's formula and Brylawski's decomposition theorem for broken circuit complexes on matroids for convex geometries. We also present an Orlik-Solomon type algebra on a convex geometry, and show the NBC generating theorem.
Section:
Proceedings
23. Packing Three-Vertex Paths in a Subcubic Graph
In our paper we consider the $P_3$-packing problem in subcubic graphs of different connectivity, improving earlier results of Kelmans and Mubayi. We show that there exists a $P_3$-packing of at least $\lceil 3n/4\rceil$ vertices in any connected subcubic graph of order $n>5$ and minimum vertex degree $\delta \geq 2$, and that this bound is tight. The proof is constructive and implied by a linear-time algorithm. We use this result to show that any $2$-connected cubic graph of order $n>8$ has a $P_3$-packing of at least $\lceil 7n/9 \rceil$ vertices.
Section:
Proceedings
24. Largest cliques in connected supermagic graphs
A graph $G=(V,E)$ is said to be $\textit{magic}$ if there exists an integer labeling $f: V \cup E \to [1, |V \cup E|]$ such that $f(x)+f(y)+f(xy)$ is constant for all edges $xy \in E$. Enomoto, Masuda and Nakamigawa proved that there are magic graphs of order at most $3n^2+o(n^2)$ which contain a complete graph of order $n$. Bounds on Sidon sets show that the order of such a graph is at least $n^2+o(n^2)$. We close the gap between those two bounds by showing that, for any given graph $H$ of order $n$, there are connected magic graphs of order $n^2+o(n^2)$ containing $H$ as an induced subgraph. Moreover it can be required that the graph admits a supermagic labelling $f$, which satisfies the additional condition $f(V)=[1,|V|]$.
Section:
Proceedings
25. Nonrepetitive colorings of graphs
A vertex coloring of a graph $G$ is $k \textit{-nonrepetitive}$ if one cannot find a periodic sequence with $k$ blocks on any simple path of $G$. The minimum number of colors needed for such coloring is denoted by $\pi _k(G)$ . This idea combines graph colorings with Thue sequences introduced at the beginning of 20th century. In particular Thue proved that if $G$ is a simple path of any length greater than $4$ then $\pi _2(G)=3$ and $\pi_3(G)=2$. We investigate $\pi_k(G)$ for other classes of graphs. Particularly interesting open problem is to decide if there is, possibly huge, $k$ such that $\pi_k(G)$ is bounded for planar graphs.
Section:
Proceedings
26. On the enumeration of uniquely reducible double designs
A double $2$-$(v,k,2 \lambda)$ design is a design which is reducible into two $2$-$(v,k,\lambda)$ designs. It is called uniquely reducible if it has, up to equivalence, only one reduction. We present properties of uniquely reducible double designs which show that their total number can be determined if only the designs with non-trivial automorphisms are classified with respect to their automorphism group. As an application, after proving that a reducible $2$-$(21,5,2)$ design is uniquely reducible, we establish that the number of all reducible $2$-$(21,5,2)$ designs is $1 746 461 307$.
Section:
Proceedings
27. Labeling planar graphs with a condition at distance two
An $L(2,1)$-labeling of a graph is a mapping $c:V(G) \to \{0,\ldots,K\}$ such that the labels assigned to neighboring vertices differ by at least $2$ and the labels of vertices at distance two are different. Griggs and Yeh [SIAM J. Discrete Math. 5 (1992), 586―595] conjectured that every graph $G$ with maximum degree $\Delta$ has an $L(2,1)$-labeling with $K \leq \Delta^2$. We verify the conjecture for planar graphs with maximum degree $\Delta \neq 3$.
Section:
Proceedings
28. Quadratic LYM-type inequalities for intersecting Sperner families
Let $\mathcal{F}\subseteq 2^{[n]}$ be a intersecting Sperner family (i.e. $A \not\subset B, A \cap B \neq \emptyset$ for all $A,B \in \mathcal{F}$) with profile vector $(f_i)_{i=0 \ldots n}$ (i.e. $f_i=|\mathcal{F} \cap \binom{[n]}{i}|$). We present quadratic inequalities in the $f_i$'s which sharpen the previously known linear $\mathrm{LYM}$-type inequalities.
Section:
Proceedings
29. Fast separation in a graph with an excluded minor
Let $G$ be an $n$-vertex $m$-edge graph with weighted vertices. A pair of vertex sets $A,B \subseteq V(G)$ is a $\frac{2}{3} - \textit{separation}$ of $\textit{order}$ $|A \cap B|$ if $A \cup B = V(G)$, there is no edge between $A \backslash B$ and $B \backslash A$, and both $A \backslash B$ and $B \backslash A$ have weight at most $\frac{2}{3}$ the total weight of $G$. Let $\ell \in \mathbb{Z}^+$ be fixed. Alon, Seymour and Thomas [$\textit{J. Amer. Math. Soc.}$ 1990] presented an algorithm that in $\mathcal{O}(n^{1/2}m)$ time, either outputs a $K_\ell$-minor of $G$, or a separation of $G$ of order $\mathcal{O}(n^{1/2})$. Whether there is a $\mathcal{O}(n+m)$ time algorithm for this theorem was left as open problem. In this paper, we obtain a $\mathcal{O}(n+m)$ time algorithm at the expense of $\mathcal{O}(n^{2/3})$ separator. Moreover, our algorithm exhibits a tradeoff between running time and the order of the separator. In particular, for any given $\epsilon \in [0,\frac{1}{2}]$, our algorithm either outputs a $K_\ell$-minor of $G$, or a separation of $G$ with order $\mathcal{O}(n^{(2-\epsilon )/3})$ in $\mathcal{O}(n^{1+\epsilon} +m)$ time.
Section:
Proceedings
30. Supermodularity on chains and complexity of maximum constraint satisfaction
In the maximum constraint satisfaction problem ($\mathrm{Max \; CSP}$), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximise the number (or the total weight) of satisfied constraints. This problem is $\mathrm{NP}$-hard in general so it is natural to study how restricting the allowed types of constraints affects the complexity of the problem. In this paper, we show that any $\mathrm{Max \; CSP}$ problem with a finite set of allowed constraint types, which includes all constants (i.e. constraints of the form $x=a$), is either solvable in polynomial time or is $\mathrm{NP}$-complete. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known combinatorial property of supermodularity.
Section:
Proceedings
31. Permutations with short monotone subsequences
We consider permutations of $1,2,...,n^2$ whose longest monotone subsequence is of length $n$ and are therefore extremal for the Erdős-Szekeres Theorem. Such permutations correspond via the Robinson-Schensted correspondence to pairs of square $n \times n$ Young tableaux. We show that all the bumping sequences are constant and therefore these permutations have a simple description in terms of the pair of square tableaux. We deduce a limit shape result for the plot of values of the typical such permutation, which in particular implies that the first value taken by such a permutation is with high probability $(1+o(1))n^2/2$.
Section:
Proceedings
32. Weak Positional Games on Hypergraphs of Rank Three
In a weak positional game, two players, Maker and Breaker, alternately claim vertices of a hypergraph until either Maker wins by getting a complete edge or all vertices are taken without this happening, a Breaker win. For the class of almost-disjoint hypergraphs of rank three (edges with up to three vertices only and edge-intersections on at most one vertex) we show how to find optimal strategies in polynomial time. Our result is based on a new type of decomposition theorem which might lead to a better understanding of weak positional games in general.
Section:
Proceedings
33. Decomposable graphs and definitions with no quantifier alternation
Let $D(G)$ be the minimum quantifier depth of a first order sentence $\Phi$ that defines a graph $G$ up to isomorphism in terms of the adjacency and the equality relations. Let $D_0(G)$ be a variant of $D(G)$ where we do not allow quantifier alternations in $\Phi$. Using large graphs decomposable in complement-connected components by a short sequence of serial and parallel decompositions, we show examples of $G$ on $n$ vertices with $D_0(G) \leq 2 \log^{\ast}n+O(1)$. On the other hand, we prove a lower bound $D_0(G) \geq \log^{\ast}n-\log^{\ast}\log^{\ast}n-O(1)$ for all $G$. Here $\log^{\ast}n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ below $1$.
Section:
Proceedings
34. Hypertree-Width and Related Hypergraph Invariants
We study the notion of hypertree-width of hypergraphs. We prove that, up to a constant factor, hypertree-width is the same as a number of other hypergraph invariants that resemble graph invariants such as bramble-number, branch-width, linkedness, and the minimum number of cops required to win Seymour and Thomas's robber and cops game.
Section:
Proceedings
35. Monotone Boolean Functions with s Zeros Farthest from Threshold Functions
Let $T_t$ denote the $t$-threshold function on the $n$-cube: $T_t(x) = 1$ if $|\{i : x_i=1\}| \geq t$, and $0$ otherwise. Define the distance between Boolean functions $g$ and $h$, $d(g,h)$, to be the number of points on which $g$ and $h$ disagree. We consider the following extremal problem: Over a monotone Boolean function $g$ on the $n$-cube with $s$ zeros, what is the maximum of $d(g,T_t)$? We show that the following monotone function $p_s$ maximizes the distance: For $x \in \{0,1\}^n$, $p_s(x)=0$ if and only if $N(x) < s$, where $N(x)$ is the integer whose $n$-bit binary representation is $x$. Our result generalizes the previous work for the case $t=\lceil n/2 \rceil$ and $s=2^{n-1}$ by Blum, Burch, and Langford [BBL98-FOCS98], who considered the problem to analyze the behavior of a learning algorithm for monotone Boolean functions, and the previous work for the same $t$ and $s$ by Amano and Maruoka [AM02-ALT02].
Section:
Proceedings
36. Pairwise Intersections and Forbidden Configurations
Let $f_m(a,b,c,d)$ denote the maximum size of a family $\mathcal{F}$ of subsets of an $m$-element set for which there is no pair of subsets $A,B \in \mathcal{F}$ with $|A \cap B| \geq a$, $|\bar{A} \cap B| \geq b$, $|A \cap \bar{B}| \geq c$, and $|\bar{A} \cap \bar{B}| \geq d$. By symmetry we can assume $a \geq d$ and $b \geq c$. We show that $f_m(a,b,c,d)$ is $\Theta (m^{a+b-1})$ if either $b > c$ or $a,b \geq 1$. We also show that $f_m(0,b,b,0)$ is $\Theta (m^b)$ and $f_m(a,0,0,d)$ is $\Theta (m^a)$. This can be viewed as a result concerning forbidden configurations and is further evidence for a conjecture of Anstee and Sali. Our key tool is a strong stability version of the Complete Intersection Theorem of Ahlswede and Khachatrian, which is of independent interest.
Section:
Proceedings
37. A sufficient condition for bicolorable hypergraphs
In this note we prove Sterboul's conjecture, that provides a sufficient condition for the bicolorability of hypergraphs.
Section:
Proceedings
38. The game of arboricity
Using a fixed set of colors $C$, Ann and Ben color the edges of a graph $G$ so that no monochromatic cycle may appear. Ann wins if all edges of $G$ have been colored, while Ben wins if completing a coloring is not possible. The minimum size of $C$ for which Ann has a winning strategy is called the $\textit{game arboricity}$ of $G$, denoted by $A_g(G)$. We prove that $A_g(G) \leq 3k$ for any graph $G$ of arboricity $k$, and that there are graphs such that $A_g(G) \geq 2k-2$. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide other strategie based on induction.
Section:
Proceedings
39. Directed One-Trees
We identify the class of directed one-trees and prove the so-called min-max theorem for them. As a consequence, we establish the equality of directed tree-width and a new measure, $d$-width, on this class of graphs. In addition, we prove a property of all directed one-trees and use this property to create an $O(n^2)$ recognition algorithm and an $O(n^2)$ algorithm for solving the Hamiltonian cycle problem on directed one-trees.
Section:
Proceedings
40. Removing Even Crossings
An edge in a drawing of a graph is called $\textit{even}$ if it intersects every other edge of the graph an even number of times. Pach and Tóth proved that a graph can always be redrawn such that its even edges are not involved in any intersections. We give a new, and significantly simpler, proof of a slightly stronger statement. We show two applications of this strengthened result: an easy proof of a theorem of Hanani and Tutte (not using Kuratowski's theorem), and the result that the odd crossing number of a graph equals the crossing number of the graph for values of at most $3$. We begin with a disarmingly simple proof of a weak (but standard) version of the theorem by Hanani and Tutte.
Section:
Proceedings
41. On the 3/4-Conjecture for Fix-Free Codes
In this paper we concern ourself with the question, whether there exists a fix-free code for a given sequence of codeword lengths. We focus mostly on results which shows the $\frac{3 }{ 4}$-conjecture for special kinds of lengths sequences.
Section:
Proceedings
42. Color critical hypergraphs and forbidden configurations
The present paper connects sharpenings of Sauer's bound on forbidden configurations with color critical hypergraphs. We define a matrix to be \emphsimple if it is a $(0,1)-matrix$ with no repeated columns. Let $F$ be $a k× l (0,1)-matrix$ (the forbidden configuration). Assume $A$ is an $m× n$ simple matrix which has no submatrix which is a row and column permutation of $F$. We define $forb(m,F)$ as the best possible upper bound on n, for such a matrix $A$, which depends on m and $F$. It is known that $forb(m,F)=O(m^k)$ for any $F$, and Sauer's bond states that $forb(m,F)=O(m^k-1)$ fore simple $F$. We give sufficient condition for non-simple $F$ to have the same bound using linear algebra methods to prove a generalization of a result of Lovász on color critical hypergraphs.
Section:
Proceedings
43. Minor-monotone crossing number
The minor crossing number of a graph $G$, $rmmcr(G)$, is defined as the minimum crossing number of all graphs that contain $G$ as a minor. We present some basic properties of this new minor-monotone graph invariant. We give estimates on mmcr for some important graph families using the topological structure of graphs satisfying \$mcr(G) ≤k$.
Section:
Proceedings
44. Linear choosability of graphs
A proper vertex coloring of a non oriented graph $G=(V,E)$ is linear if the graph induced by the vertices of two color classes is a forest of paths. A graph $G$ is $L$-list colorable if for a given list assignment $L=\{L(v): v∈V\}$, there exists a proper coloring $c$ of $G$ such that $c(v)∈L(v)$ for all $v∈V$. If $G$ is $L$-list colorable for every list assignment with $|L(v)|≥k$ for all $v∈V$, then $G$ is said $k$-choosable. A graph is said to be lineary $k$-choosable if the coloring obtained is linear. In this paper, we investigate the linear choosability of graphs for some families of graphs: graphs with small maximum degree, with given maximum average degree, planar graphs... Moreover, we prove that determining whether a bipartite subcubic planar graph is lineary 3-colorable is an NP-complete problem.
Section:
Proceedings
45. Hadamard matrices of order 36 and double-even self-dual [72,36,12] codes
Before this work, at least 762 inequivalent Hadamard matrices of order 36 were known. We found 7238 Hadamard matrices of order 36 and 522 inequivalent [72,36,12] double-even self-dual codes which are obtained from all 2-(35,17,8) designs with an automorphism of order 3 and 2 fixed points and blocks.
Section:
Proceedings
46. Deterministic Random Walks on the Integers
We analyze the one-dimensional version of Jim Propp's $P$-machine, a simple deterministic process that simulates a random walk on $\mathbb{Z}$. The "output'' of the machine is astonishingly close to the expected behavior of a random walk, even on long intervals of space and time.
Section:
Proceedings
47. Chromatic Turán problems and a new upper bound for the Turán density of $\mathcal{K}_4^-$
We consider a new type of extremal hypergraph problem: given an $r$-graph $\mathcal{F}$ and an integer $k≥2$ determine the maximum number of edges in an $\mathcal{F}$-free, $k$-colourable $r$-graph on $n$ vertices. Our motivation for studying such problems is that it allows us to give a new upper bound for an old problem due to Turán. We show that a 3-graph in which any four vertices span at most two edges has density less than $\frac{33}{ 100}$, improving previous bounds of $\frac{1}{ 3}$ due to de Caen [1], and $\frac{1}{ 3}-4.5305×10^-6$ due to Mubayi [9].
Section:
Proceedings
48. On the $L(p,1)$-labelling of graphs
In this paper we improve the best known bound for the $L(p,1)$-labelling of graphs with given maximal degree.
Section:
Proceedings
49. Representations of Edge Intersection Graphs of Paths in a Tree
Let $\mathcal{P}$ be a collection of nontrivial simple paths in a tree $T$. The edge intersection graph of $\mathcal{P}$, denoted by EPT($\mathcal{P}$), has vertex set that corresponds to the members of $\mathcal{P}$, and two vertices are joined by an edge if the corresponding members of $\mathcal{P}$ share a common edge in $T$. An undirected graph $G$ is called an edge intersection graph of paths in a tree, if $G = EPT(\mathcal{P})$ for some $\mathcal{P}$ and $T$. The EPT graphs are useful in network applications. Scheduling undirected calls in a tree or assigning wavelengths to virtual connections in an optical tree network are equivalent to coloring its EPT graph. It is known that recognition and coloring of EPT graphs are NP-complete problems. However, the EPT graphs restricted to host trees of vertex degree 3 are precisely the chordal EPT graphs, and therefore can be colored in polynomial time complexity. We prove a new analogous result that weakly chordal EPT graphs are precisely the EPT graphs with host tree restricted to degree 4. This also implies that the coloring of the edge intersection graph of paths in a degree 4 tree is polynomial. We raise a number of intriguing conjectures regarding related families of graphs.
Section:
Proceedings
50. Colouring random geometric graphs
A random geometric graph $G_n$ is obtained as follows. We take $X_1, X_2, \ldots, X_n ∈\mathbb{R}^d$ at random (i.i.d. according to some probability distribution ν on $\mathbb{R}^d$). For $i ≠j$ we join $X_i$ and $X_j$ by an edge if $║X_i - X_j ║< r(n)$. We study the properties of the chromatic number $χ _n$ and clique number $ω _n$ of this graph as n becomes large, where we assume that $r(n) →0$. We allow any choice $ν$ that has a bounded density function and $║. ║$ may be any norm on $ℝ^d$. Depending on the choice of $r(n)$, qualitatively different types of behaviour can be observed. We distinguish three main cases, in terms of the key quantity $n r^d$ (which is a measure of the average degree). If $r(n)$ is such that $\frac{nr^d}{ln n} →0$ as $n →∞$ then $\frac{χ _n}{ ω _n} →1$ almost surely. If n $\frac{r^d }{\ln n} →∞$ then $\frac{χ _n }{ ω _n} →1 / δ$ almost surely, where $δ$ is the (translational) packing density of the unit ball $B := \{ x ∈ℝ^d: ║x║< 1 \}$ (i.e. $δ$ is the proportion of $d$-space that can be filled with disjoint translates of $B$). If $\frac{n r^d }{\ln n} →t ∈(0,∞)$ then $\frac{χ _n }{ ω _n}$ tends almost surely to a constant that can be bounded in terms of $δ$ and $t$. These results extend earlier work of McDiarmid and Penrose. The proofs in fact yield separate expressions for $χ _n$ and $ω _n$. We are also able to prove a conjecture by Penrose. This states that when […]
Section:
Proceedings
51. Negative results on acyclic improper colorings
Raspaud and Sopena showed that the oriented chromatic number of a graph with acyclic chromatic number $k$ is at most $k2^{k-1}$. We prove that this bound is tight for $k \geq 3$. We also show that some improper and/or acyclic colorings are $\mathrm{NP}$-complete on a class $\mathcal{C}$ of planar graphs. We try to get the most restrictive conditions on the class $\mathcal{C}$, such as having large girth and small maximum degree. In particular, we obtain the $\mathrm{NP}$-completeness of $3$-$\mathrm{ACYCLIC \space COLORABILITY}$ on bipartite planar graphs with maximum degree $4$, and of $4$-$\mathrm{ACYCLIC \space COLORABILITY}$ on bipartite planar graphs with maximum degree $8$.
Section:
Proceedings
52. Spanning paths in hypercubes
Given a family $\{u_i,v_i\}_{i=1}^k$ of pairwise distinct vertices of the $n$-dimensional hypercube $Q_n$ such that the distance of $u_i$ and $v_i$ is odd and $k \leq n-1$, there exists a family $\{P_i\}_{i=1}^k$ of paths such that $u_i$ and $v_i$ are the endvertices of $P_i$ and $\{V(P_i)\}_{i=1}^k$ partitions $V(Q_n)$. This holds for any $n \geq 2$ with one exception in the case when $n=k+1=4$. On the other hand, for any $n \geq 3$ there exist $n$ pairs of vertices satisfying the above condition for which such a family of spanning paths does not exist. We suggest further generalization of this result and explore a relationship to the problem of hamiltonicity of hypercubes with faulty vertices.
Section:
Proceedings
53. On the Minimum Number of Completely 3-Scrambling Permutations
A family $\mathcal{P} = \{\pi_1, \ldots , \pi_q\}$ of permutations of $[n]=\{1,\ldots,n\}$ is $\textit{completely}$ $k$-$\textit{scrambling}$ [Spencer, 1972; Füredi, 1996] if for any distinct $k$ points $x_1,\ldots,x_k \in [n]$, permutations $\pi_i$'s in $\mathcal{P}$ produce all $k!$ possible orders on $\pi_i (x_1),\ldots, \pi_i(x_k)$. Let $N^{\ast}(n,k)$ be the minimum size of such a family. This paper focuses on the case $k=3$. By a simple explicit construction, we show the following upper bound, which we express together with the lower bound due to Füredi for comparison. $\frac{2}{ \log _2e} \log_2 n \leq N^{\ast}(n,3) \leq 2\log_2n + (1+o(1)) \log_2 \log _2n$. We also prove the existence of $\lim_{n \to \infty} N^{\ast}(n,3) / \log_2 n = c_3$. Determining the value $c_3$ and proving the existence of $\lim_{n \to \infty} N^{\ast}(n,k) / \log_2 n = c_k$ for $k \geq 4$ remain open.
Section:
Proceedings
54. Hamiltonian Chains in Hypergraphs
Hamiltionian chain is a generalisation of hamiltonian cycles for hypergraphs. Among the several possible ways of generalisations this is probably the most strong one, it requires the strongest structure. Since there are many interesting questions about hamiltonian cycles in graphs, we can try to answer these questions for hypergraphs, too. In the present article we give a survey on results about such questions.
Section:
Proceedings
55. Relaxed Two-Coloring of Cubic Graphs
We show that any graph of maximum degree at most $3$ has a two-coloring, such that one color-class is an independent set while the other color induces monochromatic components of order at most $189$. On the other hand for any constant $C$ we exhibit a $4$-regular graph, such that the deletion of any independent set leaves at least one component of order greater than $C$. Similar results are obtained for coloring graphs of given maximum degree with $k+ \ell$ colors such that $k$ parts form an independent set and $\ell$ parts span components of order bounded by a constant. A lot of interesting questions remain open.
Section:
Proceedings
56. Counting Polyominoes on Twisted Cylinders
We improve the lower bounds on Klarner's constant, which describes the exponential growth rate of the number of polyominoes (connected subsets of grid squares) with a given number of squares. We achieve this by analyzing polyominoes on a different surface, a so-called $\textit{twisted cylinder}$ by the transfer matrix method. A bijective representation of the "states'' of partial solutions is crucial for allowing a compact representation of the successive iteration vectors for the transfer matrix method.
Section:
Proceedings
57. Local chromatic number and topology
The local chromatic number of a graph, introduced by Erdős et al., is the minimum number of colors that must appear in the closed neighborhood of some vertex in any proper coloring of the graph. This talk would like to survey some of our recent results on this parameter. We give a lower bound for the local chromatic number in terms of the lower bound of the chromatic number provided by the topological method introduced by Lovász. We show that this bound is tight in many cases. In particular, we determine the local chromatic number of certain odd chromatic Schrijver graphs and generalized Mycielski graphs. We further elaborate on the case of $4$-chromatic graphs and, in particular, on surface quadrangulations.
Section:
Proceedings
58. Hamiltonian cycles in torical lattices
We establish sufficient conditions for a toric lattice $T_{m,n}$ to be Hamiltonian. Also, we give some asymptotics for the number of Hamiltonian cycles in $T_{m,n}$.
Section:
Proceedings
59. Enumeration of walks reaching a line
We enumerate walks in the plane $\mathbb{R}^2$, with steps East and North, that stop as soon as they reach a given line; these walks are counted according to the distance of the line to the origin, and we study the asymptotic behavior when the line has a fixed slope and moves away from the origin. When the line has a rational slope, we study a more general class of walks, and give exact as well as asymptotic enumerative results; for this, we define a nice bijection from our walks to words of a rational language. For a general slope, asymptotic results are obtained; in this case, the method employed leads us to find asymptotic results for a wider class of walks in $\mathbb{R}^m$.
Section:
Proceedings
60. Acyclic Coloring of Graphs of Maximum Degree $\Delta$
An acyclic coloring of a graph $G$ is a coloring of its vertices such that: (i) no two neighbors in $G$ are assigned the same color and (ii) no bicolored cycle can exist in $G$. The acyclic chromatic number of $G$ is the least number of colors necessary to acyclically color $G$, and is denoted by $a(G)$. We show that any graph of maximum degree $\Delta$ has acyclic chromatic number at most $\frac{\Delta (\Delta -1) }{ 2}$ for any $\Delta \geq 5$, and we give an $O(n \Delta^2)$ algorithm to acyclically color any graph of maximum degree $\Delta$ with the above mentioned number of colors. This result is roughly two times better than the best general upper bound known so far, yielding $a(G) \leq \Delta (\Delta -1) +2$. By a deeper study of the case $\Delta =5$, we also show that any graph of maximum degree $5$ can be acyclically colored with at most $9$ colors, and give a linear time algorithm to achieve this bound.
Section:
Proceedings
61. On the number of series parallel and outerplanar graphs
We show that the number $g_n$ of labelled series-parallel graphs on $n$ vertices is asymptotically $g_n \sim g \cdot n^{-5/2} \gamma^n n!$, where $\gamma$ and $g$ are explicit computable constants. We show that the number of edges in random series-parallel graphs is asymptotically normal with linear mean and variance, and that the number of edges is sharply concentrated around its expected value. Similar results are proved for labelled outerplanar graphs.
Section:
Proceedings
62. Every $3$-connected, essentially $11$-connected line graph is hamiltonian
Thomassen conjectured that every $4$-connected line graph is hamiltonian. A vertex cut $X$ of $G$ is essential if $G-X$ has at least two nontrivial components. We prove that every $3$-connected, essentially $11$-connected line graph is hamiltonian. Using Ryjáček's line graph closure, it follows that every $3$-connected, essentially $11$-connected claw-free graph is hamiltonian.
Section:
Proceedings
63. Maximal sets of integers not containing $k+1$ pairwise coprimes and having divisors from a specified set of primes
We find the formula for the cardinality of maximal set of integers from $[1,\ldots,n]$ which does not contain $k+1$ pairwise coprimes and has divisors from a specified set of primes. This formula is defined by the set of multiples of the generating set, which does not depend on $n$.
Section:
Proceedings
64. Balanced Avoidance Games on Random Graphs
We introduce and study balanced online graph avoidance games on the random graph process. The game is played by a player we call Painter. Edges of the complete graph with $n$ vertices are revealed two at a time in a random order. In each move, Painter immediately and irrevocably decides on a balanced coloring of the new edge pair: either the first edge is colored red and the second one blue or vice versa. His goal is to avoid a monochromatic copy of a given fixed graph $H$ in both colors for as long as possible. The game ends as soon as the first monochromatic copy of $H$ has appeared. We show that the duration of the game is determined by a threshold function $m_H = m_H(n)$. More precisely, Painter will asymptotically almost surely (a.a.s.) lose the game after $m = \omega (m_H)$ edge pairs in the process. On the other hand, there is an essentially optimal strategy, that is, if the game lasts for $m = o(m_H)$ moves, then Painter will a.a.s. successfully avoid monochromatic copies of H using this strategy. Our attempt is to determine the threshold function for certain graph-theoretic structures, e.g., cycles.
Section:
Proceedings
65. A Min-Max theorem about the Road Coloring Conjecture
The Road Coloring Conjecture is an old and classical conjecture e posed in Adler and Weiss (1970); Adler et al. (1977). Let $G$ be a strongly connected digraph with uniform out-degree $2$. The Road Coloring Conjecture states that, under a natural (necessary) condition that $G$ is "aperiodic'', the edges of $G$ can be colored red and blue such that "universal driving directions'' can be given for each vertex. More precisely, each vertex has one red and one blue edge leaving it, and for any vertex $v$ there exists a sequence $s_v$ of reds and blues such that following the sequence from $\textit{any}$ starting vertex in $G$ ends precisely at the vertex $v$. We first generalize the conjecture to a min-max conjecture for all strongly connected digraphs. We then generalize the notion of coloring itself. Instead of assigning exactly one color to each edge we allow multiple colors to each edge. Under this relaxed notion of coloring we prove our generalized Min-Max theorem. Using the Prime Number Theorem (PNT) we further show that the number of colors needed for each edge is bounded above by $O(\log n / \log \log n)$, where $n$ is the number of vertices in the digraph.
Section:
Proceedings
66. Improving the Gilbert-Varshamov bound for $q$-ary codes
Given positive integers $q$, $n$ and $d$, denote by $A_q(n,d)$ the maximum size of a $q$-ary code of length $n$ and minimum distance $d$. The famous Gilbert-Varshamov bound asserts that $A_q(n,d+1) \geq q^n / V_q(n,d)$, where $V_q(n,d)=\sum_{i=0}^d \binom{n}{i}(q-1)^i$ is the volume of a $q$-ary sphere of radius $d$. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant $\alpha$ less than $(q-1)/q$ there is a positive constant $c$ such that for $d \leq \alpha n, A_q(n,d+1) \geq c \frac{q^n}{ V_q(n,d)}n$. This confirms a conjecture by Jiang and Vardy.
Section:
Proceedings
67. Matchings and Hamilton cycles in hypergraphs
It is well known that every bipartite graph with vertex classes of size $n$ whose minimum degree is at least $n/2$ contains a perfect matching. We prove an analogue of this result for uniform hypergraphs. We also provide an analogue of Dirac's theorem on Hamilton cycles for $3$-uniform hypergraphs: We say that a $3$-uniform hypergraph has a Hamilton cycle if there is a cyclic ordering of its vertices such that every pair of consecutive vertices lies in a hyperedge which consists of three consecutive vertices. We prove that for every $\varepsilon > 0$ there is an $n_0$ such that every $3$-uniform hypergraph of order $n \geq n_0$ whose minimum degree is at least $n/4+ \varepsilon n$ contains a Hamilton cycle. Our bounds on the minimum degree are essentially best possible.
Section:
Proceedings
68. On infinite permutations
We define an infinite permutation as a sequence of reals taken up to the order, or, equivalently, as a linear ordering of a finite or countable set. Then we introduce and characterize periodic permutations; surprisingly, for each period $t$ there is an infinite number of distinct $t$-periodic permutations. At last, we introduce a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is different for the right infinite and the bi-infinite case.
Section:
Proceedings
69. Random Inscribing Polytopes
For convex bodies $K$ with $\mathcal{C}^2$ boundary in $\mathbb{R}^d$, we provide results on the volume of random polytopes with vertices chosen along the boundary of $K$ which we call $\textit{random inscribing polytopes}$. In particular, we prove results concerning the variance and higher moments of the volume, as well as show that the random inscribing polytopes generated by the Poisson process satisfy central limit theorem.
Section:
Proceedings
70. Equivalent Subgraphs of Order $3$
It is proved that any graph of order $14n/3 + O(1)$ contains a family of n induced subgraphs of order $3$ such that they are vertex-disjoint and equivalent to each other.
Section:
Proceedings
71. An extremal problem on trees and database theory
We consider an extremal problem on labelled directed trees and applications to database theory. Among others, we will show explicit keysystems on an underlying set of size $n$, that cannot be represented by a database of less than $2^{n(1-c\cdot \log \log n / \log n)}$ rows.
Section:
Proceedings
72. On the Frobenius’ Problem of three numbers
Given $k$ natural numbers $\{a_1, \ldots ,a_k\} \subset \mathbb{N}$ with $1 \leq a_1 < a_2 < \ldots < a_k$ and $\mathrm{gcd} (a_1, \ldots ,a_k)=1$, let be $R(a_1, \ldots ,a_k) = \{ \lambda_1 a_1+ \cdots + \lambda_k a_k | \space \lambda_i \in \mathbb{N}, i=1 \div k\}$ and $\overline{R}(a_1, \ldots ,a_k) = \mathbb{N} \backslash R (a_1, \ldots ,a_k)$. It is easy to see that $| \overline{R}(a_1, \ldots ,a_k)| < \infty$. The $\textit{Frobenius Problem}$ related to the set $\{a_1, \ldots ,a_k\}$ consists on the computation of $f(a_1, \ldots ,a_k)=\max \overline{R} (a_1, \ldots ,a_k)$, also called the $\textit{Frobenius number}$, and the cardinal $| \overline{R}(a_1, \ldots ,a_k)|$. The solution of the Frobenius Problem is the explicit computation of the set $\overline{R} (a_1,\ldots ,a_k)$. In some cases it is known a sharp upper bound for the Frobenius number. When $k=3$ this bound is known to be $$F(N)=\max\limits_{\substack{0 \lt a \lt b \lt N \\ \mathrm{gcd}(a,b,N)=1}} f(a,b,N)= \begin{cases} 2(\lfloor N/2 \rfloor -1)^2-1 & \textrm{if } N \equiv 0 (\mod 2),\\ 2 \lfloor N/2 \rfloor (\lfloor N/2 \rfloor -1) -1 & \textrm{if } N \equiv 1 (\mod 2).\\ \end{cases}$$ This bound is given in [Dixmier1990]. In this work we give a geometrical proof of this bound which allows us to give the solution of the Frobenius problem for all the sets $\{\alpha ,\beta ,N\}$ such that $f(\alpha ,\beta ,N)=F(N)$.
Section:
Proceedings
73. Discrepancy of Products of Hypergraphs
For a hypergraph $\mathcal{H} = (V,\mathcal{E})$, its $d$―fold symmetric product is $\Delta^d \mathcal{H} = (V^d,\{ E^d | E \in \mathcal{E} \})$. We give several upper and lower bounds for the $c$-color discrepancy of such products. In particular, we show that the bound $\textrm{disc}(\Delta^d \mathcal{H},2) \leq \textrm{disc}(\mathcal{H},2)$ proven for all $d$ in [B. Doerr, A. Srivastav, and P. Wehr, Discrepancy of Cartesian products of arithmetic progressions, Electron. J. Combin. 11(2004), Research Paper 5, 16 pp.] cannot be extended to more than $c = 2$ colors. In fact, for any $c$ and $d$ such that $c$ does not divide $d!$, there are hypergraphs having arbitrary large discrepancy and $\textrm{disc}(\Delta^d \mathcal{H},c) = \Omega_d(\textrm{disc}(\mathcal{H},c)^d)$. Apart from constant factors (depending on $c$ and $d$), in these cases the symmetric product behaves no better than the general direct product $\mathcal{H}^d$, which satisfies $\textrm{disc}(\mathcal{H}^d,c) = O_{c,d}(\textrm{disc}(\mathcal{H},c)^d)$.
Section:
Proceedings
74. A Probabilistic Counting Lemma for Complete Graphs
We prove the existence of many complete graphs in almost all sufficiently dense partitions obtained by an application of Szemerédi's Regularity Lemma. More precisely, we consider the number of complete graphs $K_{\ell}$ on $\ell$ vertices in $\ell$-partite graphs where each partition class consists of $n$ vertices and there is an $\varepsilon$-regular graph on $m$ edges between any two partition classes. We show that for all $\beta > $0, at most a $\beta^m$-fraction of graphs in this family contain less than the expected number of copies of $K_{\ell}$ provided $\varepsilon$ is sufficiently small and $m \geq Cn^{2-1/(\ell-1)}$ for a constant $C > 0$ and $n$ sufficiently large. This result is a counting version of a restricted version of a conjecture by Kohayakawa, Łuczak and Rödl and has several implications for random graphs.
Section:
Proceedings
75. Cycles intersecting edge-cuts of prescribed sizes
We prove that every cubic bridgeless graph $G$ contains a $2$-factor which intersects all (minimal) edge-cuts of size $3$ or $4$. This generalizes an earlier result of the authors, namely that such a $2$-factor exists provided that $G$ is planar. As a further extension, we show that every graph contains a cycle (a union of edge-disjoint circuits) that intersects all edge-cuts of size $3$ or $4$. Motivated by this result, we introduce the concept of a coverable set of integers and discuss a number of questions, some of which are related to classical problems of graph theory such as Tutte's $4$-flow conjecture or the Dominating circuit conjecture.
Section:
Proceedings
76. On minimal blocking sets of the generalized quadrangle $Q(4, q)$
The generalized quadrangle $Q(4,q)$ arising from the parabolic quadric in $PG(4,q)$ always has an ovoid. It is not known whether a minimal blocking set of size smaller than $q^2 + q$ (which is not an ovoid) exists in $Q(4,q)$, $q$ odd. We present results on smallest blocking sets in $Q(4,q)$, $q$ odd, obtained by a computer search. For $q = 5,7,9,11$ we found minimal blocking sets of size $q^2 + q - 2$ and we discuss their structure. By an exhaustive search we excluded the existence of a minimal blocking set of size $q^2 + 3$ in $Q(4,7)$.
Section:
Proceedings
77. Kernel perfect and critical kernel imperfect digraphs structure
A kernel $N$ of a digraph $D$ is an independent set of vertices of $D$ such that for every $w \in V(D)-N$ there exists an arc from $w$ to $N$. If every induced subdigraph of $D$ has a kernel, $D$ is said to be a kernel perfect digraph. Minimal non-kernel perfect digraph are called critical kernel imperfect digraph. If $F$ is a set of arcs of $D$, a semikernel modulo $F$, $S$ of $D$ is an independent set of vertices of $D$ such that for every $z \in V(D)- S$ for which there exists an $Sz-$arc of $D-F$, there also exists an $zS-$arc in $D$. In this talk some structural results concerning critical kernel imperfect and sufficient conditions for a digraph to be a critical kernel imperfect digraph are presented.
Section:
Proceedings