The Hamming graph H(d, n) is the Cartesian product of d complete graphs on n vertices. Let ${m=d(n-1)}$ be the degree and $V = n^d$ be the number of vertices of H(d, n). Let $p_c^{(d)}$ be the critical point for bond percolation on H(d, n). We show that, for $d \in \mathbb{N}$ fixed and $n \to \infty$,

$$p_c^{(d)} = {1 \over m} + {{2{d^2} - 1} \over {2{{(d - 1)}^2}}}{1 \over {{m^2}}} + O({m^{ - 3}}) + O({m^{ - 1}}{V^{ - 1/3}}),$$

$O(m^{-1}V^{-1/3})$

$d=4,5,6$

$m^{-3} = O(m^{-1}V^{-1/3})$

$p_c^{(d)}$

$d=2,3,4$

We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe approximation of the Ising partition function. The other is a polynomial of one variable that is obtained by the specialization of the first one. It is shown that these polynomials satisfy deletion–contraction relations and are new examples of the V-function, which was introduced by Tutte (Proc. Cambridge Philos. Soc.43, 1947, p. 26). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs, i.e., spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer–dimer partition function with weights parametrized by that variable. The properties of the coefficients and the possible region of zeros are also discussed for this polynomial.

Given two k-graphs (k-uniform hypergraphs) F and H, a perfect F-tiling (or F-factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H. For all complete k-partite k-graphs K, Mycroft proved a minimum codegree condition that guarantees a K-factor in an n-vertex k-graph, which is tight up to an error term o(n). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that our improved codegree condition is asymptotically tight in infinitely many cases, thus disproving a conjecture of Mycroft. Finally, we determine exact minimum codegree conditions for tiling K(k)(1, … , 1, 2) and tiling loose cycles, thus generalizing the results of Czygrinow, DeBiasio and Nagle, and of Czygrinow, respectively.

This note presents two results on real zeros of chromatic polynomials. The first result states that if $G$ is a graph containing a $q$-tree as a spanning subgraph, then the chromatic polynomial $P(G,\lambda)$ of $G$ has no non-integer zeros in the interval $(0,q)$. Sokal conjectured that for any graph $G$ and any real $\lambda>\Delta(G)$, $P(G,\lambda)>0$. Our second result confirms that it is true if $\Delta(G)\ge \lfloor n/3\rfloor -1$, where $n$ is the order of $G$.

We show that certain topologically defined uniform spanning tree probabilities for graphs embedded in an annulus can be computed as linear combinations of Pfaffians of matrices involving the line-bundle Green's function, where the coefficients count cover-inclusive Dyck tilings of skew Young diagrams.

A graph is claw-free if it does not contain an induced subgraph isomorphic to K1,3. Cycles in claw-free graphs have been well studied. In this paper we extend results on disjoint cycles in claw-free graphs satisfying certain minimum degree conditions. In particular, we prove that if G is claw-free of sufficiently large order n = 3k with δ(G) ≥ n/2, then G contains k disjoint triangles.

Let B = [b1, …, bn] (with column vectors bi) be a basis of ℝn. Then L = [sum ]biℤ is a lattice in ℝn and A = B[top ]B is the Gram matrix of B. The reciprocal lattice L* of L has basis B* = (B−1)[top ] with Gram matrix A−1. For any nonsingular matrix A = (ai,j) with inverse A−1 = (a*i,j), let τ(A) = max1[les ]i[les ]n {[sum ]nj =1[mid ]ai,j ·a*j,j[mid ]}. Then τ(A), τ(A−1)[ges ]1 holds, with equality for an orthogonal basis. We will show that for any lattice L there is a basis with Gram matrix A such that τ(A), τ(A−1) = exp (O((ln n)2)). This generalizes a result in [8] and [20].

For any basis transformation A→Ā with Ā = T[top ]AT, T = (ti,j)∈SLn(ℤ), we will show [mid ]ti,j[mid ][les ]τ(A−1) ·τ(Ā). This implies that every integral matrix representation of a finite group is equivalent to a representation where the coefficients of the matrices representing group elements are bounded by exp (O((ln n)2)). This new bound is considerably smaller than the known (exponential) bounds for automorphisms of Minkowski-reduced lattice bases: see, for example, [6].

The quantities τ(A), τ(A−1) have the following geometric interpretation. Let V(L) [ratio ]= {x∈ℝn[mid ]∀λ∈L [ratio ][mid ]x[mid ][les ][mid ]x−λ[mid ]} be the Voronoi cell (also called the Dirichlet region) of the lattice L. For a basis B of L, we call C(B) = {[sum ]xibi, [mid ]xi[mid ][les ]1/2} the basis cell of B. Both cells define a lattice tiling of ℝn (see [6]); they coincide for an orthogonal basis. For a general basis B of L with Gram matrix A we will show V(L)[les ]τ(A−1)·C(B) and C(B)[les ]n·τ(A)·V(L).

We show that a dense subset of a sufficiently large group multiplication table contains either a large part of the addition table of the integers modulo some k, or the entire multiplication table of a certain large abelian group, as a subgrid. As a consequence, we show that triples systems coming from a finite group contain configurations with t triples spanning $ O(\sqrt t )$ vertices, which is the best possible up to the implied constant. We confirm that for all t we can find a collection of t triples spanning at most t + 3 vertices, resolving the Brown–Erdős–Sós conjecture in this context. The proof applies well-known arithmetic results including the multidimensional versions of Szemerédi’s theorem and the density Hales–Jewett theorem.

This result was discovered simultaneously and independently by Nenadov, Sudakov and Tyomkyn [5], and a weaker result avoiding the arithmetic machinery was obtained independently by Wong [11].

The prime factorization of a random integer has a GEM/Poisson-Dirichlet distribution as transparently proved by Donnelly and Grimmett [8]. By similarity to the arc-sine law for the mean distribution of the divisors of a random integer, due to Deshouillers, Dress and Tenenbaum [6] (see also Tenenbaum [24, II.6.2, p. 233]), – the ‘DDT theorem’ – we obtain an arc-sine law in the GEM/Poisson-Dirichlet context. In this context we also investigate the distribution of the number of components larger than ε which correspond to the number of prime factors larger than nε.

Given a locally finite connected infinite graph G, let the interval [pmin(G), pmax(G)] be the smallest interval such that if p > pmax(G), then every 1-independent bond percolation model on G with bond probability p percolates, and for p < pmin(G) none does. We determine this interval for trees in terms of the branching number of the tree. We also give some general bounds for other graphs G, in particular for lattices.

Let $\Gamma_{k,g}$ be the class of $k$-connected cubic graphs of girth at least $g$. For several choices of $k$ and $g$, we determine a set ${\cal O}_{k,g}$ of graph operations, for which, if $G$ and $H$ are graphs in $\Gamma_{k,g}$, $G\not\cong H$, and $G$ contains $H$ topologically, then some operation in ${\cal O}_{k,g}$ can be applied to $G$ to result in a smaller graph $G'$ in $\Gamma_{k,g}$ such that, on one hand, $G'$ is contained in $G$ topologically, and on the other hand, $G'$ contains $H$ topologically.

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k [ges ] 3. The best known polynomial time approximation algorithms require nδ (for a positive constant δ depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be k-coloured almost surely in polynomial time.

In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into k colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) [ges ] n−1+ε where ε is a constant greater than 1/4.

We define a new ribbon group action on ribbon graphs that uses a semidirect product of a permutation group and the original ribbon group of Ellis-Monaghan and Moffatt to take (partial) twists and duals, or twuals, of ribbon graphs. A ribbon graph is a fixed point of this new ribbon group action if and only if it is isomorphic to one of its (partial) twuals. This extends the original ribbon group action, which only used the canonical identification of edges, to the more natural setting of self-twuality up to isomorphism. We then show that every ribbon graph has in its orbit an orientable embedded bouquet and prove that the (partial) twuality properties of these bouquets propagate through their orbits. Thus, we can determine (partial) twualities via these one vertex graphs, for which checking isomorphism reduces simply to checking dihedral group symmetries. Finally, we apply the new ribbon group action to generate all self-trial ribbon graphs on up to seven edges, in contrast with the few, large, very high-genus, self-trial regular maps found by Wilson, and by Jones and Poultin. We also show how the automorphism group of a ribbon graph yields self-dual, -petrial or –trial graphs in its orbit, and produce an infinite family of self-trial graphs that do not arise as covers or parallel connections of regular maps, thus answering a question of Jones and Poulton.

We define a sequence of tree-indexed processes closely related to the operation of the QuickSelect search algorithm (also known as Find) for all the various values of n (the number of input keys) and m (the rank of the desired order statistic among the keys). As a ‘master theorem’ we establish convergence of these processes in a certain Banach space, from which known distributional convergence results as n → ∞ about

1. (1) the number of key comparisons required

   are easily recovered

   1. (a) when m/n → α ∈ [0, 1], and

   2. (b) in the worst case over the choice of m.

   From the master theorem it is also easy, for distributional convergence of

2. (2) the number of symbol comparisons required,

Our techniques allow us to unify the treatment of cases (1) and (2) and indeed to consider many other cost functions as well. Further, all our results provide a stronger mode of convergence (namely, convergence in Lp or almost surely) than convergence in distribution. Extensions to MultipleQuickSelect are discussed briefly.

Let G be a graph of minimum degree at least k and let Gp be the random subgraph of G obtained by keeping each edge independently with probability p. We are interested in the size of the largest complete minor that Gp contains when p = (1 + ε)/k with ε > 0. We show that with high probability Gp contains a complete minor of order $\tilde{\Omega}(\sqrt{k})$ , where the ~ hides a polylogarithmic factor. Furthermore, in the case where the order of G is also bounded above by a constant multiple of k, we show that this polylogarithmic term can be removed, giving a tight bound.

We introduce the concept of a relative Tutte polynomial of coloured graphs. We show that this relative Tutte polynomial can be computed in a way similar to the classical spanning tree expansion used by Tutte in his original paper on this subject. We then apply the relative Tutte polynomial to virtual knot theory. More specifically, we show that the Kauffman bracket polynomial (and hence the Jones polynomial) of a virtual knot can be computed from the relative Tutte polynomial of its face (Tait) graph with some suitable variable substitutions. Our method offers an alternative to the ribbon graph approach, using the face graph obtained from the virtual link diagram directly.

The thickness of sparse random graphs in the model Gn, p is closely related to the arboricity, provided p(n) is suitably small. This allows us to identify a range of p(n) for which the thickness is approximately np/2.

In the Penney Ante game two players choose one binary string of length k each in turn, and toss a coin repeatedly. If at some stage the last k outcomes match one of their strings, the player with that string wins. The case k ≤ 4 is somewhat exceptional and in any case easily done. For k ≥ 5, Guibas and Odlyzko proved that the second player's optimal strategy is to choose the first k − 1 digits of the first player's string prefixed by 0 or 1. They conjectured that these two choices are never equally good. We prove that this conjecture is correct. Then we prove that 01…100 (with k − 1 ones) is an optimal strategy for the first player, and find all the strategies that are equally good.

Consider a random $n\times n$ zero-one matrix with ‘sparsity’ p, sampled according to one of the following two models: either every entry is independently taken to be one with probability p (the ‘Bernoulli’ model) or each row is independently uniformly sampled from the set of all length-n zero-one vectors with exactly pn ones (the ‘combinatorial’ model). We give simple proofs of the (essentially best-possible) fact that in both models, if $\min(p,1-p)\geq (1+\varepsilon)\log n/n$ for any constant $\varepsilon>0$, then our random matrix is nonsingular with probability $1-o(1)$. In the Bernoulli model, this fact was already well known, but in the combinatorial model this resolves a conjecture of Aigner-Horev and Person.

Let M be a matroid and let Xr count copies of M in a random matroid of rank r. The Poisson and normal convergence of Xr are investigated under some restriction.