An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdős, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.

We perform the asymptotic enumeration of two classes of rooted maps on orientable surfaces: m-hypermaps and m-constellations. For m = 2 they correspond respectively to maps with even face degrees and bipartite maps. We obtain explicit asymptotic formulas for the number of such maps with any finite set of allowed face degrees.

Our proofs combine a bijective approach, generating series techniques related to lattice walks, and elementary algebraic graph theory.

A special case of our results implies former conjectures of Z. Gao.

It is well known that, when normalized by n, the expected length of a longest common subsequence of d sequences of length n over an alphabet of size σ converges to a constant γσ,d. We disprove a speculation by Steele regarding a possible relation between γ2,d and γ2,2. In order to do that we also obtain some new lower bounds for γσ,d, when both σ and d are small integers.

Let G = G(n) be a randomly chosen k-edge-coloured k-regular graph with 2n vertices, where k = k(n). Such a graph can be obtained from a random set of k edge-disjoint perfect matchings of K2n. Let h = h(n) be a graph with m = m(n) edges such that m2 + mk = o(n). Using a switching argument, we find an asymptotic estimate of the expected number of subgraphs of G isomorphic to h. Isomorphisms may or may not respect the edge colouring, and other generalizations are also presented. Special attention is paid to matchings and cycles.

The results in this paper are essential to a forthcoming paper of McLeod in which an asymptotic estimate for the number of k-edge-coloured k-regular graphs for k = o(n5/6) is found.

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colourable, Hamiltonian, etc.) if and only if a related system of polynomial equations has a solution.

For an infeasible polynomial system, the (complex) Hilbert Nullstellensatz gives a certificate that the associated combinatorial problem is infeasible. Thus, unless P = NP, there must exist an infinite sequence of infeasible instances of each hard combinatorial problem for which the minimum degree of a Hilbert Nullstellensatz certificate of the associated polynomial system grows.

In the first part of the paper, we show that the minimum degree of a Nullstellensatz certificate for the non-existence of a stable set of size greater than the stability number of the graph is the stability number of the graph. Moreover, such a certificate contains at least one term per stable set of G. In contrast, for non-3-colourability, we proved that the minimum degree of a Nullstellensatz certificate is at least four. Our efforts so far have only yielded graphs with Nullstellensatz certificates of precisely that degree.

In the second part of this paper, for the purpose of computation, we construct new polynomial encodings for the problems of finding in a graph its longest cycle, the largest planar subgraph, the edge-chromatic number, or the largest k-colourable subgraph. We include some applications to graph theory.

A minor-closed class of graphs is addable if each excluded minor is 2-connected. We see that such a class of labelled graphs has smooth growth; and, for the random graph Rn sampled uniformly from the n-vertex graphs in , the fragment not in the giant component asymptotically has a simple ‘Boltzmann Poisson distribution’. In particular, as n → ∞ the probability that Rn is connected tends to 1/A(ρ), where A(x) is the exponential generating function for and ρ is its radius of convergence.

The U-polynomial, the polychromate and the symmetric function generalization of the Tutte polynomial, due to Stanley, are known to be equivalent in the sense that the coefficients of any one of them can be obtained as a function of the coefficients of any other. The definition of each of these functions suggests a natural way in which to strengthen them, which also captures Tutte's universal V-function as a specialization. We show that the equivalence remains true for the strong functions, thus answering a question raised by Dominic Welsh.