Advanced Search

In this paper we show that every family of triples, that is, a 3-uniform hypergraph, with minimum degree at least [...] contains a tight Hamiltonian cycle

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m\left(G\right)=ma{x}_{F\subseteq G}\left|E\left(F\right)\right|/\left|V\left(F\right)\right|$ and define the Ramsey density $m_{inf}(H,r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{inf}(H,r)=(R-1)/2$, where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited to Chvatál...

For two graphs, G and F, and an integer r ≥ 2 we write G → (F)r if every r-coloring of the edges of G results in a monochromatic copy of F. In 1995, the first two authors established a threshold edge probability for the Ramsey property G(n, p) → (F)r, where G(n, p) is a random graph obtained by including each edge of the complete graph on n vertices, independently, with probability p. The original proof was based on the regularity lemma of Szemerédi and this led to tower-type dependencies between...

For an integer $k\ge 2$ and a $k$-uniform hypergraph $H$, let ${\delta }_{k-1}\left(H\right)$ be the largest integer $d$ such that every $(k-1)$-element set of vertices of $H$ belongs to at least $d$ edges of $H$. Further, let $t(k,n)$ be the smallest integer $t$ such that every $k$-uniform hypergraph on $n$ vertices and with ${\delta }_{k-1}\left(H\right)\ge t$ contains a perfect matching. The parameter $t(k,n)$ has been completely determined for all $k$ and large $n$ divisible by $k$ by Rödl, Ruci’nski, and Szemerédi in [, submitted]. The values of $t(k,n)$ are very close to $n/2-k$. In fact, the function $t(k,n)=n/2-k+c_{n,k}$, where $c_{n,k}\in \{3/2,2,5/2,3\}$ depends...