Abstract. Let [Formula: see text] be a 3-uniform hypergraph. The multicolor Ramsey number [Formula: see text] is the smallest integer [Formula: see text] such that every coloring of [Formula: see text] with [Formula: see text] colors has a monochromatic copy of [Formula: see text]. Let [Formula: see text] be the loose 3-uniform path with 3 edges and [Formula: see text] denote the messy 3-uniform path with 3 edges; that is, let [Formula: see text] and [Formula: see text]. In this note we prove [Formula: see text] and [Formula: see text] for [Formula: see text] sufficiently large.

Let $B_i^{(k)}$ be the $k$-uniform hypergraph whose vertex set is of the form $S\cup T$, where $|S|=i$, $|T|=k-1$, and $S\cap T=\emptyset$, and whose edges are the $k$-subsets of $S\cup T$ that contain either $S$ or $T$. We derive upper and lower bounds for the Turán density of $B_i^{(k)}$ that are close to each other as $k\to\infty$. We also obtain asymptotically tight bounds for the Turán density of several other infinite families of hypergraphs. The constructions that imply the lower bounds are derived from elementary number theory by probabilistic arguments, and the upper bounds follow from some results of de Caen, Sidorenko, and Keevash.

We study a problem motivated by a question related to quantum error-correcting codes. Combinatorially, it involves the graph parameter $f(G)=\min\{|A|+|\{x\in V\setminus A:d_A(x)$ is $\text{odd}\}|:A\neq\emptyset\}$, where V is the vertex set of G and $d_A(x)$ is the number of neighbors of x in A. We give asymptotically tight estimates of f for the random graph $G_{n,p}$ when p is constant. Also, if $f(n)=\max\{f(G):\,|V(G)|=n\}$, then we show that $f(n)\leq(0.382+o(1))n$.

In an Achlioptas process two random pairs of $\{1,\dots,n\}$ arrive in each round and the player has to choose one of them. We study the very restrictive version where a player's decisions cannot depend on the previous history and only one vertex from the two random edges is revealed. We prove that the player can create a giant component in $(2\sqrt{5}-4+o(1))n=(0.4721\ldots+o(1))n$ rounds and that this is the best possible. On the other hand, if the player wants to delay the appearance of a giant, then the optimal bound is $(1/2+o(1))n$, the same as in the Erdős–Rényi model.

Given a digraph D=(V,A) and a set of $\kappa$ pairs of vertices in V, we are interested in finding, for each pair (x i , y i ), a directed path connecting x i to y i such that the set of $\kappa$ paths so found is arc-disjoint. For arbitrary graphs the problem is ${\cal NP}$-complete, even for $\kappa=2$. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and the degree r is sufficiently large, then all sets of $\kappa=\Omega(n/\log n)$ pairs of vertices can be joined. This is within a constant factor of best possible.

This article contains a construction for independent sets in the powers of the complements of odd cycles. In particular, we show that /spl alpha/(C~/sub 2n+3/(2/sup n/))/spl ges/2(2/sup n/)+1. It follows that for n/spl ges/0 we have /spl Theta/(C~/sub 2n+3/)>2, where /spl Theta/(G) denotes the Shannon (1956) capacity of graph G.

Given a digraph D=(V, A) and a set of /spl kappa/ pairs of vertices in V, we are interested in finding for each pair (x/sub i/, y/sub i/), a directed path connecting x/sub i/ to y/sub i/, such that the set of /spl kappa/ paths so found is arc-disjoint. For arbitrary graphs, the problem is /spl Nscr//spl Pscr/-complete, even for /spl kappa/=2. We present a polynomial time randomized algorithm for finding arc-disjoint paths in an r-regular expander digraph D. We show that if D has sufficiently strong expansion properties and r is sufficiently large, then all sets of /spl kappa/=/spl Omega/(n/log n) pairs of vertices can be joined. This is within a constant factor of best possible.