We show that the maximum number of convex polygons in a triangulation of n points in the plane is O(1.5029n). This improves an earlier bound of O(1.6181n) established by van Kreveld, Löffler and Pach (2012), and almost matches the current best lower bound of Ω(1.5028n) due to the same authors. Given a planar straight-line graph G with n vertices, we also show how to compute efficiently the number of convex polygons in G.

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Ω(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.

Scott conjectured in [6] that the class of graphs with no induced subdivision of a given graph is χ-bounded. We verify his conjecture for maximal triangle-free graphs.

A set of points in d-dimensional Euclidean space is almost equidistant if, among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in ℝd has cardinality O(d4/3).

We derive area limit laws for the various symmetry classes of staircase polygons on the square lattice, in a uniform ensemble where, for fixed perimeter, each polygon occurs with the same probability. This complements a previous study by Leroux and Rassart, where explicit expressions for the area and perimeter generating functions of these classes have been derived.

We prove a number of results related to a problem of Po-Shen Loh [9], which is equivalent to a problem in Ramsey theory. Let a = (a1, a2, a3) and b = (b1, b2, b3) be two triples of integers. Define a to be 2-less than b if ai < bi for at least two values of i, and define a sequence a1, …, am of triples to be 2-increasing if ar is 2-less than as whenever r < s. Loh asks how long a 2-increasing sequence can be if all the triples take values in {1, 2, …, n}, and gives a log* improvement over the trivial upper bound of n2 by using the triangle removal lemma. In the other direction, a simple construction gives a lower bound of n3/2. We look at this problem and a collection of generalizations, improving some of the known bounds, pointing out connections to other well-known problems in extremal combinatorics, and asking a number of further questions.

Improving upon work in [2], the precise value of the set reconstruction number is given for all cyclic groups of odd order.

Given a finite set $A \subseteq \mathbb{R}^d$, points $a_1,a_2,\dotsc,a_{\ell} \in A$ form an $\ell$-hole in A if they are the vertices of a convex polytope, which contains no points of A in its interior. We construct arbitrarily large point sets in general position in $\mathbb{R}^d$ having no holes of size $O(4^dd\log d)$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. The basic version of our construction uses a certain type of equidistributed point sets, originating from numerical analysis, known as (t,m,s)-nets or (t,s)-sequences, yielding a bound of $2^{7d}$. The better bound is obtained using a variant of (t,m,s)-nets, obeying a relaxed equidistribution condition.

We show that, for a constant-degree algebraic curve γ in ℝD, every set of n points on γ spans at least Ω(n4/3) distinct distances, unless γ is an algebraic helix, in the sense of Charalambides [2]. This improves the earlier bound Ω(n5/4) of Charalambides [2].

We also show that, for every set P of n points that lie on a d-dimensional constant-degree algebraic variety V in ℝD, there exists a subset S ⊂ P of size at least Ω(n4/(9+12(d−1))), such that S spans $\left({\begin{array}{*{20}{c}} {|S|} \\ 2 \\\end{array}} \right)$ distinct distances. This improves the earlier bound of Ω(n1/(3d)) of Conlon, Fox, Gasarch, Harris, Ulrich and Zbarsky [4].

Both results are consequences of a common technical tool.

Let k be a positive integer, k ≥ 2. In this paper we study bipartite graphs G such that, for n sufficiently large, each two-coloring of the edges of the complete graph Kn gives a monochromatic copy of G, with some k of its vertices having the maximum degree of these k vertices minus the minimum degree of these k vertices (in the colored Kn) at most k − 2.

The partition number of a product hypergraph is introduced as the minimal size of a partition of its vertex set into sets that are edges. This number is shown to be multiplicative if all factors are graphs with all loops included.

The goal of property testing is to quickly distinguish between objects which satisfy a property and objects that are ε-far from satisfying the property. There are now several general results in this area which show that natural properties of combinatorial objects can be tested with ‘constant’ query complexity, depending only on ε and the property, and not on the size of the object being tested. The upper bound on the query complexity coming from the proof techniques is often enormous and impractical. It remains a major open problem if better bounds hold.

Maybe surprisingly, for testing with respect to the rectangular distance, we prove there is a universal (not depending on the property), polynomial in 1/ε query complexity bound for two-sided testing hereditary properties of sufficiently large permutations. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden subpermutation for the property. Finally, we show that several different permutation metrics of interest are related to the rectangular distance, yielding similar results for testing with respect to these metrics.

Lemke and Kleitman [2] showed that, given a positive integer d and d (necessarily non-distinct) divisors of da1, …, ad there exists a subset Q ⊆ {1, …, d} such that d = [sum ]i∈Qai answering a conjecture of Erdo″s and Lemke. Here we extend this result, showing that, provided [sum ]p|d1/p [les ] 1 (where the sum is taken over all primes p), there is some collection from a1, …, ad which both sum to d and which can themselves be ordered so that each element divides its successor in the order. Furthermore, we shall show that the condition on the prime divisors is in some sense also necessary.

A random interval graph of order n is generated by picking 2n numbers X1,…,X2n independently from the uniform distribution on [0,1] and considering the collection of n intervals with endpoints X2i−1 and X2i for i ∈ {1,…,n}. The graph vertices correspond to intervals. Two vertices are connected if the corresponding intervals intersect. This paper characterizes the fluctuations of the independence number in random interval graphs. This characterization is obtained through the analysis of the greedy algorithm. We actually prove limit theorems (central limit theorem and large deviation principle) on the number of phases of this greedy algorithm. The proof relies on the analysis of first-passage times through a random level.

Consider the following communication problem, which leads to a new notion of edge colouring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the transmitters and the nodes on the other side are the receivers. The edges correspond to messages, and every edge e is associated with an integer c(e), corresponding to the time it takes the message to reach its destination. A proper k-edge-colouring with delays is a function f from the edges to {0, 1, . . ., k − 1}, such that, for every two edges e1 and e2 with the same transmitter, f(e1) ≠ f(e2), and for every two edges e1 and e2 with the same receiver, f(e1) + c(e1) ≢ f(e2) + c(e2) (mod k). Ross, Bambos, Kumaran, Saniee and Widjaja [18] conjectured that there always exists a proper edge colouring with delays using k = Δ + o(Δ) colours, where Δ is the maximum degree of the graph. Haxell, Wilfong and Winkler [11] conjectured that a stronger result holds: k = Δ + 1 colours always suffice. We prove the weaker conjecture for simple bipartite graphs, using a probabilistic approach, and further show that the stronger conjectureholds for some multigraphs, applying algebraic tools.

We establish a relation between two uniform models of random k-graphs (for constant k ⩾ 3) on n labelled vertices: ℍ(k)(n,m), the random k-graph with exactly m edges, and ℍ(k)(n,d), the random d-regular k-graph. By extending the switching technique of McKay and Wormald to k-graphs, we show that, for some range of d = d(n) and a constant c > 0, if m ~ cnd, then one can couple ℍ(k)(n,m) and ℍ(k)(n,d) so that the latter contains the former with probability tending to one as n → ∞. In view of known results on the existence of a loose Hamilton cycle in ℍ(k)(n,m), we conclude that ℍ(k)(n,d) contains a loose Hamilton cycle when d ≫ log n (or just d ⩾ C log n, if k = 3) and d = o(n1/2).

It was conjectured by Bartels and Welsh [1] that removing an edge from an n-vertex graph G will not increase the average number of colours in the proper colourings of G if k=n colours are available. This paper shows that for all n>3, and for each k∈{3, 4, …, [lfloor ](3n−6)/2[rfloor ]}, there is a graph on n vertices with an edge whose removal increases the average number of colours in the k-colourings, thus disproving the conjecture.

A univariate polynomial f over a field is decomposable if it is the composition f = g ○ h of two polynomials g and h whose degree is at least 2. We determine an approximation to the number of decomposables over a finite field. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood, and we obtain exponentially decreasing relative error bounds. The wild case, where p divides n, is more challenging and our error bounds are weaker.

We consider the near-critical Erdős–Rényi random graph G(n, p) and provide a new probabilistic proof of the fact that, when p is of the form $p=p(n)=1/n+\lambda/n^{4/3}$ and A is large,

\begin{equation*}\mathbb{P}(|\mathcal{C}_{\max}|>An^{2/3})\asymp A^{-3/2}e^{-\frac{A^3}{8}+\frac{\lambda A^2}{2}-\frac{\lambda^2A}{2}},\end{equation*}

$\mathcal{C}_{\max}$

$\lambda$

We prove the following metric Ramsey theorem. For any connected graph G endowed with a linear order on its vertex set, there exists a graph R such that in every colouring of the t-sets of vertices of R it is possible to find a copy G* of G inside R satisfying:

• • distG*(x, y) = distR(x, y) for every x, y ∈ V(G*);

• • the colour of each t-set in G* depends only on the graph-distance metric induced in G by the ordered t-set.