Let h(·) be an arrangement increasing function, let X have an arrangement increasing density, and let XE be a random permutation of the coordinates of X. We prove E{h(XE)} ≤ E{h(X)}. This comparison is delicate in that similar results are sometimes true and sometimes false. In a finite distributive lattice, a similar comparison follows from Holley's inequality, but the set of permutations with the arrangement order is not a lattice. On the other hand, the set of permutations is a lattice, though not a distributive lattice, if it is endowed with a different partial order, but in this case the comparison does not hold.

Analogues of the Erdős-Ko-Rado theorem are proved for the Boolean algebra of all subsets of {1,…n} and in this algebra truncated by the removal of the empty set and the whole set.

We define and efficiently compute the canonical flow on a graph, which is a certain feasible solution for the concurrent flow problem and exhibits invariance under the action of the automorphism group of the graph. Using estimates for the congestion of our canonical flow, we derive lower bounds on the crossing number, bisection width, and the edge and vertex expansion of a graph in terms of sizes of the edge and vertex orbits and the average distance in the graph. We further exhibit classes of graphs for which our lower bounds are tight within a multiplicative constant. Also, in cartesian product graphs a concurrent flow is constructed in terms of the concurrent flows in the factors, and in this way lower bounds for the edge and vertex expansion of the power graphs are derived in terms of that of the original graph.

Let ℝ+(ℋn),ℤ(ℋn),ℤ+(ℋn) be, respectively, the cone over ℝ, the lattice and the cone over ℤ, generated by all cuts of the complete graph on n nodes. For i ≥ 0, let has exactly i realizations in ℤ+(ℋn)}. We show that is infinite, except for the undecided case and empty and for i = 0, n ≤ 5 and for i ≥ 2, n ≤ 3. The set contains 0,1,∞ nonsimplicial points for n ≤ 4, n = 5, n ≥ 6, respectively. On the other hand, there exists a finite number t(n) such that t(n)d ∈ ℤ+(ℋn) for any ; we also estimate such scales for classes of points. We construct families of points of and ℤ+(ℋn), especially on a 0-lifting of a simplicial facet, and points d ∈ ℝ+(ℋn) with di, n = t for 1 ≤ i ≤ n − 1.

Gallai [1] raised the question of determining t(n), the maximum number of triangles in graphs of n vertices with acyclic neighborhoods. Here we disprove his conjecture (t(n) ~ n2/8) by exhibiting graphs having n2/7.5 triangles. We improve the upper bound [11] of (n2 − n)/6 to t(n) ≤; n2/7.02 + O(n). For regular graphs, we further decrease this bound to n2/7.75 + O(n).

The main result of this paper is that for every 2 ≤ r < s, and n sufficiently large, there exist graphs of order n, not containing a complete graph on s vertices, in which every relatively not too small subset of vertices spans a complete graph on r vertices. Our results improve on previous results of Bollobás and Hind.

We give some sufficient conditions for an (S, U)-outline T-factorization of Kn to be an (S, U)-amalgamated T-factorization of Kn. We then apply these to give various necessary and sufficient conditions for edge coloured graphs G to have recoverable embeddings in T-factorized Kn's.

We introduce five probability models for random topological graph theory. For two of these models (I and II), the sample space consists of all labeled orientable 2-cell imbeddings of a fixed connected graph, and the interest centers upon the genus random variable. Exact results are presented for the expected value of this random variable for small-order complete graphs, for closed-end ladders, and for cobblestone paths. The expected genus of the complete graph is asymptotic to the maximum genus. For Model III, the sample space consists of all labeled 2-cell imbeddings (possibly nonorientable) of a fixed connected graph, and for Model IV the sample space consists of all such imbeddings with a rotation scheme also fixed. The event of interest is that the ambient surface is orientable. In both these models the complete graph is almost never orientably imbedded. The probability distribution in Models I and III is uniform; in Models II and IV it depends on a parameter p and is uniform precisely when p = 1/2. Model V combines the features of Models II and IV.

It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T-or Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.

A Steiner quadruple system SQS(v) of order v is a family ℬ of 4-element subsets of a v-element set V such that each 3-element subset of V is contained in precisely one B ∈ ℬ. We prove that if T ∩ B ≠ ø for all B ∈ ℬ (i.e., if T is a transversal), then |T| ≥ v/2, and if T is a transversal of cardinality exactly v/2, then V \ T is a transversal as well (i.e., T is a blocking set). Also, in respect of the so-called ‘doubling construction’ that produces SQS(2v) from two copies of SQS(v), we give a necessary and sufficient condition for this operation to yield a Steiner quadruple system with blocking sets.

An element e of a matroid M is called non-binary when M\e and M/e are both non-binary matroids. Oxley in [5] gave a characterization of the 3-connected non-binary matroids without non-binary elements. In this paper, we will construct all the 3-connected matroids having 1, 2 or 3 non-binary elements.

Every general graph with degrees 2k and 2k − 2, k ≥ 3, with zero or at least two vertices of degree 2k − 2 in each component, has a k-edge-colouring such that each monochromatic subgraph has degree 1 or 2 at every vertex.

In particular, if T is a triangle in a 6-regular general graph, there exists a 2-factorization of G such that each factor uses an edge in T if and only if T is non-separating.

Let f(t) be the largest integer such that every graph with average degree t has a topological clique with f(i) vertices. It is widely believed that . Here we prove the weaker estimate .

Suppose M and N are distinct matroids on a set E such that, for every e ∈ E, the deletion of e from M equals the deletion of e from N or the contraction of e from M equals the contraction of e from N. In this note we prove that, apart from some easily specified exceptions, one of M and N must be a relaxation of the other.

Let S be a closed surface with boundary ∂S and let G be a graph. Let K ⊆ G be a subgraph embedded in S such that ∂S ⊆ K. An embedding extension of K to G is an embedding of G in S that coincides on K with the given embedding of K. Minimal obstructions for the existence of embedding extensions are classified in cases when S is the disk or the cylinder. Linear time algorithms are presented that either find an embedding extension, or return an obstruction to the existence of extensions. These results are to be used as the corner stones in the design of linear time algorithms for the embeddability of graphs in an arbitrary surface and for solving more general embedding extension problems.

The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph Gnm are shown to be asymptotically normal if m is neither too large nor too small. At the lowest limit m ≍ n3/2, these numbers are asymptotically log-normal. For Gnp, the numbers are asymptotically log-normal for a wide range of p, including p constant. The same results are obtained for random directed graphs and bipartite graphs. The results are proved using decomposition and projection methods.

All digraphs are determined that have the property that when any vertex and any edge that are not adjacent are deleted, the connectivity number decreases by two.