We upper-bound the number of common zeros over a finite grid of multivariate polynomials and an arbitrary finite collection of their consecutive Hasse derivatives (in a coordinate-wise sense). To that end, we make use of the tool from Gröbner basis theory known as footprint. Then we establish and prove extensions in this context of a family of well-known results in algebra and combinatorics. These include Alon's combinatorial Nullstellensatz [1], existence and uniqueness of Hermite interpolating polynomials over a grid, estimations of the parameters of evaluation codes with consecutive derivatives [20], and bounds on the number of zeros of a polynomial by DeMillo and Lipton [8], Schwartz [25], Zippel [26, 27] and Alon and Füredi [2]. As an alternative, we also extend the Schwartz-Zippel bound to weighted multiplicities and discuss its connection to our extension of the footprint bound.

We extend a recent argument of Kahn, Narayanan and Park ((2021) Proceedings of the AMS 149 3201–3208) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of $C_4$ that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning $K_r$-cycles.

Two graphs G1 and G2 on n vertices are said to pack if there exist injective mappings of their vertex sets into [n] such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobás and Eldridge and, independently, Catlin, asserts that if (Δ(G1) + 1)(Δ(G2) + 1) ⩽ n + 1, then G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t ⩾ 2 that if G1 contains no copy of the complete bipartite graph K2,t and Δ(G1) > 17t · Δ(G2), then (Δ(G1) + 1)(Δ(G2) + 1) ⩽ n + 1 implies that G1 and G2 pack. We also provide a mild improvement if moreover G2 contains no copy of the complete tripartite graph K1,1,s, s ⩾ 1.

Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations $Ax = b$, where the coordinates of the vector x are restricted to take values in some small subset (e.g. $\{\pm 1\}$) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of $n\times n$ Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random $\{\pm 1\}$ matrix.

We prove a generalmulti-dimensional central limit theorem for the expected number of vertices of a given degree in the family of planar maps whose vertex degrees are restricted to an arbitrary (finite or infinite) set of positive integers D. Our results rely on a classical bijection with mobiles (objects exhibiting a tree structure), combined with refined analytic tools to deal with the systems of equations on infinite variables that arise. We also discuss possible extensions to maps of higher genus and to weighted maps.

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha \gt 0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$. Our proofs make use of a variant of an absorbing method of Montgomery.

We find an asymptotic enumeration formula for the number of simple $r$ -uniform hypergraphs with a given degree sequence, when the number of edges is sufficiently large. The formula is given in terms of the solution of a system of equations. We give sufficient conditions on the degree sequence which guarantee existence of a solution to this system. Furthermore, we solve the system and give an explicit asymptotic formula when the degree sequence is close to regular. This allows us to establish several properties of the degree sequence of a random $r$ -uniform hypergraph with a given number of edges. More specifically, we compare the degree sequence of a random $r$ -uniform hypergraph with a given number edges to certain models involving sequences of binomial or hypergeometric random variables conditioned on their sum.

Yahya ould Hamidoune passed away in Paris on 11 March 2011 after a brief illness, leaving insufficient time for his friends and colleagues to express their indebtedness to him for his kindness and generosity, both in mathematics and in everyday life. Yahya was a discreet individual, always looking for the essential rather than the superficial, and certainly did not receive the recognition he deserved. May this modest testimony render justice to this singular man.

We consider the component structure of the random digraph D(n,p) inside the critical window $p = n^{-1} + \lambda n^{-4/3}$ . We show that the largest component $\mathcal{C}_1$ has size of order $n^{1/3}$ in this range. In particular we give explicit bounds on the tail probabilities of $|\mathcal{C}_1|n^{-1/3}$ .

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$.

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.

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.

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.).

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.

We provide a deterministic algorithm that finds, in ɛ-O(1)n2 time, an ɛ-regular Frieze–Kannan partition of a graph on n vertices. The algorithm outputs an approximation of a given graph as a weighted sum of ɛ-O(1) many complete bipartite graphs.

As a corollary, we give a deterministic algorithm for estimating the number of copies of H in an n-vertex graph G up to an additive error of at most ɛnv(H), in time ɛ-OH(1)n2.

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.

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.

For a subgraph $G$ of the blow-up of a graph $F$ , we let $\delta ^*(G)$ be the smallest minimum degree over all of the bipartite subgraphs of $G$ induced by pairs of parts that correspond to edges of $F$ . Johansson proved that if $G$ is a spanning subgraph of the blow-up of $C_3$ with parts of size $n$ and $\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$ , then $G$ contains $n$ vertex disjoint triangles, and presented the following conjecture of Häggkvist. If $G$ is a spanning subgraph of the blow-up of $C_k$ with parts of size $n$ and $\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$ , then $G$ contains $n$ vertex disjoint copies of $C_k$ such that each $C_k$ intersects each of the $k$ parts exactly once. A similar conjecture was also made by Fischer and the case $k=3$ was proved for large $n$ by Magyar and Martin.

In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of $G$ to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically.

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.

Let $F\,{=}\,\{H_1,\ldots,H_k\}$ be a family of graphs. A graph $G$ is called totally$F$-decomposable if for every linear combination of the form $\alpha_1 e(H_1) \,{+}\,{\cdots}\,{+}\,\alpha_k e(H_k) \,{=}\, e(G)$ where each $\alpha_i$ is a nonnegative integer, there is a colouring of the edges of $G$ with $\alpha_1\,{+}\,{\cdots}\,{+}\,\alpha_k$ colours such that exactly $\alpha_i$ colour classes induce each a copy of $H_i$, for $i\,{=}\,1,\ldots,k$. We prove that if $F$ is any fixed nontrivial family of trees then $\log n/n$ is a sharp threshold function for the property that the random graph $G(n,p)$ is totally $F$-decomposable. In particular, if $H$ is a tree with more than one edge, then $\log n/n$ is a sharp threshold function for the property that $G(n,p)$ contains $\lfloor e(G)/e(H) \rfloor$ edge-disjoint copies of $H$.