Abstract. For each [Formula: see text], we construct a finite set [Formula: see text] of multigraphs such that for each graph [Formula: see text] of girth at least 5 obtained from a multigraph [Formula: see text] by subdividing each edge at least two times, [Formula: see text] has twin-width at most [Formula: see text] if and only if [Formula: see text] has no minor in [Formula: see text]. This answers a question of Bergé, Bonnet, and Déprés asking for the structure of graphs [Formula: see text] such that each long subdivision of [Formula: see text] has twin-width 4. As a corollary, we show that the [Formula: see text] grid has twin-width 4, which answers a question of Schidler and Szeider.

Abstract. We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph [Formula: see text] is called [Formula: see text]- rainbow saturated if [Formula: see text] does not contain a rainbow copy of [Formula: see text] and adding an edge of any color to [Formula: see text] creates a rainbow copy of [Formula: see text]. The rainbow saturation number [Formula: see text] is the minimum number of edges in an [Formula: see text]-vertex [Formula: see text]-rainbow saturated graph. Girão, Lewis, and Popielarz conjectured that [Formula: see text] for fixed [Formula: see text]. Disproving this conjecture, we establish that for every [Formula: see text], there exists a constant [Formula: see text] such that [Formula: see text] and [Formula: see text]. Recently, Behague, Johnston, Letzter, Morrison, and Ogden independently gave a slightly weaker upper bound which was sufficient to disprove the conjecture. They also introduced the weak rainbow saturation number and asked whether this is equal to the rainbow saturation number of [Formula: see text], since the standard weak saturation number of complete graphs equals the standard saturation number. Surprisingly, our lower bound separates the rainbow saturation number from the weak rainbow saturation number, answering this question in the negative. The existence of the constant [Formula: see text] resolves another of their questions in the affirmative for complete graphs. Furthermore, we show that the conjecture of Girão, Lewis, and Popielarz is true if we have an additional assumption that the edge-colored [Formula: see text]-rainbow saturated graph must be rainbow. As an ingredient of the proof, we study graphs which are [Formula: see text]-saturated with respect to the operation of deleting one edge and adding two edges.

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$.

We systematically study a natural problem in extremal graph theory, to minimize the number of edges in a graph with a fixed number of vertices, subject to a certain local condition: each vertex must be in a copy of a fixed graph $H$. We completely solve this problem when $H$ is a clique, as well as more generally when $H$ is any regular graph with degree at least about half its number of vertices. We also characterize the extremal graphs when $H$ is an Erdös--Rényi random graph. The extremal structures turn out to have the similar form as the conjectured extremal structures for a well-studied but elusive problem of similar flavor with local constraints: to maximize the number of copies of a fixed clique in graphs in which all degrees have a fixed upper bound.