We determine lower bounds for the number of random binary vectors, chosen uniformly from vectors of weight k, needed to obtain a dependent set.

It is shown that an oriented graph of order n whose every indegree and outdegree is at least cn is hamiltonian if c ≥ ½ − 2−15 but need not be if c < ⅜.

We analyse a class of randomized Least Recently Used (LRU) cache replacement algorithms under the independent reference model with generalized Zipf's law request probabilities. The randomization was recently proposed for Web caching as a mechanism that discriminates between different document sizes. In particular, the cache maintains an ordered list of documents in the following way. When a document of size $s$ is requested and found in the cache, then with probability $p_s$ it is moved to the front of the cache; otherwise the cache stays unchanged. Similarly, if the requested document of size $s$ is not found in the cache, the algorithm places it with probability $p_s$ to the front of the cache or leaves the cache unchanged with the complementary probability $(1-p_s)$. The successive randomized decisions are independent and the corresponding success probabilities $p_s$ are completely determined by the size of the currently requested document. In the case of a replacement, the necessary number of documents that are least recently moved to the front of the cache are removed in order to accommodate the newly placed document.

In this framework, we provide explicit asymptotic characterization of the cache fault probability. Using the derived result we prove that the asymptotic performance of this class of algorithms is optimized when the randomization probabilities are chosen to be inversely proportional to document sizes. In addition, for this optimized and easy-to-implement policy, we show that its performance is within a constant factor from the optimal static algorithm.

We study the diameter of 1, the largest component of the Erdős–Rényi random graph (n, p) in the emerging supercritical phase, i.e., for p = where ε3n → ∞ and ε = o(1). This parameter was extensively studied for fixed ε > 0, yet results for ε = o(1) outside the critical window were only obtained very recently. Prior to this work, Riordan and Wormald gave precise estimates on the diameter; however, these did not cover the entire supercritical regime (namely, when ε3n → ∞ arbitrarily slowly). Łuczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differed by a factor of .

We show that throughout the emerging supercritical phase, i.e., for any ε = o(1) with ε3n → ∞, the diameter of 1 is with high probability asymptotic to D(ε, n) = (3/ε)log(ε3n). This constitutes the first proof of the asymptotics of the diameter valid throughout this phase. The proof relies on a recent structure result for the supercritical giant component, which reduces the problem of estimating distances between its vertices to the study of passage times in first-passage percolation. The main advantage of our method is its flexibility. It also implies that in the emerging supercritical phase the diameter of the 2-core of 1 is w.h.p. asymptotic to , and the maximal distance in 1 between any pair of kernel vertices is w.h.p. asymptotic to .

The van der Waerden theorem in Ramsey theory states that, for every k and t and sufficiently large N, every k-colouring of [N] contains a monochromatic arithmetic progression of length t. Motivated by this result, Radoičić conjectured that every equinumerous 3-colouring of [3n] contains a 3-term rainbow arithmetic progression, i.e., an arithmetic progression whose terms are coloured with distinct colours. In this paper, we prove that every 3-colouring of the set of natural numbers for which each colour class has density more than 1/6, contains a 3-term rainbow arithmetic progression. We also prove similar results for colourings of . Finally, we give a general perspective on other anti-Ramsey-type problems that can be considered.

A 1993 result of Alon and Füredi gives a sharp upper bound on the number of zeros of a multivariate polynomial over an integral domain in a finite grid, in terms of the degree of the polynomial. This result was recently generalized to polynomials over an arbitrary commutative ring, assuming a certain ‘Condition (D)’ on the grid which holds vacuously when the ring is a domain. In the first half of this paper we give a further generalized Alon–Füredi theorem which provides a sharp upper bound when the degrees of the polynomial in each variable are also taken into account. This yields in particular a new proof of Alon–Füredi. We then discuss the relationship between Alon–Füredi and results of DeMillo–Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon–Füredi theorem and its generalization in terms of Reed–Muller-type affine variety codes is shown, which gives us the minimum Hamming distance of these codes. Then we apply the Alon–Füredi theorem to quickly recover – and sometimes strengthen – old and new results in finite geometry, including the Jamison–Brouwer–Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.

We provide an alternate proof of the central limit theorem for the uctuations of the size of the giant component in sparse random graphs. In contrast with previous proofs, the argument investigates a depth-first search algorithm, through first-passage analysis using couplings and martingale limit theorems. The analysis of the first passage limiting distribution for sequences of Markov chains might be interesting in its own right. This proof naturally provides an upper bound for the rate of convergence.

Erdős asked in 1962 about the value of f(n,k,l), the minimum number of k-cliques in a graph with order n and independence number less than l. The case (k,l)=(3,3) was solved by Lorden. Here we solve the problem (for all large n) for (3,l) with 4 ≤ l ≤ 7 and (k,3) with 4 ≤ k ≤ 7. Independently, Das, Huang, Ma, Naves and Sudakov resolved the cases (k,l)=(3,4) and (4,3).

There are several known results asserting that undirected graphs can be partitioned in a way that satisfies various constraints imposed on the degrees. The corresponding results for directed graphs, where degrees are replaced by outdegrees, often fail, and when they do hold, they are usually much harder, and lead to fascinating open problems. In this note we list three problems of this type, and mention the undirected analogues. All graphs and digraphs considered here are simple, that is, they have no loops and no multiple edges.

We give a combinatorial proof of the result of Kahn, Kalai and Linial [16], which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least . The methods of the proof are then used to recover additional isoperimetric results for the cube, with improved constants.

We also state some conjectures about optimal constants.

We study the number of random records in a binary search tree with n vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

Let p and q be distinct primes. We characterize transitive groups G that admit a complete block system of q blocks of size p such that the subgroup of G which fixes each block set-wise has a Sylow p-subgroup of order p. Using this result, we prove that the full automorphism group of a metacirculant graph Γ of order pq such that Aut(Γ) is imprimitive, is contained in one of several families of transitive groups. As the automorphism groups of vertex-transitive graphs of order pq that are primitive have been determined by several authors, this result implies that automorphism groups of vertex-transitive graphs of order pq are known. We also determine all nonnormal Cayley graphs of order pq, and all 1/2-transitive graphs of order pq.

In this paper, we combine two previous works, the first being by the first author and K. Nelander, and the second by J. van den Berg and the second author, to show (1) that one can carry out a Propp–Wilson exact simulation for all Markov random fields on ℤd satisfying a certain high noise assumption, and (2) that all such random fields are a finitary image of a finite state i.i.d. process. (2) is a strengthening of the previously known fact that such random fields are so-called Bernoulli shifts.

Let d = (d1, d2, . . ., dn) be a vector of non-negative integers with even sum. We prove some basic facts about the structure of a random graph with degree sequence d, including the probability of a given subgraph or induced subgraph.

Although there are many results of this kind, they are restricted to the sparse case with only a few exceptions. Our focus is instead on the case where the average degree is approximately a constant fraction of n.

Our approach is the multidimensional saddle-point method. This extends the enumerative work of McKay and Wormald (1990) and is analogous to the theory developed for bipartite graphs by Greenhill and McKay (2009).

The smallest minimal degree of an r-partite graph that guarantees the existence of a complete subgraph of order r has been found for the case r = 3 by Bollobás, Erdő and Szemerédi, who also gave bounds for the cases r ≥ 4. In this paper the exact value is established for the cases r = 4 and 5, and the bounds for r ≥ 6 are improved.

Let H be a graph on h vertices, and G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n/h vertex disjoint copies of H. The fractional arboricity of H is , where the maximum is taken over all subgraphs (V′, E′) of H with |V′| > 1. Let δ(H) denote the minimum degree of a vertex of H. It is shown that if δ(H) < a(H), then n−1/a(H) is a sharp threshold function for the property that the random graph G(n, p) contains an H-factor. That is, there are two positive constants c and C so that for p(n) = cn−1/a(H) almost surely G(n, p(n)) does not have an H-factor, whereas for p(n) = Cn−1/a(H), almost surely G(n, p(n)) contains an H-factor (provided h divides n). A special case of this answers a problem of Erdős.

We give results for the age-dependent distribution of vertex degree and number of vertices of given degree in the undirected web-graph process, a discrete random graph process introduced in [8]. For such processes we show that as $k \rightarrow \infty$, the expected proportion of vertices of degree $k$ has power law parameter $1+1/\eta$ where $\eta$ is the limiting ratio of the expected number of edge endpoints inserted by preferential attachment to the expected total degree. The proof for the undirected process generalizes naturally to give similar results for the directed hub-authority process, and an undirected hypergraph process.

We prove that the chromatic polynomial of a finite graph of maximal degree Δ is free of zeros for |q| ≥ C*(Δ) with This improves results by Sokal and Borgs. Furthermore, we present a strengthening of this condition for graphs with no triangle-free vertices.

We study the expected value of the length Ln of the minimum spanning tree of the complete graph Kn when each edge e is given an independent uniform [0, 1] edge weight. We sharpen the result of Frieze [6] that limn→∞$\mathbb{E}$(Ln) = ζ(3) and show that

$$ \mathbb{E}(L_n)=\zeta(3)+\frac{c_1}{n}+\frac{c_2+o(1)}{n^{4/3}}, $$

A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt. A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥ (t − 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, …, Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asymptotically. Furthermore, we consider a generalization to hypergraphs in terms of the codegree.