9512.net
甜梦文库
当前位置:首页 >> >>

The penultimate rate of growth for graph properties



THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES
? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH Abstract. Given a property P of graphs, write P n for the set of graphs with vertex set [n] having property P. We call |P n | the speed of P. Recent research has shown that the speed of a monotone or hereditary property P can be a constant, polynomial, or exponential function of n, and the structure of the graphs in P can then be well described. Similarly, |P n | can be of the form 2 n(1?1/k+o(1))n or 2(1?1/k+o(1))n /2 for some k > 1 and the properties can be described and have well behaved speeds. In this paper, we discuss the behavior of properties with speeds between these latter bounds, i.e. between n(1+o(1))n 2 and 2(1/2+o(1))n /2 .

1. Introduction A graph property is a (in?nite) collection of (labeled) graphs closed under isomorphism. The property consisting of all ?nite graphs is called the trivial property. A property is hereditary if it is closed under taking induced subgraphs, and it is monotone if it is closed under taking subgraphs. For example, being acyclic, planar, or perfect are hereditary properties, while only the ?rst two are monotone. Rather trivially, every hereditary property can be de?ned in terms of forbidden induced subgraphs, and every monotone property can be de?ned in terms of forbidden subgraphs. Given a property P, write P n for the set of all graphs in P with n vertices. We call this the n-level of P. The number of graphs in the n-level, |P n |, is called the speed of a property. In recent years, there has been much research into the sequence (|P n |)∞ for hereditary properties (see, for example, [13], [5], [1]) and for n=1 monotone properties (see, for example, [2], [6]). The most natural questions about the speed of a hereditary property, which ?rst appeared in [13], are as follows. 1. Does limn→∞ 2. Does limn→∞ 3. Does
log |P n | exist for all hereditary properties P? n log |P n | n log n exist for all hereditary properties P? log log |P n | limn→∞ log n exist for all hereditary properties P? log |P n | limn→∞ n2 exist for all hereditary properties P?

4. Does The ?rst question was answered a?rmatively by Scheinerman and Zito in [13], and the others were left by them as open questions. The fourth question was answered a?rmatively by Bollob?s and Thomason in [5]. However, the second and a third questions remained open. In this paper we answer both negatively, even under a strong condition on the structure of the property. In doing so, we shed some light on a gap in the existing research on speeds. While investigating the questions above, Scheinerman and Zito [13] discovered that the speed sequence often has a well-de?ned behavior. They presented a rough hierarchy of speeds for hereditary properties, showing that the speed of a property must fall into certain ranges of growth. Earlier results by Bollob?s and Thomason a
Research partially supported by OTKA grant F026049. Research partially supported by NSF Grant DMS 9971788.
1

2

? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH

[5] had shown that the highest speed of growth is highly constrained as well. The present authors provided a more detailed picture of the hierarchy of speeds for hereditary properties in [1] and furthermore described the structure of properties falling into each range of speed. Similar results for monotone properties were shown in [2]. These results can be brie?y summarized in the following theorem, which presents four functional ranges into which the speed of a hereditary property may fall. The ?rst level of growth can be divided into three parts depending on whether i = 0, i = 1, or i > 1. Theorem 1. Let P be a hereditary property of graphs. Then one of the following is true: 1. there exists N, k ∈ N and a collection {pi (n)}k of polynomials such that for i=0 k all n > N , |P n | = i=0 pi (n)in , 2. there exists k ∈ N, k > 1 such that |P n | = n(1?1/k+o(1))n , 2 3. n(1+o(1))n ≤ |P n | ≤ no(n ) , 2 4. there exists k ∈ N, k > 1 such that |P n | = 2(1?1/k+o(1))n /2 . The ?rst two cases and a jump to the third are described and proven by the authors in [1, 3]. The last case and the gap between case 3 and 4 are shown by Bollob?s and Thomasson in [5, 6]. Speci?cally, Theorem 1 and the results of [1] a imply that if the speed of a property falls into either the ?rst two or the ?nal range, the speed actually approaches a limiting function and the structure of graphs in the property can be described. Even from the form of the statement of Theorem 1, however, it is clear that the exact behavior of properties with speeds falling into the third range is not well understood. For this range, even the bounds have not been fully described, although the lower bound is understood and can be approximated using results from [2]. In Section 2 of this paper, we explore the upper bound of this range and show, as in the other ranges (including within the ?rst range), that there is a discontinuous jump in the ranges of speeds allowed. In Section 3 we describe a type of property, a selectively restricted property, which exists in the penultimate range of growth. We show that some selectively restricted properties have speeds towards the bottom of the third range of growth, while others have high speeds. In Section 4, we demonstrate particular selectively restricted properties which provide an in?nite collection of negative examples for the second and third questions of Scheinerman and Zito. Speci?cally, we describe a monotone (and hence hereditary) property with speed that oscillates in?nitely often between two functions near the upper and lower bounds on the penultimate range. In the two subsequent sections, we discuss improvements on the construction given in Section 4. We close with a conjecture that the results presented here are nearly the best one could obtain. 2. Bounds on the factorial range What are the actual upper and lower limits on the penultimate range of growth? Theorem 1 implies that if P is hereditary and for some > 0 we have |P n | < n(1? )n for in?nitely many values of n, then the property will fall into ranges 1 or 2. The same is true for monotone properties, as is shown in [2]. The theorem also suggests 2 that if there is a c such that |P n | > 2cn for in?nitely many values of n, then the speed of the property falls into range 4.

THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES

3

In fact, it is shown in [3] that the smallest property in the penultimate range is the property Pclique = {G : every component of G is complete} or the comn plementary property. These properties have speed |Pclique | = b(n), where b(n) th is the n Bell number. Hence the lower bound on this speed range is b(n) ? nn (log n)?n . With the lower bound known, we begin our investigation of the penultimate 2 range at its upper bound. What speeds of the type 2o(n ) are possible for graph properties? This question may be answered more easily for monotone than for hereditary properties; in fact the question is open for the latter class. We shall show 2? that given any monotone property P, either there is an such that |P n | < 2n or 2 (1/4+o(1))n else the speed is at least 2 .
n log n 1?1/ log n

Notation and de?nitions: For a graph G, we write v(G) = |V (G)| and e(G) = |E(G)|. Further, we call a graph G an n-graph if v(G) = n, and H ? G a k-subgraph if v(H) = k. The collection of labeled n-graphs (on [n]) is denoted G n . The following lemma is a simple observation which nonetheless provides strong information about large graph properties. Lemma 2. Let > 0 and 0 < c ≤ 2. There is an N such that for all n > N , if S 2?c+ is a set of graphs on n vertices and |S| > 2n , then there is a graph G ∈ S with e(G) > n2?c . Proof. Let fc (n) be the number of graphs on n vertices with at most n2?c edges. Then,
n2?c

fc (n) ≤
j=0

n 2

j = e 2

≤n
n2?c

2?c

en2 2n2?c
2?c

n2?c

n2?c ncn

= 2n

2?c

(lg (e/2)+c lg n)+(2?c) lg n

= 2n
2?c+

2?c+o(1)

.

Hence for all there is an N such that for all n > N , fc (n) < 2n . Thus if 2?c+ n > N and there is a collection S of n-graphs with |S| > 2n , then there is a graph G ∈ S with e(G) > n2?c . We are now ready to prove the main result of this section. Note that a property P is monotone if and only if there is a (possibly in?nite) collection H of graphs such that P = Mon(H), where Mon(H) is the set of all graphs G such that no subgraph of G is isomorphic to any H ∈ H. We also de?ne Her(H) as the set of all graphs G such that no induced subgraph of G is isomorphic to any H ∈ H. Theorem 3. Let P be a monotone property. If |P n | = 2o(n ) , then there is a t ≥ 1 2?1/t+o(1) such that |P n | ≤ 2n . Proof. Let P = Mon(H) be a monotone property with speed |P n | = 2o(n ) . If every graph H ∈ H has chromatic number at least 3, then {G : G is bipartite} ? 1 n Mon(H) = P, in which case |P n | ≥ 2 2 ( 2 ) . Hence H contains a bipartite graph H. Let t be the order of the larger set in the bipartition of H. Assume for the 2?1/t+o(1) sake of contradiction that |P n | > 2n . By Lemma 2, there is then a G ∈ P o a o a such that e(G) > n2?1/t . A result of K?v?ri, S?s, and Tur?n [8] says that G contains the graph Kt,t as a subgraph. Thus G contains H as a subgraph, which is a contradiction.
2 2

4

? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH
2

The result above is nearly the best result possible about the gap below 2cn . In the proof, we showed that large properties must contain large complete bipartite graphs. On the other hand, we can construct properties that nearly reach the upper bound given for which a large complete bipartite graph is forbidden. To do so, we use the well-known fact that for any t there exists a bipartite graph with at least n2?2/t edges that contains no subgraph isomorphic to Kt,t (see, i.e., [4], p. 316, 2 Thm. VI.2.10). Hence, for example, if P = Mon({Kt,t , K3 }), then |P n | = 2o(n ) 2?2/t 2?2/t and |P n | ≥ 2n . Thus Theorem 3 in fact guarantees a t such that 2n ≤ 2?1/t n n |P | < 2 . We conjecture that the same is true for hereditary properties, and 2?2/t again this would be the best possible, as |P n | ≥ 2n for P = Her({Kt,t , K3 }). The conjecture below di?ers from Theorem 3 only in considering hereditary rather than monotone properties. Conjecture 4. Let P be a hereditary property. If |P n | = 2o(n ) , then there is a 2?1/t t ≥ 1 such that |P n | ≤ 2n . This conjecture is far from proven, however. While it would be surprising, it is not inconceivable that there could be properties with other speeds. A result of Ruzsa and Szemer?di about hypergraphs suggests that properties of hypergraphs e do not behave so nicely, but the calculations and considerations are completely di?erent. 3. Some special properties and their growth The results of the previous section imply that if the speed of P is in the penul2?1/t timate range, there is an integer t ≥ 1 such that n(1+o(1))n < |P n | < 2n . This is proven for monotone P but only conjectured for hereditary P. We now turn our attention to the question of what speeds are actually achieved in this range for graph properties, either monotone or hereditary. We present a collection of properties with speeds lying in the range. Our ?rst property is de?ned in terms of the density of subgraphs. We de?ne the c-dense property Qc by Qc = {G : e(H) ≤ cv(H) for all H ? G}. The following assertion was proved by Scheinerman and Zito [13]. Theorem 5. For any c > 1, |Qn | = n(c+o(1))n . c The property Qc is a monotone property, and this result shows that any speed of the type ncn , c > 1 is achievable. The next property we describe is not monotone or hereditary, but its n-level contains the n-level of Qc . It will be useful in further n proofs in this section. The c-dense n-level is simply Sc = {G ∈ G n : e(G) ≤ cn}. The following lemma gives a bound on its size.
n Lemma 6. If c > 1, then |Sc | < f (n)ncn , with f (n) = O(1.5n ).
2

Proof. Note simply that
cn n |Sc | ≤ j=0 n 2 cn

j


j=0

en2 /2j

j

< cn en2 /2cn where, easily, f (n) = O(1.5n ).

cn

= cn (en/2)

cn

= f (n)ncn ,

We showed in the previous section that there are properties with speeds at the 2?2/t 2?1/t ≤ |P n | < 2n . Hence, there are top of the third range, that is, with 2n

THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES

5

properties with speeds throughout the range of the third case of Theorem 1. This does not necessarily mean that any speed can be achieved, however. We examine constraints on demonstrably achievable functions later in this paper. As mentioned in the introduction, if the speed of a property falls into any but the third range, |P n | can be described with a “nice” function. However, we shall show that this is not the case for the third range. In this range, it is possible for the speed to oscillate between two di?erent functions in?nitely often. More precisely, the question we examine is as follows. Is there a property P so that for functions f (n) < g(n), |P n | oscillates in?nitely often between them? Clearly there are choices of f (n) and g(n) for which it is not possible to construct such a hereditary property. In particular, Theorem 1 implies that if g(n) ≤ 2 n(1?1/k+o(1))n for some k or f (n) ≥ n(1?1/k+o(1))n /2 for some k, then |P n | cannot oscillate. However, we shall show that for many choices of f (n) and g(n) in a subrange of the third range of Theorem 1, we can construct such a property. Furthermore, this property is monotone (and therefore also hereditary). Our methods are probabilistic in nature, and we proceed in steps, ?rst demonstrating a property with ?xed upper and lower bounds on the oscillation of its speed, and then by adjusting the upper and lower bounds. We begin with a technical probabilistic lemma regarding sets of graphs and Gn,p (i.e. a random graph of order n in which edges are selected independently at random with probability p). Lemma 7. Let > 0 be ?xed and let p = p(n) ≤ 1/2. If n is su?ciently large and √ N a set of graphs T ? G n satis?es P(Gn,p ∈ T ) ≥ 1/2 + 2 , then |T | ≥ pqN pN , where N = n and q = 1 ? p. 2 Proof. If n is su?ciently large, P(e(Gn,p ) ≤ pN ) ≤ 1/2 + . Hence P(Gn,p ∈ T and e(Gn,p ) > pN ) ≥ 1/2 + 2 ? (1/2 + ) = . Note that for any H ∈ G n the probability P(Gn,p = H) depends only on the number of edges in H. Hence, if H0 , H1 ∈ G n with e(H0 ) < e(H1 ), then P(Gn,p = H0 ) ≥ P(Gn,p = H1 ). Thus, if e(H) > pN , then for any H with e(H ) = pN , we have P (Gn,p = H) < P (Gn,p = H ) < Then P (Gn,p ∈ T and e(Gn,p ) > pN ) ≤ |{H ∈ T , e(H) > pN }| so |T | ≥ √ pqN
N pN

pqN

N pN

?1

.
?1

pqN

N pN

,

.

We will be applying this lemma in a speci?c form, expressed in the following corollary. Corollary 8. Suppose p = p(n) < 1/2, p n → ∞. If n is su?ciently large and 2 the set T ? G n satis?es P(Gn,p ∈ T ) ≥ 2/3, then |T | ≥
n 2 p n 2

≥ (1/p)p( 2 ) .

n

(1)

This corollary will be applied to show that the oscillating properties we construct grow as desired. The following basic construction will be used as a starting point in each of the theorems that are to come. Let c > 1 and ν = (ν1 , ν2 , . . . ) be an

6

? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH

increasing (possibly ?nite) sequence of natural numbers. We de?ne a selectively restricted property Pν,c as {G : if H ? G and v(H) = νi for some i, then e(H) ≤ cνi }. Note that Pν,c is monotone and therefore also hereditary. The property Pν,c has a speed which grows in a predictable way. Lemma 9. Let c > 1, < 1/c, ν = (νi )∞ be a sequence of natural numbers and i=1 k = sup{νi ∈ ν}. Then n n 1. |Pν,c | ≥ n(c+o(1))n and |Pν,c | = n(c+o(1))n whenever n = νi , 2? n 2. if k < ∞ and n is su?ciently large, |Pν,c | ≥ 2n . Proof. For any sequence ν and c > 1, we have Qc ? Pν,c and, for any i, the νi νi ν n ν level Pν,c ? Sc i . Hence we have |Pν,c | ≥ n(c+o(1))n for all n and |P νi | ≤ |Sc i | ≤
i νi on the set {νi } by Lemma 6. Using Theorem 5 for a lower bound, we n obtain |Pν,c | = n(c+o(1))n whenever n = νi . For the second part, assume k < ∞. Consider the property P(k),c , where (k) is n n the sequence (1, . . . , k). We have |P(k),c | ≤ |Pν,c | for all n. Hence we would have

(c+o(1))ν

n the result if, for su?ciently large n, |P(k),c | ≥ nn . Choose δ so that > δ > 1/c. Let p = n?δ and consider Gn,p . We consider the probability that Gn,p ∈ P(k),c . This is the probability that Gn,p has a “bad” / n subgraph, that is,

2?

P Gn,p ∈ P(k),c = P(G ∈ Gn,p : there is H ? G with v(H) ≤ k and e(H) > cv(H)) / n
k


j=1 k

E(number of j-subgraphs of Gn,p with more than cj edges) n j e j
j 2 k


j=1 k

cj ej 2c
c

pcj ≤
j=1 j

en j
k

j

ej 2 2cj

cj

n?δcj
j


j=1

n1?δc

=
j=1

Cj n1?δc

,

where Cj (? j c?1 ) is a constant depending on j and c. Since δc > 1, we have 1 ? δc < 0, so this probability goes to zero as n goes to in?nity. Choose n0 minimal so that the probability that Gn0 ,nδ has a “bad” subgraph is less than 1/3. Note 0 that this probability is monotone decreasing in n. That is, if P(G ∈ Gn0 ,nδ : G has 0 a bad subgraph) < 1/3, then P(G ∈ Gn,nδ : G has a bad subgraph) < 1/3 for all n > n0 . Now we can apply Corollary 8 to the set T = P(k),c to obtain the result
n0 P(k),c ≥ nδ 0 n?δ (n0 ) 0 2

> 2n 0

2?δ

/2

.
2?δ

n All of the inequalities above hold whenever P(Gn,p ∈ T ) ≥ 2/3, so we have |P(k),c | >

2n /2 for all n > n0 . Thus we can choose n large enough to ensure 2n and obtain our result.

2?δ

/2

> 2n

2?

4. Oscillating properties: The second and third questions Having done the preliminary calculations in Section 3, we are now ready to prove the ?rst of three theorems regarding properties that oscillate. We ?rst construct a property with a large range of oscillation. The oscillation of this speed provides a negative answer to the third question of Scheinerman and Zito; we shall answer the second question with Theorem 11.

THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES

7

Lemma 9 gives a property with the proper bounds on its speed, so all that remains is to choose a sequence so that the property grows as desired. We shall be using sequences and their elements signi?cantly in the rest of the paper and shall abuse notation slightly. For a sequence N , we shall say n ∈ N if the value n appears somewhere in the sequence. If N is a subsequence of sequence M , we shall write N ? M . In other words, we shall use set notation with sequences to mean that the relations hold for the set of elements in the sequence. Theorem 10. Let c > 1 and > 1/c. There exist sequences ν = (νi )∞ and i=1 ? = (?i )∞ , where ?i = νi ? 1 for all i, such that i=1 n 1. |Pν,c | = n(c+o(1))n whenever n = νi , 2? n 2. |Pν,c | ≥ 2n whenever n = ?i , 2? (c+o(1))n n 3. n ≤ |Pν,c | < 2n if n = ?i . Proof. We choose ν1 , ν2 , . . . , one by one, starting with ν1 = 3. Having chosen 2? n ν1 , . . . , νk , we set ν = (ν1 , . . . , νk ) and note that by Lemma 9, |Pν,c | ≥ 2n for 2? ?k+1 su?ciently large n. Choose ?k+1 > νk minimal such that |Pν,c | ≥ ?k+1 ?k+1 . Set νk+1 = ?k+1 + 1. Continuing in this way, we obtain an in?nite sequence and the required property. The results in Theorems 3 and 10 suggest that ncn 2n is a natural range of oscillation that may occur in the penultimate range. However, there are many other types of oscillation possible. We ?rst show that the upper bound of the oscillation can be any function in the range that we choose, and, further, that the oscillation can be constrained to remain very close to the upper bound. Choosing f (n) = n(d+o(1))n for some d > c then gives a negative answer to the second question of Scheinerman and Zito. With Theorem 12, we shall show a similar, though slightly weaker, result for the lower bound. 2? Given a function f (n) ≤ 2n , Theorem 10 gives a sequence ν which guarantees n that |Pν,c | oscillates between n(c+o(1))n and some value above f (n) in?nitely often. Clearly, we can choose ν so that the speed only goes above f (n) when n = νi ? 1 for some i. However, we can do better than this by carefully truncating our properties at level ?i = νi ? 1 and showing that this will not a?ect any aspect of the construction we perform subsequently. This is precisely the method of the following theorem. Note that we constrain f (n) > nc n > n(c+o(1))n so that oscillation will actually occur. Theorem 11. Let c > 1, c > c, and > 1/c. Let f (n) be a function such that 2? nc n < f (n) ≤ 2n for all n. There exist sequences ν = (νi )∞ and ? = (?i )∞ n=1 n=1 and a monotone property P such that 1. |P n | = n(c+o(1))n whenever n = νi , 2. |P n | > f (n) ? n! whenever n = ?i , 3. |P n | ≤ f (n) for all n, 4. |P n | ≥ n(c+o(1))n . Proof. Choose sequences ν and ? as in Theorem 10, selecting values of ?i according 2? n n to |Pν,c | ≥ f (n) rather than |Pν,c | ≥ 2n . ?i n Then the property Pν,c has speed |Pν,c | ≥ f (?i ) and |Pν,c | < f (n) for all su?(c+o(1))n < f (n). ciently large n = ?i , since n We will use the fact that if P is monotone and G is an n-graph in P such that G H for any other graph on n or more vertices in P, then P \ {H : H ? G} is =
2?1/c

8

? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH

still a monotone property. That is, removing graphs from P k has no e?ect on P n and does not depend on the graphs in P n for any n < k. Furthermore, removing a graph and all graphs isomorphic to it from a property reduces |P n | by at most n!. If we choose graphs to remove carefully, this property will remain monotone. (N.B.: the same is true for hereditary properties.) We shall call a graph G ∈ P eligible in P if e(G) > cv(G) and there are no graphs H ∈ P with G H. For the property Pν,c , if νi?1 ≤ v(G) < νi ? 1 (= ?i ), G is eligible if and only if there are no ?i -graphs H with G ? H. If v(G) = ?i , then we need the further condition that no νi -graphs contain G as a subgraph. To construct a property satisfying the theorem, we remove ?i -graphs from Pν,c to obtain P. We only need to show that there is a set F, closed under isomorphism, ?i ?i consisting of eligible ?i -graphs in Pν,c such that f (n) ? n! < |Pν,c ? F| ≤ f (n). By the comment in the previous paragraph, changing a property at the ?i -level a?ects other levels if and only if it a?ects the νi -level. ?i νi How many graphs in Pν,c are subgraphs of graphs in Pν,c ? For any monotone property P, if Dk = {G : v(G) = k ? 1 and there is an H ∈ P k such that G ? H}, then Dk = {G : G ? H ? v, H ∈ P k , v ∈ V (H)}. Since P is monotone the fact = that P k is closed under taking subgraphs ensures that we get all possible subgraphs. (c+o(1))νi ?i Hence |Dk | ≤ k · |P k |. Thus, there are at most νi · νi graphs in Pν,c that
i νi are subgraphs of those in Pν,c . Hence |Dνi | ≤ ?i for su?ciently large i. Given a collection of graphs {Gj }j∈A , let F({Gj }j∈A ) be the set of all graphs i νi isomorphic to Gj for some j ∈ A and let Pk = Pν,c?1 \ F({Gj }j∈A ). We wish to i i build a collection of eligible graphs so that Pk will be monotone and f (?i ) ≥ |Pk | > f (?i ) ? ?i !. (c+o(1))?i ?i ?i As |Dνi | ≤ ?i < f (?i ) ≤ |Pν,c |, there are eligible graphs in Pν,c . Let G1 ?i i be an eligible graph in Pν,c . The property P1 is monotone since G1 eligible implies ?i i i G1 H for any H ∈ Pν,c ? G1 . Further |Pν,c | ? |P1 | ≤ ?i !, so |P1 | > f (?i ) ? ?i !. We proceed by picking eligible graphs in order, stopping at the ?rst point when i i |Pk | ≤ f (?i ). Clearly, if we have picked {Gi }k and |Pk | > f (?i ), the counting i=1 i argument above guarantees that Pk still has an eligible graph Gk+1 , so this process i i can continue, and |Pk | ? |Pk+1 | ≤ ?i !. Thus, if when considering ?i we stop with a i set of li graphs, |Pli | ≥ f (?i ). n Let P n = Pν,c for all n ∈ ? and P ?i = Plii for all i. As noted above, P is a / i monotone property. Clearly |P νi | = νi and f (?i ) ≥ |P ?i | > f (?i ) ? ?i !. / Also, by our choice of νi , |P n | < f (n) for all n ∈ ?.

(c+o(1))?

(c+o(1))ν

5. Oscillation from below Can we produce oscillation similar to that in Section 4, but which has a function other than ncn as its lower bound? That is, given a function f (n), is there a property 2? with speed that oscillates from just below f (n) to just above 2n in?nitely often? A modi?cation of the property in Theorem 10 again provides a candidate for the oscillation. However, we must relax the condition that the oscillation stay close to the upper bound in order to make the proof work easily. In particular, there is a 2? range of levels for which we cannot say whether |P n | < 2n . Theorem 12. Let c > 1 and > 1/c. Let f (n) be a function such that n(c+o(1))n ≤ 2? f (n) < 2n for all n. There exists a pair of sequences R = (ρi )∞ and M = i=1 ∞ (?i )i=1 and a monotone property P such that 1. f (ρi ) ? ρi ! < |P ρi | ≤ f (ρi ) for all i, 2? 2. |P ?i | > 2?i for all i,

THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES

9

3. |P n | ≥ f (n) for all n ∈ R, / 2? 4. |P n | < 2n for n ∈ i [ρi , ?i+1 ? 1]. Proof. The proof follows along the same lines as the proofs of Theorems 10 and 11, only this time we construct two sequences, R and ν. We ?rst build a sequence ν = (νi )∞ as in Theorem 10. Again let ?i = νi ? 1 for all i, and consider Pν,c . i=1 This satis?es conditions 2 and 4 of the theorem (for any sequence R which does not intersect M = (?i )). Hence we need to modify Pν,c to obtain conditions 1 and 3. However, in doing so, we need to be sure we do not create a property contradicting conditions 2 or 4. We choose the sequence R as follows. For all i, let ρi be the maximal n such 2? νi+1 (c+o(1))νi n νi that νi ≤ n < νi+1 and Pν,c ≤ f (n). Since |Pν,c | = νi , |Pν,c | > 2n , and 2? n(c+o(1))n ≤ f (n) < 2n , there always will be such an n. ρi We shall add graphs to Pν,c so that its speed is close to f (n). We know that this will not a?ect the n-levels of our property for n > ρi . If we can pick these graphs ?i so that every ?i -subgraph is in Pν,c , we will not a?ect any n-level for n ≤ σi either. ρi However, adding such a graph to Pν,c will enlarge the n-levels for ?i < n < ρi . ρi ρi If |Pν,c | > f (ρi )?ρi !, we need not modify |Pν,c |. Otherwise, consider the sequence ρ ρi ρi N = (ν1 , . . . , νi ). Then Pν,c ? PN ,c . In particular, Pν,c ? PNi ,c . Since |Pν,c | < f (ρi ) < 2n
2?

ρ ρ ρi < |PNi ,c |, there is a graph G ∈ (PNi ,c ? Pν,c ) such that every H ? G v(H)

with v(H) ≤ ?i is in Pν,c . We call such a graph insertable. Let G1 be an insertable graph with a minimal number of edges. Then every proper ρi -subgraph of G is in ρi ρi ρi Pν,c , so |Pν,c ∪F({G1 })| ≤ |Pν,c |+(ρi )!. Also, if P1 is a minimal property containing ρi n n Pν,c ∪ F({G1 }), then |P1 | = |Pν,c | for n > ρi and n < νi . For νi ≤ n ≤ ρi , the ρi n n speed |P1 | ≤ |Pν,c | + (ρi )! n . We continue choosing ρi -graphs in this way until we have a collection {G1 , . . . , Gli } so that f (ρi ) ? ρi ! < |Plρi | ≤ f (ρi ). As the only i condition we needed to guarantee an insertable graph was that the property had speed below f (n), it is clear that we can always ?nd an insertable graph if the property has speed below f (n). If we consider each i in turn and construct the property P = P{lj } in the obvious way, we obtain a monotone property satisfying conditions 1 and 2. However, conditions 3 and 4 do not necessarily hold for P on the intervals {[νi , ρi )}. Consider each value of i in turn and examine the interval [νi , ρi ) from the right. If, for t = ρi ? 1, the speed |(P )t | < f (t), we can proceed as we did ρi for (Pν,c ): add a ?nite collection graphs to (P )t to obtain a new property with 2? speed above f (t). If |(P )t | > 2t , we can instead remove graphs, as we did in 2? Theorem 11, until the property has fewer than 2t t-graphs. In either case, we only a?ect the n-levels for n ∈ [νi , t]. So continuing for each smaller value in the interval, we obtain a property P satisfying all of the conditions of the theorem. Ideally, given any two functions in the proper range with positive di?erence (= o(1)), we would like to construct a property with speed that oscillates in?nitely often between the two functions. However, this is clearly not possible, as for any monotone or hereditary property, |P n+1 |/|P n | ≤ 2n . Thus, for example, choosing functions that increase together by more than a factor of 2n would make it impossible to keep the speed between the bounds. With a restriction to “smooth” functions avoiding this problem, it seems that oscillation is possible. However, as we have seen in the proof of Theorem 12, even with a “smooth” function the proof would be cumbersome. In fact, even a proper de?nition of “smooth” would be unappealing. However, an outline of the approach we would take to prove the desired statement is as follows. Given two such functions f (n) < g(n), we wish to obtain a property

10

? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH

which achieves speeds close f (n) for in?nitely many n and close to g(n) for in?nitely many n. Rather than ?nding the sequence ν from Theorem 10, we would use the sequence from Theorem 11. In the ?nal step, when we add or remove graphs according to whether the property has too high or low a speed, we need to take care that in removing graphs we do not alter later properties. This may require adjusting our sequence so that the level for which the speed is above g(n) is in the interval between ?i and ρi rather than at ?i . The condition n(c ?c)n f (n) < g(n) would ensure the conditions of Theorem 11 and the positive di?erence between the functions. This, however, does not solve the problem we have discussed regarding condition 4 of Theorem 12. We believe that it is not worth the e?ort to describe in more detail what needs to be done. Nevertheless, we believe the following statement to be true, and would be happy to see an elegant proof. Let c > 1, c > c, and > 1/c. Let f (n), g(n) be “smooth” functions such that
2?

n(c+o(1))n ≤ f (n) < n(c ?c)n f (n) ≤ g(n) ≤ 2n

for all n. There exists a pair of sequences R = (ρi )∞ and S = (σi )∞ and a i=1 i=1 monotone property P such that 1. |P n | ≥ f (n) and |P n | ≤ g(n) for all n ∈ R ∪ S, / 2. f (ρi ) > |P ρi | > f (ρi ) ? ρi ! for all ρi ∈ R, 3. g(σi ) < |P σi | < g(σi ) + σi ! for all σi ∈ S. 6. A more natural oscillating property The aim of this section is to “sharpen” our results from a di?erent point of view. The properties given in Theorems 10 and 11 are useful for our purposes. In particular they neatly answer the questions of [13] mentioned in the introduction. However, the properties we describe are extremely arti?cial, their oscillation coming, to a large degree, from “unnecessary” graphs. In particular, there are many (isomorphism classes of) graphs in Pν,c that may be removed without a?ecting the hereditary nature of the property. In fact, we have used this fact rather heavily in the proofs of Theorems 11 and 12. However, while the removal of the graphs would not a?ect the hereditary nature of the properties in question, it would a?ect their speed. It would be nice, therefore, to know if there is a property for which each isomorphism class is necessary and for which the speed still oscillates. Given a property P, we de?ne the limit of P as P ? = {G : for all n > v(G) there is an n-graph H ∈ P with G ≤ H}. Then every graph in P is necessary if and only if P = P ? . In this case, we say that P is a limit property. Note that the limit of a property is a limit property, that is (P ? )? = P ? . n In [7], Bollob?s and Thomason show that if |P n | = 2(c+o(1))( 2 ) and |P ?n | = a n 2(c +o(1))( 2 ) , then c = c . Hence for properties in the highest range of speeds, where c > 0, a property and its limit have the same speed. However, this is clearly not true ? n for all properties, as Pν,c = Qc for all in?nite increasing sequences ν, while |Pν,c | n may oscillate but |Qc | does not. Hence we would like to demonstrate a property that has a limit whose speed oscillates. The following theorem provides a limit property with the same type of oscillation as that in Theorem 10. Theorem 13. Let c > 1, > 1/c. There is a monotone limit property P and two sequences R = (ρi )∞ and S = (σi )∞ with σi < ρi < σi+1 such that i=1 i=1 1. |P n | = n(c+o(1))n whenever n = ρi for some i, 2? 2. |P n | = 2(1+o(1))n whenever n = σi for some i, 2? 3. n(c+o(1))n ≤ |P n | ≤ 2(1+o(1))n for all n.

THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES

11

Proof. For two sequences R, S and a property P, consider the properties AR,S and BR,S de?ned by levels as follows. An = {G : v(G) = n and for all i and for all R,S n σi < l ≤ ρi , every l-subgraph H ? G has e(H) ≤ cl}, and BR,S = {G : v(G) = n σi and G = H ∪ Kl where H ∈ P and l = n ? σi for σi = max{s : n > s ∈ S}}. Note that AR,S is a property of the type Pν,c for some ν ? R. We will construct a property P ? AR,S ∪ BR,S which is monotone, limit, and has the proper speeds. As in the proof of the previous theorems, we proceed by constructing sequences R and S so that P is as described. We shall calculate values of ρi , σi based on those of ρi?1 , σi?1 , and describe P incrementally by levels. 2? Let ρ0 = 2 and let σ1 > ρ0 be the smallest value such that |T σi | > 2σ1 , where T is the trivial property. As in the proof of Theorem 11, we can remove graphs from 2? T σi so that |T σi | ≤ 2σ1 + n!. Let P σi be the collection of graphs which remain, and for n < σ1 , let P n = {G : v(G) = n and there is H ∈ P σi with G ? H}. Assume we have chosen sequences Ri?1 , Si where Ri = (ρ1 , . . . , ρi?1 ), Si = (σ1 , . . . , σi ) and we have de?ned the n-level of P for n ≤ σi . We wish to ?nd ρi (c+o(1))ρi ρ so that |Aρii?1 ,Si ∪ BRii?1 ,Si | = ρi . By Lemma 6, we know that for any R
i choice of ρi , the speed |Aρii?1 ,Si | = ρi . So if we choose ρi (minimal) so that R ρi cρi |BRi?1 ,Si | < ρi the desired relation will hold. There is such an ρi , since for all

(c+o(1))ρ

σ n n n > σi , |BRi?1 ,Si | ≤ σi |PRi ,Si | ≤ nσi 2σi , where the last estimate comes from i?1 all graphs being in the σi -level of P. Hence ρi = 2σi would be more than su?cient. n For σi < n ≤ ρi , let P n = An i ,Si ∪ BRi ,Si . R

2

Given ρi , let σi+1 > ρi be the smallest number such that |ARi+1 i ∪BRi+1 i | > 2σi+1 . i ,S i ,S The existence of such a number is guaranteed by Lemma 9. As in the proof of Theorem 11, we can remove eligible graphs, one isomorphism class at a time, from 2? σ σ ARi+1 i ∪ BRi+1 i to obtain P σi +1 with |P σi +1 | < 2σi+1 + σi+1 !. As we want to i ,S i ,S create a limit property, we will then remove graphs from P n for n < σi+1 , keeping only those graphs which appear as subgraphs of those in P σi+1 . However, we want to be sure that P remains at the proper speed. In particular, we will remove no σ σ graphs from BRi+1 i and no graphs in Qc i+1 (noting that Qn ? An for all n c R,S i ,S and any sequences R, S). Clearly there are enough eligible graphs avoiding these σ σ (c+o(1))σi+1 collections, as |BRi+1 i | + |Qc i+1 | < σi+1 . Note that with this restriction, we i ,S will not remove any graphs from P n for n ≤ ρi . In this way we construct in?nite sequences R and S. It is clear that P is a monotone property, and the construction guarantees that P is limit property, since we remove all graphs that are not contained in arbitrarily large graphs. The speeds given in conditions 1 and 2 are correct on the elements of R and S, respectively, by the construction. Furthermore, Qc ? P, so the lower bound given in condition 3 is correct. For the upper bound, we split the interval (σi , σi+1 ) into two parts. Our choice of 2? the sequence S guarantees that for ρi < n < σi+1 , |P n | < 2n . For σi < n ≤ ρi , we 2? σi n n n < note |P n | ≤ An + BR,S . Hence |PR.S | < n(c+o(1))n + σi PR,S < nσi 2n R,S 2(1+o(1))n
2?

σ

σ

2?

.

Thus we have presented a “sensible” property for which the speed oscillates over 2? nearly the whole interval from n(1+o(1))n to 2n . This property, as is true of all of the properties presented in the paper, has an in?nite class of forbidden subgraphs corresponding to the in?nite sequences constructed. That is, if P is one of our oscillating properties and F is a minimal class of graphs such that P = Mon(F), then F is in?nite. Is this a necessary condition for oscillation to occur? We believe

12

? ? ? JOZSEF BALOGH, BELA BOLLOBAS, AND DAVID WEINREICH

that it is: if a monotone property has a ?nite class of forbidden subgraphs, then all of the limits presented in the introduction should exist. So far, however, a proof of such a result is elusive. 7. Tight bounds on the penultimate range The results of Sections 4 – 6 demonstrate that the penultimate range di?ers signi?cantly from the other ranges of speed. In fact, it is unclear that properties in this range need to satisfy any well-de?ned behavior besides the broad bounds given in Section 2. Nevertheless, based on results involving a di?erent measure of properties in [2], we believe that the range of oscillation demonstrated in the properties presented here is the maximum possible. The converse of the conjecture is true for monotone properties, as shown by Theorem 3 and in [2]. However, the ?rst part of the conjecture is open even for monotone properties. Conjecture 14. For all c > 1, there exists an > 0 such that if P is a hereditary 2? property and |P n | ≥ 2n holds in?nitely often, then |P n | ≥ n(c+o(1))n . Conversely, for all d > 1 there exists a δ > 0 such that if |P n | ≤ n(d+o(1))n in?nitely often, then 2?δ+o(1) |P n | ≤ 2n . It is clear from Lemma 9 that, if Conjecture 14 is true, δ ≤ 1/d. Perhaps Conjecture 14 even holds with = 1/c and δ = 1/d. However, there are no results of this type known. Thus the penultimate region of speeds remains a fertile area for further research.

References
[1] J. Balogh, B. Bollob?s, and D. Weinreich, The size of hereditary properties of graphs, J. a Combin. Theory Ser. ’B’ 79 2 (2000), 131–156. 1, 2 [2] J. Balogh, B. Bollob?s, and D. Weinreich, The size and speed of monotone properties of a graphs, submitted to Disc. Appl. Math. 1, 2, 12 [3] J. Balogh, B. Bollob?s, and D. Weinreich, The structure of posets and an application to a hereditary properties, preprint. 2, 3 [4] B. Bollob?s, Extremal Graph Theory, Academic Press, London (1978). 4 a [5] B. Bollob?s and A. Thomason, Projections of bodies and hereditary properties of hypergraphs, a J. London Math. Soc. 27 (1995), 417–424. 1, 2 [6] B. Bollob?s and A. Thomason, Hereditary and monotone properties of graphs, in “The Matha ematics of Paul Erd?s II” (R.L. Graham and J. Neˇetˇil, eds.) Algorithms and Combinatorics, o s r Vol. 14, Springer-Verlag (1997), 70–78. 1, 2 [7] B. Bollob?s and A. Thomason, The structure of hereditary properties and colourings of a random graphs, Combinatorica, to appear. 10 [8] T. K?v?ri, V.T. S?s, and P. Tur?n, On a problem of K. Zarankiewicz. Colloq. Math. 3 (1954), o a o a 50-57. 3 [9] H.J. Pr¨mel and A. Steger, Excluding induced subgraphs: quadrilaterals, Random Structures o and Algorithms 2 (1991), 55–71. [10] H.J. Pr¨mel and A. Steger, Excluding induced subgraphs II: extremal graphs, Discrete Apo plied Mathematics 44 (1993), 283–294. [11] H.J. Pr¨mel and A. Steger, Excluding induced subgraphs III: a general asymptotic, Random o Structures and Algorithms 3 (1992), 19–31. [12] H.J. Pr¨mel and A. Steger, The asymptotic structure of H-free graphs, in Graph Structure o Theory (N. Robertson and P. Seymour, eds), Contemporary Mathematics 147, Amer. Math. Soc., Providence, 1993, pp. 167-178. [13] E.R. Scheinerman and J. Zito, On the size of hereditary classes of graphs, J. Combinat. Theory (B) 61 (1994), 16–39. 1, 4, 10

THE PENULTIMATE RATE OF GROWTH FOR GRAPH PROPERTIES

13

Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152 E-mail address: balogj@msci.memphis.edu Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, and, Trinity College, Cambridge CB2 1TQ, England E-mail address: bollobas@msci.memphis.edu Department of Mathematics, University of Wisconsin – La Crosse, La Crosse, Wisconsin 54601 E-mail address: weinreic@math.uwlax.edu



更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图