Let G be a graph on vertex set [n], and for X ⊆ [n] let N(X) be the union of X and its neighbourhood in G. A family of sets [Fscr ] ⊆ 2[n] is G-intersecting if N(X) ∩ Y ≠ [empty ] for all X, Y ∈ [Fscr ]. In this paper we study the cardinality and structure of the largest k-uniform G-intersecting families on a fixed graph G.

A random interval graph of order n is generated by picking 2n numbers X1,…,X2n independently from the uniform distribution on [0,1] and considering the collection of n intervals with endpoints X2i−1 and X2i for i ∈ {1,…,n}. The graph vertices correspond to intervals. Two vertices are connected if the corresponding intervals intersect. This paper characterizes the fluctuations of the independence number in random interval graphs. This characterization is obtained through the analysis of the greedy algorithm. We actually prove limit theorems (central limit theorem and large deviation principle) on the number of phases of this greedy algorithm. The proof relies on the analysis of first-passage times through a random level.

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n [ges ] n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

We introduce a notion of the derivative with respect to a function, not necessarily related to a probability distribution, which generalizes the concept of derivative as proposed by Lebesgue [14]. The differential calculus required to solve linear differential equations using this notion of the derivative is included in the paper. The definition given here may also be considered as the inverse operator of a modified notion of the Riemann–Stieltjes integral. Both this unified approach and the results of differential calculus allow us to characterize distributions in terms of three different types of conditional expectations. In applying these results, a test of goodness of fit is also indicated. Finally, two characterizations of a general Poisson process are included. Specifically, a useful result for the homogeneous Poisson process is generalized.

Given an r-graph F, an r-graph G is called weakly F-saturated if the edges missing from G can be added, one at a time, in some order, each extra edge creating a new copy of F. Let w-sat(n, F) be the minimal size of a weakly F-saturated graph of order n. We compute the w-sat function for a wide class of r-graphs called pyramids: these include many examples for which the w-sat function was known, as well as many new examples, such as the computation of w-sat(n,Ks + Kt), and enable us to prove a conjecture of Tuza.

Our main technique, developed from ideas of Kalai, is based on matroids derived from exterior algebra. We prove that if it succeeds for some graphs then the same is true for the ‘cones’ and ‘joins’ of such graphs, so that the w-sat function can be computed for many graphs that are built up from certain elementary graphs by these operations.

We generalize a minimal 3-connectivity result of Halin from graphs to binary matroids. As applications of this theorem to minimally 3-connected matroids, we obtain new results and short inductive proofs of results of Oxley and Wu. We also give new short inductive proofs of results of Dirac and Halin on minimally k-connected graphs for k ∈ {2,3}.