A generalization of the random assignment problem asks the expected cost of the minimum-cost matching of cardinality k in a complete bipartite graph Km,n, with independent random edge weights. With weights drawn from the exponential distribution with intensity 1, the answer has been conjectured to be

Σi,j≥0, i+j<k1/(m−i)(n−j).

Here, we prove the conjecture for k [les ] 4, k = m = 5, and k = m = n = 6, using a structured, automated proof technique that results in proofs with relatively few cases. The method yields not only the minimum assignment cost's expectation but the Laplace transform of its distribution as well. From the Laplace transform we compute the variance in these cases, and conjecture that, with k = m = n → ∞, the variance is 2/n + O(log n/n2). We also include some asymptotic properties of the expectation and variance when k is fixed.

Let Gr denote a graph chosen uniformly at random from the set of r-regular graphs with vertex set {1,2, …, n}, where 3 [les ] r [les ] c0n for some small constant c0. We prove that, with probability tending to 1 as n → ∞, Gr is r-connected and Hamiltonian.

Let c [les ] 0.076122 and T1, T2,…, Tn be a sequence of trees such that [mid ]V(Ti)[mid ] [les ] i−c(i−1). We prove that, if for each 1 [les ] i [les ] n there exists a vertex xi ∈ V(Ti) such that Ti−xi has at least (1−2c)(i−1) isolated vertices, then T1,…, Tn can be packed into Kn. We also prove that if T is a tree of order n+1−c′n, c′ [les ] 1/25 (37−8 √21 ) ≈ 0.0135748, such that there exists a vertex x ∈ V(T) and T−x has at least n(1−2c′) isolated vertices, then 2n+1 copies of T may be packed into K2n+1.

The space of permutation pseudographs is a probabilistic model of 2-regular pseudographs on n vertices, where a pseudograph is produced by choosing a permutation σ of {1,2,…, n} uniformly at random and taking the n edges {i,σ(i)}. We prove several contiguity results involving permutation pseudographs (contiguity is a kind of asymptotic equivalence of sequences of probability spaces). Namely, we show that a random 4-regular pseudograph is contiguous with the sum of two permutation pseudographs, the sum of a permutation pseudograph and a random Hamilton cycle, and the sum of a permutation pseudograph and a random 2-regular pseudograph. (The sum of two random pseudograph spaces is defined by choosing a pseudograph from each space independently and taking the union of the edges of the two pseudographs.) All these results are proved simultaneously by working in a general setting, where each cycle of the permutation is given a nonnegative constant multiplicative weight. A further contiguity result is proved involving the union of a weighted permutation pseudograph and a random regular graph of arbitrary degree. All corresponding results for simple graphs are obtained as corollaries.

Given a family [Fscr ] of r-graphs, let ex(n, [Fscr ]) be the maximum number of edges in an n-vertex r-graph containing no member of [Fscr ]. Let C(r)4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s1 [les ] … [les ] sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr.

Füredi conjectured over 15 years ago that ex(n,C(3)4) [les ] (n2) for sufficiently large n. We prove the weaker result

ex(n, {C(3)4, K(3)(1,2,4)}) [les ] (n2).

Generalizing a well-known conjecture for the Turán number of bipartite graphs, we conjecture that

ex(n, K(r)(s1,…,sr)) = Θ(nr−1/s),

where s = Πr−1i=1si. We prove this conjecture when s1 = … = sr−2 = 1 and

(i) sr−1 = 2, (ii) sr−1 = sr = 3, (iii)sr > (sr−1−1)!.

In cases (i) and (ii), we determine the asymptotic value of ex(n,K(r)(s1,…,sr)).

We also provide an explicit construction giving

ex(n,K(3)(2,2,3)) > (1/6−o(1))n8/3.

This improves upon the previous best lower bound of Ω(n29/11) obtained by probabilistic methods. Several related open problems are also presented.

In ‘Automorphisms of Dowling lattices and related geometries’, J. Bonin constructed the automorphism group A of a Dowling lattice as the image of a certain semidirect product, A = θ(K [rtimes ] H). In this work we find necessary and sufficient conditions for this quotient to be the semidirect product A = θ(K) [rtimes ] θ(H). In addition, we include a construction of A that lends itself to computation more readily than that found in Bonin's work.