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.

We introduce a discrete random process which we call the passenger model, and show that it is connected to a certain random model of the assignment problem and in particular to the so-called Buck–Chan–Robbins urn process. We propose a conjecture on the distribution of the location of the minimum cost assignment in a cost matrix with zeros at specified positions and remaining entries of exponential distribution. The conjecture is consistent with earlier results on the participation probability of an individual matrix entry. We also use the passenger model to verify a conjecture by V. Dotsenko on the assignment problem.

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.

The Ramsey Schur number $RS(s,t)$ is the smallest $n$ such that every 2-colouring of the edges of $K_n$ with vertices $1,2,\ldots,n$ contains a green $K_s$ or there are vertices $x_1,x_2,\ldots,x_t$ fulfilling the equation $x_1+x_2+\cdots+x_{t-1}=x_t$ and all edges $(x_i,x_j)$ are red. We prove $RS(3,3)=11, RS(3,t)=t^2-3$ for $t\equiv1\ (\mbox{mod}\ 6)$ and $t=8$, and $RS(3,t)\geq t^2-3$.

In this work we analyse bucket increasing tree families. We introduce two simple stochastic growth processes, generating random bucket increasing trees of size n, complementing the earlier result of Mahmoud and Smythe (1995, Theoret. Comput. Sci.144 221–249.) for bucket recursive trees. On the combinatorial side, we define multilabelled generalisations of the tree families d-ary increasing trees and generalised plane-oriented recursive trees. Additionally, we introduce a clustering process for ordinary increasing trees and relate it to bucket increasing trees. We discuss in detail the bucket size two and present a bijection between such bucket increasing tree families and certain families of graphs called increasing diamonds, providing an explanation for phenomena observed by Bodini et al. (2016, Lect. Notes Comput. Sci.9644 207–219.). Concerning structural properties of bucket increasing trees, we analyse the tree parameter $K_n$ . It counts the initial bucket size of the node containing label n in a tree of size n and is closely related to the distribution of node types. Additionally, we analyse the parameters descendants of label j and degree of the bucket containing label j, providing distributional decompositions, complementing and extending earlier results (Kuba and Panholzer (2010), Theoret. Comput. Sci.411(34–36) 3255–3273.).

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.

This paper begins with the observation that half of all graphs containing no induced path of length 3 are disconnected. We generalize this in several directions. First, we give necessary and sufficient conditions (in terms of generating functions) for the probability of connectedness in a suitable class of graphs to tend to a limit strictly between zero and one. Next we give a general framework in which this and related questions can be posed, involving operations on classes of finite structures. Finally, we discuss briefly an algebra associated with such a class of structures, and give a conjecture about its structure.

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.

Coding in a new metric space, called the Enomoto-Katona space, has recently been considered in connection with the study of implication structures of functional dependencies and their generalizations in relational databases. The central problem is the determination of C(n,k,d), the size of an optimal code of length n, weight k, and distance d in the Enomoto-Katona space. The value of C(n,k,d) was known only for some congruence classes of n when (k,d) ∈ {(2,3),(3,5)}. In this paper, we obtain new infinite families of optimal codes in the Enomoto-Katona space and verify a conjecture of Brightwell and Katona in certain instances. In particular, C(n,k, 2k − 1) is determined for all sufficiently large n satisfying either n ≡ 1 mod k and n(n − 1) ≡ 0 mod 2k2, or n ≡ 0 mod k. We also give complete solutions for k = 2 and determine C(n,3,5) for certain congruence classes of n with finite exceptions.

Let X be a vertex-transitive graph and let S be an arbitrary finite subset of its vertices. Denote by @∂S the set of vertices adjacent to S but not in S. Babai and Szegedy proved that for an infinite, connected, locally finite X with subexponential growth we have

formula here

where d(S) is the diameter of S. The aim of this note is to provide a slightly better, tight lower bound on this quantity. We prove that

formula here

under the same conditions.

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.

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.

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.

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.

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.

Analogues of the Erdős-Ko-Rado theorem are proved for the Boolean algebra of all subsets of {1,…n} and in this algebra truncated by the removal of the empty set and the whole set.

We analyse the weighted height of random tries built from independent strings of i.i.d. symbols on the finite alphabet {1, . . .d}. The edges receive random weights whose distribution depends upon the number of strings that visit that edge. Such a model covers the hybrid tries of de la Briandais and the TST of Bentley and Sedgewick, where the search time for a string can be decomposed as a sum of processing times for each symbol in the string. Our weighted trie model also permits one to study maximal path imbalance. In all cases, the weighted height is shown to be asymptotic to c log n in probability, where c is determined by the behaviour of the core of the trie (the part where all nodes have a full set of children) and the fringe of the trie (the part of the trie where nodes have only one child and form spaghetti-like trees). It can be found by maximizing a function that is related to the Cramér exponent of the distribution of the edge weights.