Search

We provide sufficient conditions for the existence of long cycles in locally expanding graphs, and present applications of our conditions and techniques to Ramsey theory, random graphs and positional games. [ABSTRACT FROM AUTHOR]

A theorem of Lovász asserts that τ( H)/τ*( H)≤ r/2 for every r-partite hypergraph H (where τ and τ* denote the covering number and fractional covering number respectively). Here it is shown that the same upper bound is valid for a more general class of hypergraphs: those which admit a partition ( V, ..., V) of the vertex set and a partition p+...+ p of r such that | e⌢ V|≤ p≤ r/2 for every edge e and every 1≤ i≤ k. Moreover, strict inequality holds when r>2, and in this form the bound is tight. The investigation of the ratio τ/τ* is extended to some other classes of hypergraphs, defined by conditions of similar flavour. Upper bounds on this ratio are obtained for k-colourable, strongly k-colourable and (what we call) k-partitionable hypergraphs. [ABSTRACT FROM AUTHOR]