Abstract. Given an [Formula: see text] vertex graph whose edges have colored from one of [Formula: see text] colors [Formula: see text], we define the Hamilton cycle color profile [Formula: see text] to be the set of vectors [Formula: see text] such that there exists a Hamilton cycle that is the concatenation of [Formula: see text] paths [Formula: see text], where [Formula: see text] contains [Formula: see text] edges of color [Formula: see text]. We study [Formula: see text] when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when [Formula: see text].

We study the isomorphism problem for random hypergraphs. We show that it is solvable in polynomial time for the binomial random k-uniform hypergraph Hn,p;k, for a wide range of p. We also show that it is solvable w.h.p. for random r-regular, k-uniform hypergraphs Hn,r;k,r=O(1).

This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite graph $G$ is $H$-saturated if $G$ does not contain a subgraph isomorphic to $H$ but adding any missing edge to $G$ creates a copy of $H$. More than half a century ago, Wessel and Bollobás independently solved the problem of minimizing the number of edges in $K_{(s,t)}$-saturated graphs, where $K_{(s,t)}$ is the “ordered” complete bipartite graph with $s$ vertices from the first color class and $t$ from the second. However, the very natural “unordered” analogue of this problem was considered only half a decade ago by Moshkovitz and Shapira. When $s=t$, it can be easily checked that the unordered variant is exactly the same as the ordered case. Later, Gan, Korándi, and Sudakov gave an asymptotically tight bound on the minimum number of edges in $K_{(s,t)}$-saturated $n$ by $n$ bipartite graphs, which is only smaller than the conjecture of Moshkovitz and Shapira by an additive constant. In this paper, we confirm their conjecture for $s=t-1$ with the classification of the extremal graphs. We also improve the estimates of Gan, Korándi, and Sudakov for general $s$ and $t$, and for all sufficiently large $n$.