Almost all graphs are rigid—revisited

Almost all graphs are rigid—revisited

Discrete Mathematics 309 (2009) 5420–5424 Contents lists available at ScienceDirect Discrete Mathematics journal homepage: www.elsevier.com/locate/d...

352KB Sizes 0 Downloads 41 Views

Discrete Mathematics 309 (2009) 5420–5424

Contents lists available at ScienceDirect

Discrete Mathematics journal homepage: www.elsevier.com/locate/disc

Note

Almost all graphs are rigid—revisited Jens Kötters Faculty of Information Technology, Monash University, Clayton, Victoria 3800, Australia

article

info

Article history: Received 2 January 2006 Accepted 25 November 2008 Available online 21 January 2009 Keywords: Almost all graphs Rigid graphs Unretractive graphs

abstract It is shown that almost all graphs are unretractive, i.e. have no endomorphisms other than their automorphisms. A more general result has already been published in [V. Koubek, V. Rödl, On the minimum order of graphs with given semigroup, J. Combin. Theory Ser. B 36 (1984) 135–155]. In the paper at hand, a different proof is presented, following an approach of P. Erdős and A. Rényi that was used in their proof [P. Erdős, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315] that almost all graphs are asymmetric (have a trivial automorphism group). The approach is modified using an algebraically motivated reduction to idempotent endomorphisms. Thesetake n the role of the automorphisms in the proof of Erdős and Rényi. A bound of O (n2 43 ) is provided for the ratio of retractive graphs among all graphs with n vertices, confirming an earlier statement by Babai [L. Babai, Automorphism groups, isomorphism, reconstruction, in: R.L. Graham, M. Grötschel, L. Lovász (Eds.), in: Handbook of Combinatorics, vol. 2, Elsevier, Amsterdam, 1995, pp. 1447–1540]. The fact that almost all graphs are unretractive and asymmetric can be summarized in the statement that almost all graphs are rigid (have a trivial endomorphism monoid), and the same bound can be obtained for corresponding ratios of nonrigid graphs. © 2008 Elsevier B.V. All rights reserved.

1. Introduction A graph is considered to be a pair (V , E ), with V being a finite nonempty set of vertices and E ⊆ {k ⊆ V | |k| = 2} the set of its edges. The set of all automorphisms of a graph G is denoted by Aut(G). In case Aut(G) contains only the identity, G is called asymmetric. The set of all endomorphisms of a graph G is denoted by End(G), and in case End(G) contains only the identity, G is called rigid. Furthermore, G is called retractive if End(G) \ Aut(G) 6= ∅, otherwise it is called unretractive. Obviously, a graph is rigid if and only if it is asymmetric and unretractive. I denote by [n] the set of numbers {1, 2, . . . , n} (n ∈ N \ {0}) and by G(n) the set of all graphs with vertex set [n]. If, for a property P of graphs, GP (n) denotes the subset of G(n) containing the graphs with property P, then almost all graphs are |G (n)| said to have property P if limn→∞ |GP(n)| exists and is equal to 1. It is a known fact that almost all graphs are asymmetric. This follows from a result of George Pólya, namely that the sequence of the numbers of isomorphism classes on G(n) (the isomorphism classes are also termed unlabeled graphs) is asymptotically equivalent to |G(n)|/n!. The result first appeared in [3], however no proof was given there. An accordant proof can be found in [4] (Section 2.4, 4.1, 9.1 and 9.4). A proof that almost all graphs are asymmetric which is based on the same principles but uses a different approach is contained in [2]. Let us denote by GS (n) the subset of G(n) containing the graphs which are not asymmetric, and by Sn∗ the set of all nonidentical permutations of [n]. It is easy to see that the following inequality holds:

|GS (n)| ≤

X

|{G ∈ G(n) | ϕ ∈ Aut(G)}|.

ϕ∈Sn∗ E-mail address: [email protected] 0012-365X/$ – see front matter © 2008 Elsevier B.V. All rights reserved. doi:10.1016/j.disc.2008.11.031

(1)

J. Kötters / Discrete Mathematics 309 (2009) 5420–5424

5421

Erdős and Rényi derive a formula for the quantities |{G ∈ G(n) | ϕ ∈ Aut(G)}| and then find different estimates for it |G (n)| depending on the number of fixed points of ϕ . Together, these estimates imply that |GS(n)| → 0 as n → ∞. The latter means that almost all graphs are asymmetric. I have learned from Aleš Pultr that the result that almost all graphs are rigid was announced by Erdős in the mid sixties (also reported in [5, pg. 1237]), and that the question whether rigid graphs (save for the one-vertex graph) exist at all was still an open problem at that time. Erdős himself asked for finding concrete examples, and the first one (having 14 vertices) was presented in [5]. In [6], a constructive proof is given for the existence of a rigid graph with any number of vertices n ≥ 8, and it is shown that there exists no rigid graph with 2 ≤ n ≤ 7 vertices. A similar result for the edges is presented in [7]. According to the results of my investigations, Erdős has never published a proof that almost all graphs are rigid. László Babai states in [1, pg. 1461] that such a proof can be obtained by upgrading the proof given in [2]. Babai also states that n the ratio of nonrigid graphs among the graphs of G(n) lies in O (n2 43 ). The paper at hand shows how this result can be obtained. Another, substantially different proof can be found in the literature ([10, section I] and [8, pg. 94–96]). I will first give an outline of my own proof and then of the other proof. By the remark concluding the first paragraph of this section, it suffices to show that almost all graphs are unretractive. A transformation ϕ of a set A (i.e., a mapping ϕ : A → A) is called idempotent if it satisfies ϕ 2 = ϕ . Every transformation of a finite set has a uniquely determined idempotent power. This can be seen as follows: Let ϕ be a transformation of a finite set A. Because A is finite, ϕ a = ϕ a+k must hold for some a, k ∈ N, k 6= 0. If there is an idempotent power of ϕ , it can be represented as ϕ a+r with 0 ≤ r < k (this is easy to see if a is chosen minimal). The power ϕ a+r is idempotent iff there exists an m ∈ N such that 2(a + r ) = a + r + mk or, equivalently, a + r = mk. There is exactly one such r with 0 ≤ r < k, and therefore exactly one idempotent power of ϕ . A good illustration of this fact can be found in [9]. We denote by GR (n) the subset of G(n) containing the retractive graphs, and by In∗ the set of all nonidentical idempotent transformations of [n]. The idempotent power of a transformation of a finite set is the identity if and only if the transformation is bijective. Hence, the idempotent power of an endomorphism ϕ of a graph G ∈ G(n) is the identity if ϕ is an automorphism of G, otherwise it is an endomorphism of G belonging to the set In∗ . A graph is thus retractive if and only if it has an endomorphism belonging to the set In∗ . This observation gives rise to an upper bound for the number of retractive graphs with n vertices (cf. (1)):

|GR (n)| ≤

X

|{G ∈ G(n) | ϕ ∈ End(G)}|.

(2)

ϕ∈In∗

In the following section it will be shown that the set In∗ can be covered by some sets Mi (n), i = 1, . . . , 4, such that there

exist upper bounds Ai (n) ≥ |Mi (n)| and Bi (n) ≥ maxϕ∈Mi (n) |{G ∈ G(n) | ϕ ∈ End(G)}| with limn→∞ 2−( 2 ) Ai (n)Bi (n) = 0. n

Note that 2( 2 ) = |G(n)|. It then follows from inequality (2), that almost all graphs are unretractive: n

4 Ai (n)Bi (n) |GR (n)| X ≤ → 0. n n→∞ |G(n)| 2( 2 ) i =1

The proof by Koubek and Rödl will be illustrated as it appears in the book of Hell and Nešetřil [8]. By definition, the random graph G(n, 12 ) is with equal probability one of the elements of G(n) (the number 12 gives the ‘‘edge probability’’).

For a given  > 0, five properties are stated which the random graph G(n, 12 ) asymptotically almost surely has. In other words, almost all graphs have these properties. One of these properties is that the degree of each vertex differs from the 1 expectation value 2n by at most  2n . In [10], only the case  = 10 is considered, and the property is proven differently. Another property is that the largest clique (as well as the largest independent set) has fewer than (2 log2 n)(1 + ) vertices. This is a result of Erdős. The other properties are of the same type and are not proven in [8], but are proven in [10]. It is shown that every homomorphism between two graphs G, H ∈ G(n) with these properties must be bijective. This implies that almost all graphs are unretractive. The proof in this paper is elementary, it develops further the idea of the proof of Erdős (for asymmetry) using the algebraically motivated reduction to idempotent endomorphisms. The proof in [10] and in [8] focusses on graphs with a well-balanced structure in the sense that the five properties hold, rather than on unretractive graphs. In fact, the proof at |G (n)| hand provides a bound of O (n2 ( 43 )n ) on |GR(n)| (previously stated by Babai, [1]), whereas the corresponding bounds given in [10] and in [8] are not better than O (n−20 ln n ). 2. Main part Recall from the introduction that

|GR (n)| ≤

X

|{G ∈ G(n) | ϕ ∈ End(G)}|.

ϕ∈In∗

Let c1 , . . . , ck denote the fixed points of some transformation ϕ ∈ In∗ . Because ϕ is idempotent, the sets Ci := {x ∈ [n] | ϕ(x) = ci },

1 ≤ i ≤ k,

which may be referred to as the ϕ -orbits, form a partition of [n].

5422

J. Kötters / Discrete Mathematics 309 (2009) 5420–5424

Lemma 1. Let ϕ ∈ In∗ , and let C1 , . . . , Ck be the ϕ -orbits. Then

Y

|{G ∈ G(n) | ϕ ∈ End(G)}| =

(1 + 2|Ci ||Cj |−1 ).

1≤i
Proof. Consider the possible edge sets a graph with endomorphism ϕ can have. Suppose that G is such a graph and K is the set of its edges. Define Ci,j := {{x, y} | x ∈ Ci , y ∈ Cj },

1 ≤ i ≤ j ≤ k,

and note that

[

K =

(K ∩ Ci,j ).

(3)

1≤i≤j≤k

Let c1 , . . . , ck denote the fixed points of ϕ which lie in C1 , . . . , Ck , i.e. ϕ(x) = ci for x ∈ Ci . Because ϕ is an endomorphism of G, K ∩ Ci,j 6= ∅ implies that {ci , cj } is an edge of G. So, for 1 ≤ i < j ≤ k, either K ∩ Ci,j = ∅ or K ∩ Ci,j is one of the 2|Ci ||Cj |−1 subsets of Ci,j containing {ci , cj }. For 1 ≤ i = j ≤ k, only K ∩ Ci,j = ∅ is possible. According to (3), then, K must necessarily be Q one of 1≤i
  n  |GR (n)| 3 = O n2 . |G(n)| 4 Proof. Let ϕ ∈ In∗ , and let C1 , . . . , Ck be the ϕ -orbits. We begin with putting Lemma 1 slightly different: P

|{G ∈ G(n) | ϕ ∈ End(G)}| = 21≤i
|Ci ||Cj |

Y  1≤i
1 2|Ci ||Cj |

+

1 2



.

(4)

Let us denote by j1 (ϕ) the number of ϕ -orbits which have exactly one element and by ∆(ϕ) the number of ϕ -orbits which have more than one element. Note that ∆(ϕ) ≥ 1, because ϕ is not the identity. Without loss of generality we can assume that |C1 |, . . . , |C∆(ϕ) | ≥ 2 and |C∆(ϕ)+1 | = · · · = |Ck | = 1. We will now establish a different bound on the right-hand side of (4) for each of four different cases that are chosen with regard to j1 (ϕ) and ∆(ϕ). I have found it convenient to make the following distinction, which covers all possible values of j1 (ϕ) and ∆(ϕ) that can occur with a given ϕ ∈ In∗ : Case 1 (j1 (ϕ) ≤ n − n0.9 , ∆(ϕ) ≤ n0.6 ). It can be readily seen that

 X

|Ci ||Cj | =

1≤i
1 2



!2 X



|Ci |

X



1≤i≤k

2

|Ci |  ≤

1≤i≤k

1 2

! X

2

n −

2

|Ci |

.

(5)

1≤i≤∆(ϕ)

Furthermore, we can see that

X

|Ci | ≥

1≤i≤∆(ϕ)

!2

1

X

∆(ϕ)

1≤i≤∆(ϕ)

2

|Ci |

=

(n − j1 (ϕ))2 ≥ n1.2 , ∆(ϕ)

(6)

where the first inequality arises from the Cauchy–Schwarz inequality. Applying (6) to (5), we get

X 1≤i
|Ci ||Cj | ≤

1 2

(n2 − n1.2 ).

The product term in (4) is bounded by 1, and we obtain n 1 1.2 |{G ∈ G(n) | ϕ ∈ End(G)}| ≤ 2( 2 ) · 2− 2 n +O (n) .

Note that in the inequality above, ‘‘O (n)’’ was used as a convenience notation for the term in an inequality, we will still interpret the ‘‘≤’’ as a comparison between numbers.

(7) ‘‘ 12 n’’.

When using the O -notation

J. Kötters / Discrete Mathematics 309 (2009) 5420–5424

5423

Case 2 (∆(ϕ) ≥ n0.6 ). In this and the remaining cases, we shall use the estimate P 1≤i
|Ci ||Cj |

2

n ≤ 2( 2 ) .

The product term in (4) contains



∆(ϕ)



2



Y  1≤i
1 2|Ci ||Cj |

+

1



 ≤

2

9



factors with |Ci |, |Cj | ≥ 2, which yields

∆(ϕ)





2



16

9

 21 n1.2 − 12 n0.6

16

.

Putting this together, we have n |{G ∈ G(n) | ϕ ∈ End(G)}| ≤ 2( 2 ) ·



 21 n1.2 +O (n0.6 )

9 16

.

(8)

Case 3 (n − n0.9 ≤ j1 (ϕ) ≤ n − 3). The product term has ∆(ϕ)j1 (ϕ) factors with |Ci | ≥ 2 and |Cj | = 1. It is either ∆(ϕ) ≥ 2 and

Y  1≤i
1 2|Ci ||Cj |

+

1

 ∆(ϕ)j1 (ϕ)

 ≤

2

3

 ≤

4

9

n−n0.9

16

or ∆(ϕ) = 1, |C1 | = 3 and

Y  1≤i
1 2|Ci ||Cj |

+

1 2

 n−n0.9

 j1 (ϕ)

 ≤

5

5



8

8

.

Thus we have

|{G ∈ G(n) | ϕ ∈ End(G)}| ≤ 2( 2 ) · n

 n+O (n0.9 ) 5

8

.

(9)

Case 4 (j1 (ϕ) = n − 2). In the same fashion as in Case 3, it can be seen that

|{G ∈ G(n) | ϕ ∈ End(G)}| ≤ 2( 2 ) · n

 n−2 3

4

.

(10)

Note that j1 (ϕ) = n − 1 is not possible and j1 (ϕ) = n holds only for the identity. In accordance with the above cases of ϕ , set M1 (n) := {ϕ ∈ In∗ | j1 (ϕ) ≤ n − n0.9 , ∆(ϕ) ≤ n0.6 }, M2 (n) := {ϕ ∈ In∗ | ∆(ϕ) > n0.6 }, M3 (n) := {ϕ ∈ In∗ | n − n0.9 < j1 (ϕ) < n − 2}, M4 (n) := {ϕ ∈ In∗ | j1 (ϕ) = n − 2}. The cardinalities of M1 (n) and M2 (n) can be estimated by the total number of transformations of [n]:

|M1 (n)|, |M2 (n)| ≤ nn .

(11)

For the number of elements of M3 (n), a closer bound will be needed. Since all transformations in M3 (n) have more than n − n0.9 fixed points, and since for ` ∈ N the number of idempotent transformations of [n] which have exactly ` fixed points n is ` `n−` , we get

|M3 (n)| ≤

X n `n−` ≤ ` 0.9

`>n−n

X

n2n

0.9

≤ n2n

0.9 +1

.

(12)

`>n−n0.9

The elements of M4 (n) are the transformations with n − 1 fixed points:

|M4 (n)| = n(n − 1).

(13)

5424

J. Kötters / Discrete Mathematics 309 (2009) 5420–5424

Using inequalities (7) through (13), finally we have

|GR (n)| 1 X 1 1.2 ≤ n |{G ∈ G(n) | ϕ ∈ End(G)}| ≤ |M1 (n)| · 2− 2 n +O (n) ( ) |G(n)| 2 2 ϕ∈I∗ n

+ |M2 (n)| ·



 21 n1.2 +O (n0.6 )

9 16



1 1.2 +O (n log n)

≤ 2− 2 n |G (n)|

This shows that |GR(n)| = O (n2

+

3 n 4



).

9

+ |M3 (n)| ·

 12 n1.2 +O (n log n)

16

 n+O (n0.9 ) 5 8

+ |M4 (n)| ·

 n+O (n0.9 log n) +

5 8

  n −2 3 4

+ n(n − 1)

 n−2 3

4

.



The same bound holds for the nonrigid graphs, as well. We denote by GN (n) the subset of G(n) containing the nonrigid graphs. Corollary 3. Almost all graphs are rigid. More exactly,

  n  3 |GN (n)| = O n2 . |G(n)| 4 Proof. For the graphs which are not asymmetric, we have

  n  1 |GS (n)| = O n2 , |G(n)| 2 see e.g. [1, pg. 1461].



Acknowledgements The author thanks Ulrich Knauer for his support and Aleš Pultr for his correspondence. The author also thanks an anonymous referee for making him aware of the proof of Koubek and Rödl. References [1] L. Babai, Automorphism groups, isomorphism, reconstruction, in: R.L. Graham, M. Grötschel, L. Lovász (Eds.), in: Handbook of Combinatorics, vol. 2, Elsevier, Amsterdam, 1995, pp. 1447–1540. [2] P. Erdős, A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963) 295–315. [3] G.W. Ford, G.E. Uhlenbeck, Combinatorial problems in the theory of graphs, IV, Proc. Natl. Acad. Sci. USA 43 (1957) 163–167. [4] F. Harary, Graphical Enumeration, Academic Press, New York et al., 1973. [5] Z. Hedrlín, A. Pultr, Symmetric relations (undirected graphs) with given semigroups, Monatsh. Math. 69 (4) (1965) 318–322. [6] Z. Hedrlín, A. Pultr, On rigid undirected graphs, Canad. J. Math. 18 (6) (1966) 1237–1242. [7] P. Hell, Rigid undirected graphs with given number of vertices, Comment. Math. Univ. Carolin. 9 (1968) 51–69. [8] P. Hell, J. Nešetřil, Graphs and Homomorphisms, Oxford U. Press, Oxford, 2004. [9] M. Kilp, U. Knauer, A. Mikhalev, Monoids, Acts and Categories, Walter de Gruyter, Berlin et al., 2000. [10] V. Koubek, V. Rödl, On the minimum order of graphs with given semigroup, J. Combin. Theory Ser. B 36 (1984) 135–155.