Quasirandom Graphs and the Pantograph Equation

Abstract

The pantograph differential equation and its solution, the deformed exponential function, are remarkable objects that appear in areas as diverse as combinatorics, number theory, statistical mechanics, and electrical engineering. In this article, we describe a new surprising application of these objects in graph theory, by showing that the set of all cliques is not forcing for quasirandomness. This provides a natural example of an infinite family of graphs, which is not forcing, and answers a natural question posed by P. Horn.

Keywords:

• MSC: Primary 05C35
• Secondary 05C80
• 30D20

1 The pantograph equation and its solution

The best-known differential equation$$y^{\prime }(x)=py(x),y(0)=1$$

is solved by the exponential function $y=e^{px}$. Consider a visually similar but very different equation$$y\prime (x)=y(px),y(0)=1,$$where $0<p\le 1$. This is a special case of the pantograph equation, one of the most studied examples of delay differential equations, where the value of the derivative of y at time x is a function of the value of y at an earlier time px. The pantograph equation owes its name to a component of the electric locomotive, connecting it to the overhead wire, and was first studied in the late 1960s by British Railways. The equation results from the study of the pantograph’s movement, where it is crucial that the pantograph stays in constant contact with the wire, in order to collect current for the locomotive without interruptions; see Griebel [4] for more historical and physics background.

The pantograph equation and its generalizations have found many applications in physics [10] and mathematics. It can be verified that its unique solution is the so-called deformed exponential function (1) $$f_p(x)=\sum _{j=0}^{\infty }\frac{x^j}{j!}{p}^{\left(\begin{array}{c}j\\ 2\end{array}\right)}=1+x+\frac{x^2}{2}p+\frac{x^3}{6}{p}^3+\cdots ;$$(1) note that when p = 1 we have $f_1(x)=e^x$, hence the name. In fact, the deformed exponential was first studied by Mahler [12], nearly 30 years before the pantograph equation made an appearance. Mahler’s motivation was in number theory: he used the function f_p to derive an asymptotic formula for the number of partitions of a large integer n into powers of a fixed integer r. Later the deformed exponential was found to appear naturally in many other contexts. In combinatorics it is connected to the Tutte polynomial of complete graphs [22], the enumeration of acyclic digraphs [16], and inversions of trees [13]. In statistical mechanics the function f_p appears as the partition function of one-site lattice gas [17], and in complex analysis it is related to the Whittaker and Goncharov constants [1]. The function f_p continues to be the focus of current research; see, for example, the recent paper [23] which studies the asymptotics of its roots.

In this article, we present an unexpected application of certain properties of the deformed exponential function to the theory of quasirandom graphs.

2 Quasirandom graphs and forcing families

Quasirandomness, or pseudorandomness, is a phenomenon occurring in several areas of discrete mathematics: number theory, group theory, combinatorics, and graph theory. It can be loosely described as the study of properties of truly random objects in deterministic ones; see [21] for a general survey, and [7] for a survey on pseudorandom graphs.

Let us first focus on counting copies of a fixed small graph H inside a large graph G. It will be more convenient to count labeled copies, that is, injective mappings from the vertex set of H to that of G that map edges to edges. Let us illustrate this with some examples.

Example 1.

If G is a complete bipartite graph¹ with both parts of size $n/2$, where n is a large even number, and H is a star with k edges, i.e., a complete bipartite graph with part sizes 1 and k, then G contains$$n·\frac{n}{2}\left(\frac{n}{2}-1\right)\cdots \left(\frac{n}{2}-k+1\right)=(1+o(1))2^{-k}{n}^{k+1}$$

labeled copies of H.

In the above example, as well as throughout the rest of the article, any o(1) expression should be read as a function tending to 0 as n goes to $\infty$. The $o()$-notation is an equivalent, yet more convenient-to-use form of the usual ϵ-δ-n₀ formalism. In particular, we can use multiple o(1)-expressions in the same formula, saving us the need to introduce multiple ϵ’s (two o(1)-expressions are not assumed to be identical). Note that here and later the $o()$-notation assumes that n tends to infinity and treats all other variables (e.g., k in Example 1) as constant parameters.

Example 2.

If G is a clique² on pn vertices, where n is large and $0<p\le 1$, and H is a cycle of length k, then G has$$pn(pn-1)\cdots (pn-k+1)=(1+o(1))p^k{n}^k$$

labeled copies of H.

For $0<p<1$ and a large integer n, the p-random graph on n vertices [3], also known as the binomial random graph and denoted by G(n, p), is obtained by taking n labeled vertices and including every edge between them randomly and independently with probability p. Then, a standard probabilistic argument using Chebyshev’s inequality (also known as the second moment method [3]) implies the following.

Example 3.

For any fixed graph $H=(V,E)$, the random graph G(n, p) contains with high probability (i.e., with probability tending to 1 as n grows)$$(1+o(1))p^{\left|E\right|}{n}^{\left|V\right|}$$

labeled copies of H. In particular, G(n, p) with high probability contains $(1+o(1))p{n}^2$ labeled edges and $(1+o(1))p^4{n}^4$ labeled copies of the 4-cycle C₄.

The reason we singled out the edges and C₄s in the last example is the following seminal result of Chung, Graham, and Wilson [2, Theorem 1]. In what follows, when speaking about “large graphs,” we mean, formally, sequences of graphs with the number of vertices n tending to $\infty$.

Theorem 1

([2]). Suppose that $0<p<1$. The following properties of (large) n-vertex graphs G are equivalent.

(P1)G has $(1+o(1))p{n}^2$ labeled edges and $$(1+o(1))p^4{n}^4$$labeled copies of C₄.

(P2)For every fixed graph $H=(V,E)$, the number of labeled copies of H in G is $$(1+o(1))p^{\left|E\right|}{n}^{\left|V\right|}.$$

(P3)For every c > 0 and vertex set $S\subseteq V(G)$ of size $\left|S\right|\ge cn$, the number of labeled edges between vertices in S is $$(1+o(1))p|S{|}^2.$$

Observe that, by Example 3, a random graph G(n, p) satisfies with high probability property (P2) and thus, a fortiori, also (P1). Similarly, a standard application of the Chernoff bound [3] shows that G(n, p) satisfies with high probability property (P3). The remarkable aspect of Theorem 1 is that every (deterministic) graph that satisfies the seemingly very weak property (P1) must also satisfy the much stronger properties (P2) and (P3). In fact, the main result of [2] exhibited a number of further equivalent conditions (which we do not state here formally, for brevity).

A large graph satisfying either (P1), (P2), or (P3) (and therefore all three of them), is called p-quasirandom. A graph is quasirandom if it is p-quasirandom for some $0<p<1$. The notion of quasirandomness is central to extremal combinatorics: for instance, Szemerédi’s famous regularity lemma [20] states (vaguely speaking) that the vertices of a large graph can be partitioned into a bounded number of parts, so that “almost all” bipartite graphs between those parts are quasirandom, i.e., resemble a truly random subgraph of a complete bipartite graph.

A very sensible question to ask at this point is, whether any deterministically constructed quasirandom graphs are known to exist. The answer is yes, and one prominent class of examples are the Paley graphs (arising from a similar construction for matrices in [15]). Their quasirandomness can be deduced from properties of quadratic residues.

Example 4.

Let $n=4k+1$ be a prime, so that x is a quadratic residue modulo n if and only if – x is one. Let G be a graph on the vertex set $\{0,\dots ,n-1\}$, where xy is an edge whenever x – y is a quadratic residue modulo n. Then G is 1/2-quasirandom.

On the cautious side we would like to add that some properties of the truly random graph G(n, p) are not captured by quasirandomness. For example, the largest clique in G(n, p) is with high probability of order $\text{log}\hspace{0.17em}n$, whereas in quasirandom graphs it can be of “almost linear” size.

The discussion above led the authors of [2] to define the notion of a forcing graph family.

Definition.

A family of graphs $\mathcal{F}$ is forcing if the following holds for every $0<p<1$. Suppose G is an n-vertex graph so that for every $F\in \mathcal{F}$ the graph G contains $(1+o(1))n^{|V(F)|}{p}^{|E(F)|}$ labeled copies of F. Then G is p-quasirandom.

By this definition, Theorem 1 states that the pair $\{K_2,C_4\}$ is forcing. To obtain a better understanding of the quasirandomness phenomenon, one should look for a classification of forcing families. This natural inverse question to Theorem 1 was raised by Chung, Graham, and Wilson in the same paper [2].

In the subsequent years, this topic has seen a significant amount of research (see [5] and the references therein), resulting in discoveries of a number of further forcing families. It is well known that for any nonbipartite graph H the pair $\{K_2,H\}$ is not forcing, and the main open question in this area is the forcing conjecture by Skokan and Thoma [18], saying that for every connected bipartite graph H that is not a tree the pair $\{K_2,H\}$ is forcing. In [18] this was proved for every complete bipartite graph H (more generally, it was shown in [18] that $\{H_1,H_2\}$ is forcing for any pair of distinct complete bipartite graphs), but the full conjecture is still wide open.

In the light of the above, it is even more challenging to decide whether an infinite family of graphs is forcing. Consider, for instance, four of the most natural such families, namely the sets of all cycles, stars, trees, and cliques. It is easy to see that the family of all cycles is not forcing for all $0<p<1$, since, by Example 2, the graph comprising a clique on pn vertices and $(1-p)n$ isolated vertices has the “correct” number $(1+o(1))p^{\ell }{n}^{\ell }$ of labeled cycles of length $\ell$, but fails to satisfy (P3) of Theorem 1. Similarly, the family of all stars is not forcing by Example 1 — in fact, this example shows that the family of all trees is not forcing.

The situation is less clear for the set of all finite cliques $\mathcal{K}=\{K_2,K_3,\dots \}$, where K_j denotes the complete graph on j vertices. Horn, as reported by West [24] asked whether $\mathcal{K}$, or perhaps some finite subset of $\mathcal{K}$, is forcing (the latter would clearly imply the former) — this would mean that any large graph having $(1+o(1))p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}{n}^j$ labeled copies of K_j for each $j\ge 2$ satisfies property (P3) of Theorem 1. Both questions have been open until now, and our aim in this article is to answer them in the negative.

First, we give an elementary proof of the fact that any set of finitely many cliques is not forcing.

Theorem 2.

For any $k\ge 2$ and $0<p\le 1/4$, there exist arbitrarily large n-vertex graphs $G_{k,p}(n)$ with $(1+o(1))p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}{n}^j$ labeled copies of K_j for all $j=2,\dots ,k$, and an independent set of size at least $n/2$. Therefore, the family ${\mathcal{K}}_k=\{K_2,\dots ,K_k\}$ is not forcing.

The theorem above deals only with finitely many cliques and only with $p\le 1/4$.³ By applying some properties of the deformed exponential function defined in (1), we prove our main result, extending Theorem 2 to all cliques and to all values of p.

Theorem 3.

The infinite family $\mathcal{K}=\{K_2,K_3,\dots \}$ is not forcing for any $0<p<1$.

3 Proofs of the main results

The finite case.

First we deal with the case of finitely many cliques.

Proof of Theorem 2. We claim that for fixed $k\ge 2$ and $0<p\le 1/4$ there exist k real nonnegative numbers $(c_1,\dots ,c_k)=(c_1(k,p),\dots ,c_k(k,p))$ with the following properties.

1. For all $1\le j\le k$,$$\sum _{A\in \left(\begin{array}{c}\left[k\right]\\ j\end{array}\right)}\prod _{i\in A}{c}_i=\frac{p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}}{j!},$$

where $\left(\begin{array}{c}[k]\\ j\end{array}\right)$ stands for the set of all j-element subsets of $\{1,\dots ,k\}$.

1. $\max c_i\ge 3/4$.

Given these numbers, define $G=G_{k,p}(n)$ to be a graph on n vertices as follows. Partition V(G) into sets $V_1,\dots ,V_k$, such that for all $1\le i\le k$ we have $\left|\right|V_i|-c_{i}n|<1$; this is possible since, by (i), ${\sum }_{i=1}^k{c}_i=1$. Let E(G) be the set of all edges uv where $u\in V_i,v\in V_j$ for $i\ne j$. In other words, G is the complete k-partite graph on $(V_1,\dots ,V_k)$.

By this construction, for every $j=2,\dots ,k$ the graph $G_{k,p}(n)$ has$$\begin{array}{c}j!\sum _{A\in \left(\begin{array}{c}\left[k\right]\\ j\end{array}\right)}\prod _{i\in A}|V_i|=j!\sum _{A\in \left(\begin{array}{c}\left[k\right]\\ j\end{array}\right)}\prod _{i\in A}(c_{i}n\pm 1)=(1+o(1))j!\sum _{A\in \left(\begin{array}{c}\left[k\right]\\ j\end{array}\right)}\prod _{i\in A}{c}_i{n}^j\\ =(1+o(1))p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}{n}^j\end{array}$$labeled copies of K_j . Here, $c_{i}n\pm 1$ stands for an integer within 1 of $c_{i}n$. On the other hand, by (ii), it has an independent set of size at least $n·\max c_i-1\ge n/2$. Hence, this graph satisfies the assertions of Theorem 2. Note that the fact that $G_{k,p}(n)$ has an independent set of size at least $n/2$ implies it fails property (P3) of Theorem 1 for c = 1/2. Therefore, $G_{k,p}$ is not p-quasirandom for any $0<p<1$, and we conclude that ${\mathcal{K}}_k$ is not forcing.

It remains to construct the sequence $(c_1,\dots ,c_k)$ with the properties above. To this end, consider the real polynomial function(2) $$f_{p,k}(x)=\sum _{j=0}^k\frac{p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}}{j!}{x}^j,$$(2) which is a truncated version of the deformed exponential function (1).

Kurtz [8] established the following useful criterion for a polynomial to have only real roots, which can be viewed as a converse to Newton’s inequalities.

Proposition 4

([8], Theorem 2). If the coefficients of a real polynomial $P(x)={\sum }_{i=0}^n{b}_i{x}^i$ satisfy $b_i>0$ for all i and $b_i^2>4b_{i-1}{b}_{i+1}$ for all $1\le i\le n-1$, then all the roots of P are real and distinct.⁴

In order to apply Proposition 4 to the polynomial $f_{p,k}(x)$ all we need to check is that$$\frac{p^{2\left(\begin{array}{c}j\\ 2\end{array}\right)}}{j!j!}>\frac{4p^{\left(\begin{array}{c}j+1\\ 2\end{array}\right)+\left(\begin{array}{c}j-1\\ 2\end{array}\right)}}{(j+1)!(j-1)!}$$holds for every $j=1,\dots ,k-1$. This simplifies to$$\frac{1}{j}>\frac{4p}{j+1},$$

which is evidently true for all $p\le 1/4$. Thus, $f_{p,k}$ has k distinct real roots $a_1,\dots ,a_k$, and can be written as(3) $$f_{p,k}(x)=\frac{p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}}{k!}\prod _{i=1}^k(x-a_i).$$(3)

Since the coefficients of $f_{p,k}$ are positive, $f_{p,k}(x)>0$ for $x\ge 0$, and thus all of the roots are negative. Writing $c_i:=-1/a_i$ (so that $a_i=-1/c_i$), we obtain(4) $$\begin{array}{c}{f}_{p,k}(x)=\frac{p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}}{k!}\prod _{i=1}^k\left(x+\frac{1}{c_i}\right)=\frac{p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}}{k!}{\left(\prod _{i=1}^k{c}_i\right)}^{-1}\prod _{i=1}^k(1+c_{i}x)\\ =\frac{p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}}{k!}{(-1)}^k\prod _{i=1}^k{a}_i\prod _{i=1}^k(1+c_{i}x).\end{array}$$(4)

We will now show that the above-defined $c_1,\dots ,c_k$ satisfy the properties (i) and (ii) stated at the beginning of the proof. Evaluating the constant term in (3) gives$$\frac{p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}}{k!}{(-1)}^k\prod _{i=1}^k{a}_i=1,$$which, combined with (4), implies(5) $$f_{p,k}(x)=\prod _{i=1}^k(1+c_{i}x).$$(5)

Next, evaluating in (5) the coefficient of x^j for all $1\le j\le k$ gives(6) $$\sum _{A\in \left(\begin{array}{c}\left[k\right]\\ j\end{array}\right)}\prod _{i\in A}{c}_i=\frac{p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}}{j!},$$(6)

establishing property (i). In particular, (6) implies ${\sum }_{i=1}^k{c}_i=1$ and $\sum _{1\le i<j\le k}{c}_i{c}_j=p/2$. Therefore,$$\max c_i=\max c_i·\sum _{i=1}^k{c}_i\ge \sum _{i=1}^k{c}_i^2={\left(\sum _{i=1}^k{c}_i\right)}^2-2\sum _{1\le i<j\le k}{c}_i{c}_j=1-p\ge \frac{3}{4},$$establishing property (ii). □

It turns out that the polynomial $f_{p,k}$ has imaginary roots when p > 1∕2; hence, the approach we used in the proof above cannot cover all $0<p<1$. Therefore, to extend this to all $0<p<1$ and to handle the set of all cliques, we need a slightly different approach.

The general case.

We now prove that $\mathcal{K}$, the family of all finite cliques, is not forcing. As a first step toward the proof of Theorem 3, we will construct an “infinite graph” satisfying its assertion. We briefly mention that in the theory of graph limits [11] such an object is called a graphon.

Lemma 5.

For every $0<p<1$, there is a graph W_p whose vertex set is the interval $[0,1]$ and which satisfies:

1. For every $k\ge 2$, if we randomly and (Lebesgue-)uniformly select k vertices, $v_1,\dots ,v_k$ from $[0,1]$, then the probability that for every i < j the vertices v_i, v_j are connected by an edge in W_p is $p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}$.

2. There is an interval $I\subseteq [0,1]$ of length $1-p$ so that {x, y} is not an edge of $W_p$ for every $x,y\in I$.

Observe that assertion (1) is a continuous counterpart to the property of a finite n-vertex graph containing the “correct” number of cliques. Similarly, assertion (2) states that W_p has an independent set on a $(1-p)$-fraction of its vertices — a finite graph with this property would fail to satisfy (P3) of Theorem 1.

Proof of Lemma 5.

For a sequence of positive real numbers $\mathcal{C}=(c_1,c_2,\dots )$ and an integer $k\ge 1$, we use ${\sigma }_k(\mathcal{C})$ to denote the formal expression $\sum _{A\in \left(\begin{array}{c}\mathbb{N}\\ k\end{array}\right)}\prod _{j\in A}{c}_j$. Similarly to the proof of Theorem 2, we claim that for every $0<p<1$ there exists a sequence $\mathcal{C}=(c_1,c_2,\dots )$ of positive reals $1>c_1\ge c_2\ge \dots >0$ with the following properties.

1. For each $k\ge 1,{\sigma }_k(\mathcal{C})$ is convergent, with ${\sigma }_k(\mathcal{C})=p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}/k!$.

2. $\max c_i=c_1\ge 1-p.$

With such a sequence at hand, we partition the $[0,1]$-interval into infinitely many intervals $V_1,V_2,\dots$, such that $\left|V_i\right|=c_i$ for all i (note that ${\sum }_{i=1}^{\infty }{c}_i={\sigma }_1(\mathcal{C})=1$), and we let W_p be the graph on the vertex set $[0,1]$, where x and y are connected by an edge if and only if they belong to different intervals V_i and V_j .

Then for every fixed $k\ge 2$, a random sample of k vertices $v_1,\dots ,v_k$ from $[0,1]$ forms a clique in W_p with probability $k!{\sigma }_k(\mathcal{C})=p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}$. Moreover, for the interval V₁ we have $\left|V_1\right|=c_1\ge 1-p$, and no $x,y\in V_1$ are connected by an edge in W_p . Hence, W_p satisfies both assertions of the lemma.

To construct the desired sequence $\mathcal{C}$, we consider the deformed exponential function $f_p(z)$ over a complex variable z, defined in (1). It was shown in [6] and [14] that for every $0<p<1$ the function f_p can be represented as a product(7) $$f_p(z)=\prod _{i=1}^{\infty }\left(1-\frac{z}{a_i}\right),$$(7) where the a_i , the roots of f_p , are real (which means they must be negative, as the power series of f_p has only positive signs).⁵ Thus, we can set $c_i=-1/a_i$ and $\mathcal{C}:=(c_1,c_2,\dots )$, where the elements are indexed in descending order, to obtain$$f_p(z)=\prod _{i=1}^{\infty }(1+c_{i}z).$$

By comparing the coefficients of z^k for every $k\ge 1$, we obtain that each ${\sigma }_k(\mathcal{C})$ is convergent, with ${\sigma }_k(\mathcal{C})=p^{\left(\begin{array}{c}k\\ 2\end{array}\right)}/k!$. Furthermore, since all c_i are positive, and σ₁ and σ₂ are (absolutely) convergent, for $c_1=\max \mathcal{C}$ we get$$\begin{array}{c}{c}_1=c_1·1=c_1·{\sigma }_1(\mathcal{C})\ge \sum _{i=1}^{\infty }{c}_i^2={\left(\sum _{i=1}^{\infty }{c}_i\right)}^2-2\sum _{1\le i<j}{c}_i{c}_j\\ ={\sigma }_1{(\mathcal{C})}^2-2{\sigma }_2(\mathcal{C})=1-p.\end{array}$$

Lemma 5

gives an example of a “complete infinite-partite” graph that contains for every $j\ge 2$ the same fraction of copies of K_j as the random graph G(n, p). Such a construction of course cannot be achieved for finite graphs. Instead, for every $k\ge 2$ we show how to turn W_p into large graphs containing the correct number of labeled copies of K_j for every $j\le k$.

Proof of Theorem 3.

Take the infinite graph W_p defined in Lemma 5, select n vertices $v_1,\dots ,v_n$ from it uniformly at random, and let $G_p(n)$ be the graph induced on these vertices. That is, the edges of G are the edges of W_p between $v_1,\dots ,v_n$.

Fix $k\ge 2$ and $\mathrm{ϵ}>0$. By assertion (1) of Lemma 5 and the law of large numbers, for a sufficiently large $n=n(k,\mathrm{ϵ})$ the graph $G_p(n)$ will, with probability greater than 1/2, contain between $(1-\mathrm{ϵ})n^j{p}^{\left(\begin{array}{c}j\\ 2\end{array}\right)}$ and $(1+\mathrm{ϵ})n^j{p}^{\left(\begin{array}{c}j\\ 2\end{array}\right)}$ labeled copies of K_j for all $j=2,\dots ,k$. Additionally, assertion (2) of Lemma 5 together with the law of large numbers imply that, for large n, with probability greater than 1/2, $G_p(n)$ will have an independent set of size at least $(1-p)n/2$. Thus, with positive probability, there exists a graph $G_{k,p,\mathrm{ϵ}}(n)$ that has both properties. In other words, $G_{k,p,\mathrm{ϵ}}(n)$ is an n-vertex graph containing between $(1-\mathrm{ϵ})n^j{p}^{\left(\begin{array}{c}j\\ 2\end{array}\right)}$ and $(1+\mathrm{ϵ})n^j{p}^{\left(\begin{array}{c}j\\ 2\end{array}\right)}$ labeled j-cliques for $j=2,\dots ,k$ and an independent set of size at least $(1-p)n/2$.

Now, select a sequence ${\mathrm{ϵ}}_1>{\mathrm{ϵ}}_2>\dots >0$ such that $\underset{k\to \infty }{\lim }{\mathrm{ϵ}}_k=0$, for instance, ${\mathrm{ϵ}}_k=1/k$. For each k take a graph $G_k=G_{k,p,{\mathrm{ϵ}}_k}(n)$ (for some n), and consider the sequence $G_2,G_3,\dots$; for the order $n=|V(G_k)|$ of the graphs we have $n\ge k$ (as G_k contains a k-clique), so n tends to $\infty$. Moreover, by construction, for every $j\ge 2$ the graphs in the sequence contain $(1+o(1))p^{\left(\begin{array}{c}j\\ 2\end{array}\right)}{n}^j$ labeled copies of K_j , while also containing an independent set of size at least $(1-p)n/2$. In particular, G = G_k fails property (P3) of Theorem 1, implying that G is not p-quasirandom. Therefore, the set of all cliques $\mathcal{K}=\{K_2,K_3,\dots \}$ is not forcing for any $0<p<1$. □

Remark. The proof of Lemma 5 relied on the fact that the roots of f_p are all real. It is worth noting that a lot more is known about these numbers; for instance, the kth largest root (denoted a_k above) is known to be of order $-k{p}^{1-k}$. Wang and Zhang [23] very recently established the asymptotics of the roots of f_p up to arbitrary lower order terms.

Notes

1 A complete bipartite graph is a graph on the vertex set $A\cup B$, where A and B are disjoint, and whose edge set is A × B. More generally, a complete k-partite graph is a graph whose vertex set is composed of k disjoint sets $A_1,\dots ,A_k$ and whose edge set is $\underset{i<j}{\cup }{A}_i\times A_j$. In other words, every two vertices in distinct A_i , A_j are connected by an edge.

2 A clique or complete graph is a graph on a vertex set V, whose edge set consists of all pairs $\{u,v\}\subseteq V$.[Mismatch]

3 Strictly speaking, in order to prove that a family $\mathcal{F}$ is not forcing it is enough to exhibit a counterexample for just one $0<p<1$. Still, it is more desirable to give examples for all $0<p<1$.

4 Note that the constant 4 is best possible for n = 2.

5 To be more detailed, $f_p(z)$ is an entire function, that is, f_p is defined on all of $ℂ$, and is holomorphic everywhere (for more background information about entire functions see [9, 19]). The order of an entire function $g(z)={\sum }_{j=0}^{\infty }{a}_j{z}^j$ is given by the formula $\rho =\underset{n\to \infty }{\lim \sup }\frac{n\hspace{0.17em}\text{log}\hspace{0.17em}n}{\hspace{0.17em}\text{log}\hspace{0.17em}(1/|a_n|)}$ ([9, Section 1.3, Theorem 2]). Thereby, the deformed exponential f_p is of order 0. By Hadamard’s factorization theorem ([19, Theorem 5.1]) an entire function of order 0, taking value 1 at x = 0, can be represented as a product (7), where the a_i are its complex roots. In [6, 14] it was shown that for any $0<p<1$ all roots of f_p are real.

Acknowledgments

We thank two anonymous referees for their helpful remarks. The first author was supported in part by ISF Grant 1028/16, ERC Consolidator Grant 863438, and NSF-BSF Grant 20196. The second author was supported in part by ERC Synergy grant DYNASNET 810115 and the H2020-MSCA-RISE project CoSP- GA No. 823748.

Additional information

Funding

The first author was supported in part by ISF Grant 1028/16, ERC Consolidator Grant 863438, and NSF-BSF Grant 20196. The second author was supported in part by ERC Synergy grant DYNASNET 810115 and the H2020-MSCA-RISE project CoSP- GA No. 823748.

Notes on contributors

Asaf Shapira

Asaf Shapira received his Ph.D. in computer science from Tel Aviv University in 2006. He is a professor in the School of Mathematical Sciences at Tel Aviv University since 2011, where he researches and teaches discrete mathematics with an emphasis on problems in extremal combinatorics. He was previously a postdoc at Microsoft Research, Redmond (2006–2008) and an assistant professor at Georgia Institute of Technology (2008–2011).

School of Mathematics, Tel Aviv University, Tel Aviv, Israel

[email protected]

Mykhaylo Tyomkyn

Mykhaylo Tyomkyn received his Ph.D. from the University of Cambridge in 2011. He is an assistant professor at Charles University where he works in extremal combinatorics. Previously he had postdoctoral appointments at the University of Birmingham, Tel Aviv University, the University of Oxford, and the California Institute of Technology. He enjoys chess and outdoor activities.

Department of Applied Mathematics, Charles University, Prague, Czech Republic[Mismatch]

[email protected]