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.

Let q be a power of a prime p, and let n, d, ℓ be integers such that 1 ≤ n, 1 ≤ ℓ < q. Consider the modulo q complete ℓ-wide family:

We describe a Gröbner basis of the vanishing ideal I() of the set of characteristic vectors of over fields of characteristic p. It turns out that this set of polynomials is a Gröbner basis for all term orderings ≺, for which the order of the variables is xn ≺ xn−1 ≺ ⋅⋅⋅ ≺ x1.

We compute the Hilbert function of I(), which yields formulae for the modulo p rank of certain inclusion matrices related to .

We apply our results to problems from extremal set theory. We prove a sharp upper bound of the cardinality of a modulo q ℓ-wide family, which shatters only small sets. This is closely related to a conjecture of Frankl [13] on certain ℓ-antichains. The formula of the Hilbert function also allows us to obtain an upper bound on the size of a set system with certain restricted intersections, generalizing a bound proposed by Babai and Frankl [6].

The paper generalizes and extends the results of [15], [16] and [17].

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.

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.

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.

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 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 classical Andrásfai-Erdős-Sós theorem considers the chromatic number of $K_{r + 1}$ -free graphs with large minimum degree, and in the case, $r = 2$ says that any n-vertex triangle-free graph with minimum degree greater than $2/5 \cdot n$ is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each k, what minimum degree guarantees that a triangle-free graph is k-colourable? The chromatic profile has been extensively studied and was finally determined by Brandt and Thomassé. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, Luczak and Thomassé introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is b-colourable (locally b-partite graphs) as well as the family where the common neighbourhood of every a-clique is b-colourable. Our results include the chromatic thresholds of these families (extending a result of Allen, Böttcher, Griffiths, Kohayakawa and Morris) as well as showing that every n-vertex locally b-partite graph with minimum degree greater than $(1 - 1/(b + 1/7)) \cdot n$ is $(b + 1)$ -colourable. Understanding these locally colourable graphs is crucial for extending the Andrásfai-Erdős-Sós theorem to non-complete graphs, which we develop elsewhere.

We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K2m,2m, a result connected to a conjecture of Graham and Häggkvist. The result also implies that asymptotically almost surely a tree with m edges decomposes the complete graph with O(m2) edges. An ingredient of the proof consists in showing that the bipartition classes of the base tree of a random tree have roughly equal size.

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.

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.

Let and be sets of functions from domain X to ℝ. We say that validly generalises from approximate interpolation if and only if for each η > 0 and ∈, δ ∈ (0,1) there is m0(η, ∈, δ) such that for any function t ∈ and any probability distribution on X, if m > m0 then with m-probability at least 1 – δ, a sample X = (x1, X2,…,xm) ∈ Xm satisfies

We find conditions that are necessary and sufficient for to validly generalise from approximate interpolation, and we obtain bounds on the sample length m0{η,∈,δ) in terms of various parameters describing the expressive power of .

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.

Hurwitz's extension of Abel's binomial theorem defines a probability distribution on the set of integers from 0 to n. This is the distribution of the number of non-root vertices of a fringe subtree of a suitably defined random tree with n + 2 vertices. The asymptotic behaviour of this distribution is described in a limiting regime in which the fringe subtree converges in distribution to a Galton–Watson tree with a mixed Poisson offspring distribution.

A graph G arrows a graph H if in every 2-edge-colouring of G there exists a monochromatic copy of H. Schelp had the idea that if the complete graph $K_n$ arrows a small graph H, then every ‘dense’ subgraph of $K_n$ also arrows H, and he outlined some problems in this direction. Our main result is in this spirit. We prove that for every sufficiently large n, if $n = 3t+r$ where $r \in \{0,1,2\}$ and G is an n-vertex graph with $\delta(G) \ge (3n-1)/4$ , then for every 2-edge-colouring of G, either there are cycles of every length $\{3, 4, 5, \dots, 2t+r\}$ of the same colour, or there are cycles of every even length $\{4, 6, 8, \dots, 2t+2\}$ of the samecolour.

Our result is tight in the sense that no longer cycles (of length $>2t+r$ ) can be guaranteed and the minimum degree condition cannot be reduced. It also implies the conjecture of Schelp that for every sufficiently large n, every $(3t-1)$ -vertex graph G with minimum degree larger than $3|V(G)|/4$ arrows the path $P_{2n}$ with 2n vertices. Moreover, it implies for sufficiently large n the conjecture by Benevides, Łuczak, Scott, Skokan and White that for $n=3t+r$ where $r \in \{0,1,2\}$ and every n-vertex graph G with $\delta(G) \ge 3n/4$ , in each 2-edge-colouring of G there exists a monochromatic cycle of length at least $2t+r$ .

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $, where k ≥ 3 is an integer, contains at least

$$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$

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.

We consider a string editing problem in a probabilistic framework. This problem is of considerable interest to many facets of science, most notably molecular biology and computer science. A string editing transforms one string into another by performing a series of weighted edit operations of overall maximum (minimum) cost. The problem is equivalent to finding an optimal path in a weighted grid graph. In this paper we provide several results regarding a typical behaviour of such a path. In particular, we observe that the optimal path (i.e. edit distance) is almost surely (a.s.) equal to αn for large n where α is a constant and n is the sum of lengths of both strings. More importantly, we show that the edit distance is well concentrated around its average value. In the so called independent model in which all weights (in the associated grid graph) are statistically independent, we derive some bounds for the constant α. As a by-product of our results, we also present a precise estimate of the number of alignments between two strings. To prove these findings we use techniques of random walks, diffusion limiting processes, generating functions, and the method of bounded difference.

Let $\mathcal F$ ⊂ 2[n] be a family of subsets. The diameter of $\mathcal F$ is the maximum of the size of symmetric differences among pairs of members of $\mathcal F$. In 1966 Kleitman determined the maximum of |$\mathcal F$| for fixed diameter. However, this important classical result lacked a characterization of the families meeting the bound. This is remedied in the present paper, where a best possible stability result is established as well.

In Section 4 we introduce a ‘parity trick’ that provides an easy way of deducing the odd case from the even case in both Kleitman's original theorem and its stability version.

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.