We study the problem of learning k-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function f: {−1, 1}n → {−1, 1} that depends on k (unknown) coordinates. While the best-known algorithms for the general problem of learning a k-junta require running times of nk poly(n, 2k), we show that, given access to k different product distributions with biases separated by γ > 0, the functions may be learned in time poly(n, 2k, γ−k). More generally, given access to t ≤ k different product distributions, the functions may be learned in time nk/tpoly(n, 2k, γ−k). Our techniques involve novel results in Fourier analysis, relating Fourier expansions with respect to different biases, and a generalization of Russo's formula.

We consider samples of n geometric random variables with parameter 0 < p < 1, and study the largest missing value, that is, the highest value of such a random variable, less than the maximum, that does not appear in the sample. Asymptotic expressions for the mean and variance for this quantity are presented. We also consider samples with the property that the largest missing value and the largest value which does appear differ by exactly one, and call this the LMV property. We find the probability that a sample of n variables has the LMV property, as well as the mean for the average largest value in samples with this property. The simpler special case of p = 1/2 has previously been studied, and verifying that the results of the present paper coincide with those previously found for p = 1/2 leads to some interesting identities.

The expectation of the descent number of a random Young tableau of a fixed shape is given, and concentration around the mean is shown. This result is generalized to the major index and to other descent functions. The proof combines probabilistic arguments together with combinatorial character theory. Connections with Hecke algebras are mentioned.

Let M be an n × m matrix of independent Rademacher (±1) random variables. It is well known that if $n \leq m$, then M is of full rank with high probability. We show that this property is resilient to adversarial changes to M. More precisely, if $m \ge n + {n^{1 - \varepsilon /6}}$, then even after changing the sign of (1 – ε)m/2 entries, M is still of full rank with high probability. Note that this is asymptotically best possible as one can easily make any two rows proportional with at most m/2 changes. Moreover, this theorem gives an asymptotic solution to a slightly weakened version of a conjecture made by Van Vu in [17].

We present an average-case analysis of a variant of dual-pivot quicksort. We show that the algorithmic partitioning strategy used is optimal, that is, it minimizes the expected number of key comparisons. For the analysis, we calculate the expected number of comparisons exactly as well as asymptotically; in particular, we provide exact expressions for the linear, logarithmic and constant terms.

An essential step is the analysis of zeros of lattice paths in a certain probability model. Along the way a combinatorial identity is proved.

Define the Linus sequence Ln for n ≥ 1 as a 0–1 sequence with L1 = 0, and Ln chosen so as to minimize the length of the longest immediately repeated block Ln−2r+1 ⋅⋅⋅ Ln−r = Ln−r+1 ⋅⋅⋅ Ln. Define the Sally sequence Sn as the length r of the longest repeated block that was avoided by the choice of Ln. We prove several results about these sequences, such as exponential decay of the frequency of highly periodic subwords of the Linus sequence, zero entropy of any stationary process obtained as a limit of word frequencies in the Linus sequence and infinite average value of the Sally sequence. In addition we make a number of conjectures about both sequences.

An abelian processor is an automaton whose output is independent of the order of its inputs. Bond and Levine have proved that a network of abelian processors performs the same computation regardless of processing order (subject only to a halting condition). We prove that any finite abelian processor can be emulated by a network of certain very simple abelian processors, which we call gates. The most fundamental gate is a toppler, which absorbs input particles until their number exceeds some given threshold, at which point it topples, emitting one particle and returning to its initial state. With the exception of an adder gate, which simply combines two streams of particles, each of our gates has only one input wire, which sends letters (‘particles’) from a unary alphabet. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from ℕk to ℕℓ that is the sum of a linear function and a periodic function can be expressed in terms of (possibly nested) sums of floors of quotients by integers.

Let P10\e be the graph obtained by deleting an edge from the Petersen graph. We give a decomposition theorem for cubic graphs with no minor isomorphic to P10\e. The decomposition is used to show that graphs in this class are 3-edge-colourable. We also consider an application to a conjecture due to Grötzsch which states that a planar graph is 3-edge-colourable if and only if it is fractionally 3-edge-colourable.

A family of vectors in [k]n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [k]n invariant under a transitive group of symmetries is o(kn), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets.

In a previous paper we found a relation between the ranks of co-diagonal matrices (matrices with zeroes in their diagonal and nonzeroes elsewhere) and the quality of explicit Ramsey graph constructions. We also gave a construction based on the BBR polynomial of Barrington, Beigel and Rudich. In the present work we give another construction for low-rank co-diagonal matrices, based on a modular sieve formula.

Let $V$ be a finite-dimensional vector space over $\mathbb{F}_p$ . We say that a multilinear form $\alpha \colon V^k \to \mathbb{F}_p$ in $k$ variables is $d$ -approximately symmetric if the partition rank of difference $\alpha (x_1, \ldots, x_k) - \alpha (x_{\pi (1)}, \ldots, x_{\pi (k)})$ is at most $d$ for every permutation $\pi \in \textrm{Sym}_k$ . In a work concerning the inverse theorem for the Gowers uniformity $\|\!\cdot\! \|_{\mathsf{U}^4}$ norm in the case of low characteristic, Tidor conjectured that any $d$ -approximately symmetric multilinear form $\alpha \colon V^k \to \mathbb{F}_p$ differs from a symmetric multilinear form by a multilinear form of partition rank at most $O_{p,k,d}(1)$ and proved this conjecture in the case of trilinear forms. In this paper, somewhat surprisingly, we show that this conjecture is false. In fact, we show that approximately symmetric forms can be quite far from the symmetric ones, by constructing a multilinear form $\alpha \colon \mathbb{F}_2^n \times \mathbb{F}_2^n \times \mathbb{F}_2^n \times \mathbb{F}_2^n \to \mathbb{F}_2$ which is 3-approximately symmetric, while the difference between $\alpha$ and any symmetric multilinear form is of partition rank at least $\Omega (\sqrt [3]{n})$ .

We develop lower bounds on the Hadwiger number h(G) of graphs G with high chromatic number. In particular, if G has n vertices and chromatic number k then h(G) ≥ (4k − n)/3.

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.

In the paper we develop an approach to asymptotic normality through factorial cumulants. Factorial cumulants arise in the same manner from factorial moments as do (ordinary) cumulants from (ordinary) moments. Another tool we exploit is a new identity for ‘moments’ of partitions of numbers. The general limiting result is then used to (re-)derive asymptotic normality for several models including classical discrete distributions, occupancy problems in some generalized allocation schemes and two models related to negative multinomial distribution.

A set of vertices in a graph is a Hamiltonian subset if it induces a subgraph containing a Hamiltonian cycle. Kim, Liu, Sharifzadeh, and Staden proved that for large $d$, among all graphs with minimum degree $d$, $K_{d+1}$ minimises the number of Hamiltonian subsets. We prove a near optimal lower bound that takes also the order and the structure of a graph into account. For many natural graph classes, it provides a much better bound than the extremal one ($\approx 2^{d+1}$). Among others, our bound implies that an $n$-vertex $C_4$-free graph with minimum degree $d$ contains at least $n2^{d^{2-o(1)}}$ Hamiltonian subsets.

It is well known that, when normalized by n, the expected length of a longest common subsequence of d sequences of length n over an alphabet of size σ converges to a constant γσ,d. We disprove a speculation by Steele regarding a possible relation between γ2,d and γ2,2. In order to do that we also obtain some new lower bounds for γσ,d, when both σ and d are small integers.

We show that a coupling of non-colliding simple random walkers on the complete graph on n vertices can include at most n - log n walkers. This improves the only previously known upper bound of n - 2 due to Angel, Holroyd, Martin, Wilson and Winkler (Electron. Commun. Probab.18 (2013)). The proof considers couplings of i.i.d. sequences of Bernoulli random variables satisfying a similar avoidance property, for which there is separate interest.

We develop a theory of graph algebras over general fields. This is modelled after the theory developed by Freedman et al. (2007, J. Amer. Math. Soc.20 37–51) for connection matrices, in the study of graph homomorphism functions over real edge weight and positive vertex weight. We introduce connection tensors for graph properties. This notion naturally generalizes the concept of connection matrices. It is shown that counting perfect matchings, and a host of other graph properties naturally defined as Holant problems (edge models), cannot be expressed by graph homomorphism functions with both complex vertex and edge weights (or even from more general fields). Our necessary and sufficient condition in terms of connection tensors is a simple exponential rank bound. It shows that positive semidefiniteness is not needed in the more general setting.

An old conjecture of Erdős and McKay states that if all homogeneous sets in an $n$ -vertex graph are of order $O(\!\log n)$ then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$ . We prove a bipartite analogue of the conjecture: if all balanced homogeneous sets in an $n \times n$ bipartite graph are of order $O(\!\log n)$ , then the graph contains induced subgraphs of each size from $\{0,1,\ldots, \Omega \big(n^2\big)\}$ .