We study factor of i.i.d. processes on the d-regular tree for d ≥ 3. We show that if such a process is restricted to two distant connected subgraphs of the tree, then the two parts are basically uncorrelated. More precisely, any functions of the two parts have correlation at most $k(d-1) / (\sqrt{d-1})^k$, where k denotes the distance between the subgraphs. This result can be considered as a quantitative version of the fact that factor of i.i.d. processes have trivial 1-ended tails.

We prove χ′s(G) ≤ 1.93 Δ(G)2 for graphs of sufficiently large maximum degree where χ′s(G) is the strong chromatic index of G. This improves an old bound of Molloy and Reed. As a by-product, we present a Talagrand-type inequality where we are allowed to exclude unlikely bad outcomes that would otherwise render the inequality unusable.

Bollobás and Scott (Random Struct. Alg.21 (2002) 414–430) asked for conditions that guarantee a bisection of a graph with m edges in which each class has at most (1/4+o(1))m edges. We demonstrate that cycles of length 4 play an important role for this question. Let G be a graph with m edges, minimum degree δ, and containing no cycle of length 4. We show that if (i) G is 2-connected, or (ii) δ ⩾ 3, or (iii) δ ⩾ 2 and the girth of G is at least 5, then G admits a bisection in which each class has at most (1/4+o(1))m edges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollobás, Krivelevich and Sudakov shows that for infinitely many m there exists a graph with m edges and girth at least 5 for which any bisection has at least (1/4−o(1))m edges in one of the two classes.

A family of subsets of {1,. . .,n} is called intersecting if any two of its sets intersect. A classical result in extremal combinatorics due to Erdős, Ko and Rado determines the maximum size of an intersecting family of k-subsets of {1,. . .,n}. In this paper we study the following problem: How many intersecting families of k-subsets of {1,. . .,n} are there? Improving a result of Balogh, Das, Delcourt, Liu and Sharifzadeh, we determine this quantity asymptotically for n ≥ 2k+2+2$\sqrt{k\log k}$ and k → ∞. Moreover, under the same assumptions we also determine asymptotically the number of non-trivial intersecting families, that is, intersecting families for which the intersection of all sets is empty. We obtain analogous results for pairs of cross-intersecting families.

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 identify a relationship between a certain family of random walks on Euclidean lattices and difference matrices over cyclic groups. We then use the techniques of Fourier analysis to estimate the return probabilities of these random walks, which in turn yields the asymptotic number of difference matrices over cyclic groups as the number of columns increases.

Let hom(G) denote the size of the largest clique or independent set of a graph G. In 2007, Bukh and Sudakov proved that every n-vertex graph G with hom(G) = O(logn) contains an induced subgraph with Ω(n1/2) distinct degrees, and raised the question of deciding whether an analogous result holds for every n-vertex graph G with hom(G) = O(nϵ), where ϵ > 0 is a fixed constant. Here, we answer their question in the affirmative and show that every graph G on n vertices contains an induced subgraph with Ω((n/hom(G))1/2) distinct degrees. We also prove a stronger result for graphs with large cliques or independent sets and show, for any fixed k ∈ ℕ, that if an n-vertex graph G contains no induced subgraph with k distinct degrees, then hom(G)⩾n/(k − 1) − o(n); this bound is essentially best possible.

Finding a hidden partition in a random environment is a general and important problem which contains as subproblems many important questions, such as finding a hidden clique, finding a hidden colouring, finding a hidden bipartition, etc.

In this paper we provide a simple SVD algorithm for this purpose, addressing a question of McSherry. This algorithm is easy to implement and works for sparse graphs under optimal density assumptions. We also consider an approximating algorithm, which on one hand works under very mild assumptions, but on other hand can sometimes be upgraded to give the exact solution.