Starting from an n-by-n matrix of zeros, choose uniformly random zero entries and change them to ones, one at a time, until the matrix becomes invertible. We show that with probability tending to one as n → ∞, this occurs at the very moment the last zero row or zero column disappears. We prove a related result for random symmetric Bernoulli matrices, and give quantitative bounds for some related problems. These results extend earlier work by Costello and Vu [10].

An instance of a size-n stable marriage problem involves n men and n women, each individually ranking all members of opposite sex in order of preference as a potential marriage partner. A complete matching, a set of n marriages, is called stable if no unmatched man and woman prefer each other to their partners in the matching. It is known that, for every instance of marriage partner preferences, there exists at least one stable matching, and that there are instances with exponentially many stable matchings. Our focus is on a random instance chosen uniformly from among all (n!)2n possible instances. The second author had proved that the expected number of stable marriages is of order nlnn, while its likely value is of order n1/2−o(1) at least. In this paper the second moment of that number is shown to be of order (nlnn)2. The combination of the two moment estimates implies that the fraction of problem instances with roughly cnlnn solutions is at least 0.84. Whether this fraction is asymptotic to 1 remains an open question.

A family of sets is said to be intersecting if A ∩ B ≠ ∅ for all A, B ∈ . It is a well-known and simple fact that an intersecting family of subsets of [n] = {1, 2, . . ., n} can contain at most 2n−1 sets. Katona, Katona and Katona ask the following question. Suppose instead ⊂ [n] satisfies || = 2n−1 + i for some fixed i > 0. Create a new family p by choosing each member of independently with some fixed probability p. How do we choose to maximize the probability that p is intersecting? They conjecture that there is a nested sequence of optimal families for i = 1, 2,. . ., 2n−1. In this paper, we show that the families [n](≥r) = {A ⊂ [n]: |A| ≥ r} are optimal for the appropriate values of i, thereby proving the conjecture for this sequence of values. Moreover, we show that for intermediate values of i there exist optimal families lying between those we have found. It turns out that the optimal families we find simultaneously maximize the number of intersecting subfamilies of each possible order.

Standard compression techniques appear inadequate to solve the problem as they do not preserve intersection properties of subfamilies. Instead, our main tool is a novel compression method, together with a way of ‘compressing subfamilies’, which may be of independent interest.

We introduce a new graph polynomial that encodes interesting properties of graphs, for example, the number of matchings, the number of perfect matchings, and, for bipartite graphs, the number of independent sets (#BIS).

We analyse the complexity of exact evaluation of the polynomial at rational points and show a dichotomy result: for most points exact evaluation is #P-hard (assuming the generalized Riemann hypothesis) and for the rest of the points exact evaluation is trivial.

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.

An [n, k, r]-hypergraph is a hypergraph = (V, E) whose vertex set V is partitioned into n k-element sets V1, V2,…, Vn and for which, for each choice of r indices, 1 ≤ i1 < i2 < … < ir ≤ n, there is exactly one edge e ∈ E such that |e∩Vi| = 1 if i ∈ {i1, i2.…, ir} and otherwise |e ∩ Vi| = 0. An independent transversal of an [n, k, r]-hypergraph is a set T = {a1, a2,…, an} ⊆ V such that ai ∈ Vi for i = 1, 2, …, n and e ⊈ T for all e ∈ E. The purpose of this note is to estimate fr(k), defined as the largest n for which any [n, k, r]-hypergraph has an independent transversal. The sharpest results are for r = 2 and for the case when k is small compared to r.

In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast an n-bit word to n receivers (one bit per receiver), where the receivers have side information represented by a graph G. The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. For linear index coding, the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef, Birk, Jayram and Kol, IEEE Trans. Inform. Theory, 2011).

We show a polynomial-time algorithm that, given an n-vertex graph G with minrank k, finds a linear index code for G of length Õ(nf(k)), where f(k) depends only on k. For example, for k = 3 we obtain f(3) ≈ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan for graph colouring (J. Assoc. Comput. Mach., 1998) and its refined analysis due to Arora, Chlamtac and Charikar (STOC, 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is an upper bound on the objective value of the SDP in terms of the minrank.

At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovász ϑ-function of a graph with minrank k. This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.

For d ≥ 2, let Hd(n,p) denote a random d-uniform hypergraph with n vertices in which each of the $\binom{n}{d}$ possible edges is present with probability p=p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. Let either H=Hd(n,m) or H=Hd(n,p), where m/n and $\binom{n-1}{d-1}p$ need to be bounded away from (d−1)−1 and 0 respectively. We determine the asymptotic probability that H is connected. This yields the asymptotic number of connected d-uniform hypergraphs with given numbers of vertices and edges. We also derive a local limit theorem for the number of edges in Hd(n,p), conditioned on Hd(n,p) being connected.

Let ${P_s(d)}$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let ${E(d)}$ be the expected number of 0/1-vectors in the linear subspace spanned by $d-1$ random independent 0/1-vectors. (So ${E(d)}$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.)

We prove that bounds on ${P_s(d)}$ are equivalent to bounds on ${E(d)}$: \[{P_s(d)} = \bigg(2^{-d} {E(d)} + \frac{d^2}{2^{d+1}} \bigg) (1 + \so(1)). \] We also report on computational experiments pertaining to these numbers.

We study the asymptotic properties of a “uniform” random graph process in which the minimum degree of U(n, M) grows at least as fast as ⌊M/n⌋. We show that if M — n → → ∞, almost surely U(n, M) consists of one giant component and some number of small unicyclic components. We go on to study the distribution of cycles in unicyclic components as they emerge at the beginning of the process and disappear when captured by the giant one.

Consider the barycentric subdivision which cuts a given triangle along its medians to produce six new triangles. Uniformly choosing one of them and iterating this procedure gives rise to a Markov chain. We show that, almost surely, the triangles forming this chain become flatter and flatter in the sense that their isoperimetric values go to infinity with time. Nevertheless, if the triangles are renormalized through a similitude to have their longest edge equal to [0, 1] ⊂ ℂ (with 0 also adjacent to the shortest edge), their aspect does not converge and we identify the limit set of the opposite vertex with the segment [0, 1/2]. In addition we prove that the largest angle converges to π in probability. Our approach is probabilistic, and these results are deduced from the investigation of a limit iterated random function Markov chain living on the segment [0, 1/2]. The stationary distribution of this limit chain is particularly important in our study.

We consider partitions of the positive integer n whose parts satisfy the following condition. For a given sequence of non-negative numbers {bk}k≥1, a part of size k appears in exactly bk possible types. Assuming that a weighted partition is selected uniformly at random from the set of all such partitions, we study the asymptotic behaviour of the largest part Xn. Let D(s)=∑k=1∞bkk−s, s=σ+iy, be the Dirichlet generating series of the weights bk. Under certain fairly general assumptions, Meinardus (1954) obtained the asymptotic of the total number of such partitions as n→∞. Using the Meinardus scheme of conditions, we prove that Xn, appropriately normalized, converges weakly to a random variable having Gumbel distribution (i.e., its distribution function equals e−e−t, −∞<t<∞). This limit theorem extends some known results on particular types of partitions and on the Bose–Einstein model of ideal gas.

We consider the Widom–Rowlinson model of two types of interacting particles on d-regular graphs. We prove a tight upper bound on the occupancy fraction, the expected fraction of vertices occupied by a particle under a random configuration from the model. The upper bound is achieved uniquely by unions of complete graphs on d + 1 vertices, Kd+1. As a corollary we find that Kd+1 also maximizes the normalized partition function of the Widom–Rowlinson model over the class of d-regular graphs. A special case of this shows that the normalized number of homomorphisms from any d-regular graph G to the graph HWR, a path on three vertices with a loop on each vertex, is maximized by Kd+1. This proves a conjecture of Galvin.

We consider distance colourings in graphs of maximum degree at most d and how excluding one fixed cycle of length ℓ affects the number of colours required as d → ∞. For vertex-colouring and t ⩾ 1, if any two distinct vertices connected by a path of at most t edges are required to be coloured differently, then a reduction by a logarithmic (in d) factor against the trivial bound O(dt) can be obtained by excluding an odd cycle length ℓ ⩾ 3t if t is odd or by excluding an even cycle length ℓ ⩾ 2t + 2. For edge-colouring and t ⩾ 2, if any two distinct edges connected by a path of fewer than t edges are required to be coloured differently, then excluding an even cycle length ℓ ⩾ 2t is sufficient for a logarithmic factor reduction. For t ⩾ 2, neither of the above statements are possible for other parity combinations of ℓ and t. These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014).

Estimating numerically the spectral radius of a random walk on a non-amenable graph is complicated, since the cardinality of balls grows exponentially fast with the radius. We propose an algorithm to get a bound from below for this spectral radius in Cayley graphs with finitely many cone types (including for instance hyperbolic groups). In the genus 2 surface group, it improves by an order of magnitude the previous best bound, due to Bartholdi.

We prove that the number of 1324-avoiding permutations of length n is less than $(7+4\sqrt{3})^n$. The novelty of our method is that we injectively encode such permutations by a pair of words of length n over a finite alphabet that avoid a given factor.

A minimum feedback arc set of a directed graph G is a smallest set of arcs whose removal makes G acyclic. Its cardinality is denoted by β(G). We show that a simple Eulerian digraph with n vertices and m arcs has β(G) ≥ m2/2n2+m/2n, and this bound is optimal for infinitely many m, n. Using this result we prove that a simple Eulerian digraph contains a cycle of length at most 6n2/m, and has an Eulerian subgraph with minimum degree at least m2/24n3. Both estimates are tight up to a constant factor. Finally, motivated by a conjecture of Bollobás and Scott, we also show how to find long cycles in Eulerian digraphs.

Improving an old result of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl, we show that the number of distinct distances determined by a set $P$ of $n$ points in three-dimensional space is $\Omega(n^{77/141-\varepsilon})=\Omega(n^{0.546})$, for any $\varepsilon>0$. Moreover, there always exists a point $p\in P$ from which there are at least so many distinct distances to the remaining elements of $P$. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the Erdős–Szekeres theorem: For every k ≥ 1, every order-nk-dimensional permutation contains a monotone subsequence of length Ωk($\sqrt{n}$), and this is tight. On the other hand, and unlike the classical case, the longest monotone subsequence in a random k-dimensional permutation of order n is asymptotically almost surely Θk(nk/(k+1)).

We consider probability spaces which contain a family {EA[ratio ]A⊆{1, 2, …, n}, [mid ]A[mid ]=k} of events indexed by the k-element subsets of {1, 2, …, n}. A pair (A, B) of k-element subsets of {1, 2, …, n} is called a shift pair if the largest k−1 elements of A coincide with the smallest k−1 elements of B. For a shift pair (A, B), Pr[AB¯] is the probability that event EA is true and EB is false. We investigate how large the minimum value of Pr[AB¯], taken over all shift pairs, can be. As n→∞, this value converges to a number λk, with ½−1/2k+2[les ]λk[les ] ½−1/4k+2. We show that λk is a strictly increasing function of k, with λ1=¼ and λ2=1/3.

For k=1, our results have the following natural interpretation. If a fair coin is tossed repeatedly, and event Ei is true when the ith toss is heads, then for all i and j with i<j, Pr[EiĒj]=¼. Furthermore, as we show in this paper, for any ε>0, there is an n such that for any sequence E1, E2, …, En of events in an arbitrary probability space, there are indices i<j with Pr[EiĒj]<¼+ε. The results and techniques we develop in this research, together with further applications of Ramsey theory, are then used to show that the supremum of fractional dimensions of interval orders is exactly 4, answering a question of Brightwell and Scheinerman.

Generalizing the ¼+ε result to random variables X1, X2, …, Xn with values in an m-element set, we obtain a finite version of de Finetti's theorem without the exchangeability hypothesis: for any fixed m, k and ε, every sufficiently long sequence of such random variables has a length-k subsequence at variation distance less than ε from an i.i.d. mix.