Search

Kim and Vu made the following conjecture (Advances in Mathematics, 2004): if$$d\gg \log n$$d≫logn, then the randomd-regular graph$${\mathscr {G}}(n,d)$$G(n,d)can asymptotically almost surely be “sandwiched” between$${\mathscr {G}}(n,p_1)$$G(n,p1)and$${\mathscr {G}}(n,p_2)$$G(n,p2)where$$p_1$$p1and$$p_2$$p2are both$$(1+o(1))d/n$$(1+o(1))d/n. They proved this conjecture for$$\log n\ll d\geqslant n^{1/3-o(1)}$$logn≪d⩾n1/3-o(1), with a defect in the sandwiching:$${\mathscr {G}}(n,d)$$G(n,d)contains$${\mathscr {G}}(n,p_1)$$G(n,p1)perfectly, but is not completely contained in$${\mathscr {G}}(n,p_2)$$G(n,p2). The embedding$${\mathscr {G}}(n,p_1) \subseteq {\mathscr {G}}(n,d)$$G(n,p1)⊆G(n,d)was improved by Dudek, Frieze, Ruciński and Šileikis to$$d=o(n)$$d=o(n). In this paper, we prove Kim–Vu’s sandwich conjecture, with perfect containment on both sides, for alldwhere$$\min \{d, n-d\}\gg n/\sqrt{\log n}$$min{d,n-d}≫n/logn. The sandwich theorem allows translation of many results from$${\mathscr {G}}(n,p)$$G(n,p)to$${\mathscr {G}}(n,d)$$G(n,d)such as Hamiltonicity, the chromatic number, the diameter, etc. It also allows translation of threshold functions of phase transitions from$${\mathscr {G}}(n,p)$$G(n,p)to bond percolation of$${\mathscr {G}}(n,d)$$G(n,d). In addition to sandwiching regular graphs, our results cover graphs whose degrees are asymptotically equal. The proofs rely on estimates for the probability of small subgraph appearances in a random factor of a pseudorandom graph, which is of independent interest.

A linear hypergraph, also known as a partial Steiner system, is a collection of subsets of a set such that no two of the subsets have more than one element in common. Most studies of linear hypergraphs consider only the uniform case, in which all the subsets have the same size. In this paper we provide, for the first time, asymptotically precise estimates of the number of linear hypergraphs in the non-uniform case, as a function of the number of subsets of each size.

A Latin square has six conjugate Latin squares obtained by uniformly permuting its (row, column, symbol) triples. We say that a Latin square has conjugate symmetry if at least two of its six conjugates are equal. We enumerate Latin squares with conjugate symmetry and classify them according to several common notions of equivalence. We also do similar enumerations under additional hypotheses, such as assuming the Latin square is reduced, diagonal, idempotent or unipotent. Our data corrected an error in earlier literature and suggested several patterns that we then found proofs for, including (1) The number of isomorphism classes of semisymmetric idempotent Latin squares of order $n$ equals the number of isomorphism classes of semisymmetric unipotent Latin squares of order $n+1$, and (2) Suppose $A$ and $B$ are totally symmetric Latin squares of order $n\not\equiv0\bmod3$. If $A$ and $B$ are paratopic then $A$ and $B$ are isomorphic.