您的当前位置：首页 DISCRETE

DISCRETE

来源：尚车旅游网

DISCRETE MATHEMATICS ELSEVIER Discrete Mathematics 202 (1999) 227-238 Complete tripartite subgraphs in the coprime graph of integers GAbor N. SirkGzy” Computer Science Department, Worcester Polytechnic Institute. Worcester, MA 01609. USA Received 16 October 1997; revised 3 September 1998; accepted 14 September 1998 Dedicated to the memory of Paul Erd6s Abstract We denote by f(n, k) the number of positive integers m no,AC{1,2,...,n} with lAl>f(n,2) (if61n then f(n,2)= in), then the coprime graph induced by A contains a complete tripartite graph on 2 Lc,,,~~~;,,, J + 1 vertices where one of the classes is a single vertex and the other two classes each have Lc&$&--J vertices. @ 1999 Elsevier Science B.V. All rights reserved Keywords: Combinatorial number theory; Graph theory; Graphs on integers 1. Introduction 1.1. Notations and definitions Let (a,b) denote the greatest common divisor and [a,b] the least common multiple of integers a, b. Consider the coprime graph on the integers. This is the graph whose vertex set is the set of integers and two integers a, b are connected by an edge if and onlyif(a,b)=l.LetAc{1,2 ,..., n} be a set of positive integers. The coprime graph of A, denoted by G(A), is the induced coprime graph on A. A(,,,) denotes the integers ai E A, ai 3 u(modm). 4(n) denotes Euler’s function, u(n) denotes the number of distinct prime factors of n and p(n) is the Moebius function. V(G) and E(G) denote the vertex set and edge set of a graph G. K,, is the complete graph on n vertices, K(nl,nz,. . ., n,) denotes the complete v-partite graph with color classes Ur,lJz,...,U, such that IUlI=nl, \\Uz\\=nz,...,(U,(=n,. Cl is the cycle on I vertices. H is a subgraph of G, denoted by H c G, if V(H) c V(G) and * E-mail: gsarkozy@cs.wpi.edu. 0012-365x/99/$ - see front matter @ 1999 Elsevier Science B.V. All rights reserved PII: SOO12-365X(98)00359-8 228 G.N. &irk&y/ Discrete Mathematics 202 (1999) 227-238 E(H) c E(G). No(v) denotes the set of neighbors of the vertex u in the graph G and &go(v)= INo(v)l. We write N(pl,pz,... ) = ni N(pi), the set of common neighbors. 1.2. The coprime graph of integers Recently the investigation of various graphs on the integers has received significant attention (see e.g. ‘Graphs on the integers’ in [12]). The most popular graph seems to be the coprime graph, although there are many attractive problems and results con- cerning the divisor graph ([8,9,14,16]). Several researchers studied special subgraphs of the coprime graph. Perhaps the tist problem of this type was raised by Paul Erdiis in 1962 [7]: What is largest set Ac{1,2,..., G(A)? Of course, the n} such that Kk @ set of m dn which have a prime factor among the first k - 1 primes is such a set (let us denote the cardinality of this set by f(n, k - l)), and Erdijs conjectured that For k = 2,3 this is trivial, and for k = 4 it was proved this set gives the maximum. by Szabo and T&h [ 171. However, the conjecture recently was disproved by Ahlswede and Khachatrian [l]. They also gave some positive results in [2] and [3]. Another interesting question is what conditions guarantee a perfect matching in the coprime graph. Newman conjectured more than 25 years ago, that if Ii = { 1,2,. . . , n} and 12 is any interval of n consecutive integers, then there is a perfect coprime match- ing from II to I,. This conjecture was proved by Pomerance and Selfridge [ 151 (see also [4]). Note that the statement is not true if Ii is also an arbitrary interval of n consecutive integers. Example: Ii = {2,3,4} and 12 = {8,9, lo}, any one-to-one cor- respondance between II and I2 must have at least one pair of even numbers in the correspondance. In [l l] Paul Erdijs and I investigated another natural question of this type (also initiated by Erdiis), namely what can we say about cycles in G(A). The case of even cycles is not hard from earlier results (see [l 11). As it was mentioned above to guar- antee a triangle we need at least f(n,2) + 1 = 151 + [fJ - L%J + 1 (= in + 1 if 6jn) numbers. In [ 1 l] we showed that somewhat surprisingly this cardinality already guar- antees the existence of odd cycles of ‘almost’ every length. More precisely we proved that there exist constants c, 110 such that if n ano, A c { 1,2,. . . , n} and (A] > f(n, 2), then C21+i c G(A) for every positive integer I< cn. In his last problem collection paper [5] (completed just days before his death) Paul described our result [ 1 l] and then he concluded: “Perhaps G(A) contains for every fixed 1 and n > no( I) a complete tripartite graph of 21 + 1 vertices where one of the classes is a single vertex and the other two classes each have I vertices. If true it would be of interest to determine (or estimate) the largest possible value of I = f(n). Several other problems are investigated and theorems are proved. We hope to return to this problem in the near future (if there is a future for me), but Sarkozy will surely return to these problems”. Sadly, due to Paul’s death, we have not been able to continue the work jointly. It is a tremendous honor for me to fulfill Paul’s moving prediction with this paper. G. N. Sdrkiizy I Discrete Mathematics 202 (1999) 227-238 229 Indeed, I will show that our methods in [l l] can be adopted and extended to prove the following theorem. Theorem 1. There exist constants c,no such that if n&no, A C { 1,2,. . . ,n} and (Al >f(n,2), then K(1, L I) c G(A) for I= Lcal. As mentioned above, it would be interesting to determine here the best possible value of I for which the theorem remains true. Clearly, for one of the color classes of the complete tripartite subgraph we cannot say more than a single vertex, since we may take A={m/mfh2>, IA(6,l)l =s1, I&6,5)1 =s2> (1) (l<)s~ +s2bcln, (2) then K(l,Z,l)cG(A)for I= L c2 log n log log log n 1 ’ (3) Theorem 3. For every E > 0, there exist constants c3 = Q(E) and nz = nz(.z) such that if nan2, IPI >f(n,2), I&6,1)1 =sl, I&6,5)1 =s2, sl +s23w, then K(l,Z,Z)cG(A) I= Lcj lognj. for (4) 2. Proofs 2.1. Proof of Theorem 2 We may assume without loss of generality that si = max(si,s2). The rough outline of the construction of a K( 1, I, 1) in G(A) is the following: First we will pick a number a E Ace, 1) with relatively large 4(a) as the class consisting of the single vertex and the two other classes with I numbers will be chosen from A(Q) and 46,3), respectively. 230 G. M. Sirkiizy I Discrete Mathematics 202 (1999) 227-238 We need the following lemma: Lemma 1. The number of integers 16kGn satisfying 4(k)/k < l/t is less than y1 exp( - exp c4 t ) (where expz = ez), uniformly in t > 2. This lemma can be found in [6]. We apply Lemma 1 with tAoglog% c4 Sl (5) (Using (2), t > 2 holds for small enough cl .) Then the number of integers 1 l/t. The number of those integers u, for which 0<6u+2n3 then o(n)<2-----. log n log log n This lemma implies that in (6), for large enough n, the number of terms is 244 < 2 log log n . Indeed, if a cz n3 this is trivial, and if a > n3, then w(a)<2--- log a log log a 62-, log n log log n log u is increasing if u is large enough (see [13, p. 3941). since the function g(u) = 2--- log log u G. N. Sbrkiizy I Discrete Mathematics 202 (1999) 227-238 231 Thus c la--- n-2 6 c Ad) -- d 2]08n 2 loglogn u:6u+2 f(2, n) by (1 ), and trivially k+6,0)1 + h6,3)\\ + \\‘$6,4)\\%f(2,d - so that n-2 l&6,2)1 > 6 I J - (SI + a). Now, using the above along with (2), c 1 (bu+2,a) = I, 6u+2EA~s,z), 6u+2 1,: 614 + 2 ‘t’ t’ Let us denote the set of these integers by B. Thus we have (7) Let F = A(Cj3). Note that using (1) and (2) again for small enough cr. We define a bipartite graph G’ between B and F as follows: We = 1. have an edge between a b E B and an f E F if and only if (ab, f) 232 G.N. Srirkb’zylDiscrete Mathematics 202 (1999) 227-238 Next we estimate INot( for an arbitrary b E B. Put E = {ab 1 b E B} and let us take an e = ab E E. The number of those integers u, for which 6u+3l= c 12% u:6u+34n. (6uf3,e) = i, 6U+3EA@.3) G. N. Sbrkiizy I Discrete Mathematics 202 (1999) 227-238 233 Claim 1. K( I, 1) c G’. Proof of Claim. Using (3), (5), (7) and (11) we get (12) Here we also have I{fEFldeg(f)~Z}( since otherwise JE(G’)i<& ’ 9t= + lFlZ<(Bjz St2 ’ a$, (13) a contradiction with (11). To find a lower bound on the number of subsets of B of size Z with a common neighbor in F, we use Jensen’s inequality on convex functions, (8), (12) and (13) to obtain de&j) > I However, there are only subsets of B of size 1. Hence, there must be a B’ c B such that IB’l=Z and INGOING ---- ’ where we used (3), (5) and the fact that c2 is sufficiently small. Denote the elements of B’ by bt, b2,. . . , bl and choose 1 integers f~, fz,. . . , fj from Np(B’). Then G(A)l{b, . .../ b,,/i . .. . . f,} is a K(Z, Z) in G’ completing K( 1, I, I) in G(A). 2.2. Proof of Theorem 3 Here we assume that s2 > zn, the case st 2 :n is similar. Denote by P,. the product of the primes not exceeding Y. The rough outline of the proof will be the following: the proof of the claim. By adding a we get the desired 234 G.N. Sdrktizy IDiscrete Mathematics 202 (1999) 227-238 First we find 3 positive integers jr, j2 and js such that (jt , j2) = (jl , j3) = (jz, j3) = 1 and ]Acp,.,j,)I is relatively large for each i = 1,2,3. We construct a K( 1, I, 1) in G(A) in the following way: First we will pick a number a EA~~,J, 1 with relatively large @(a) as the class consisting of the single vertex and the two other classes with I numbers will be chosen from A~P,,,J~) and A(PJ~), respectively. We will need the following lemma. Lemma 3. For every o>O and 6 > 0, there exists an ro = ro(a, 6) such that if r>ro, n>n4(a,6,r) and u~{1,2 ,..., P,.}, then for all but a$ integers k satisfying 1 dkl-6. plk This lemma can be found in [lo]. Now we prove Theorem 3. Let r denote a positive integer for which r aro( I, i ). We evidently have x(kP,,6i-I)( i=l = k6,0)( f IA(P,,6i)I + ” f lA(Pr,6i+5)/) + &6,1)( + ’ ’ ‘+ k6,4)1 -tw(6,5)~+~ + k6,5)+fw+S2 2 >-n-2+ 3 ;ir. Hence there exists an io for which &P,,6io--l)l + /A(P,,6io)l + . ” + &P,,6io+5)1 2 -n+4n-2 > 3 2 pi 6 4n = 7 r + 3&$ r - F. r (14) Clearly for every u n lL4P,,u)l

~$ for all i= 1,2,3. G. N. &irk&y/ Discrete Mathematics 202 (1999) 227-238 235 In that case (15) and (18) imply that there exist integers ~1,. . . ,245 such that Odu, < ... ~$ since otherwise &P,,6io)l + . . r + 2: f =4$ + sp + 4 r I r with (18). which would hold in contradiction From (19) it follows that the sequence (6io +ul , . . . , 6io + US} contains a subsequence erms which are pairwise relatively prime, proving our claim in this {jl,jZ,j3} of 3 t case. (p,,6io+5)( < z $ is similar. Thus now we may assume that The case when (A In this case we choose ji = 6i0 - 1 and j3 = 6io + 5. For j2 we choose one from the integers 6i0 + 1,6ie -t- 2 and 6io + 3 for which (there must be one such a j2) and then (16) and (17) clearly hold. Thus the claim is proved, we have jl, j2 and j3 satisfying (16) and (17). Let a denote a positive integer for which a~A(p,,j,) and l-I Pb P’r (1-i) >l-;. (20) Lemma 3 and the choice of r guarantee that such an a exists. We are going to estimate from below the number of solutions b of (a,b)= 1, b EA(P,,jz). (21) Assume that pl(a,d) for some d z jZ(modP,). Since (jr,j,)= 1 we clearly have p > r. Denote by h(F’,., j,z) the number of those integers d for which d 1 - $ <2w(“)<22*. 236 G. N. &irk&y I Discrete Mathematics 202 (1999) 227-238 From this and (20) we get for large n > n - 2210glogn > n. ( ” > ( B > 8 Pr 1 - 1 - log n 4 p, (22) Denoting the number of solutions of (21) by X, we have by (17) and (22) (23) Therefore using Lemma 3 there are at least (~/20)(n/P,) and integers b satisfying (21) l-I p>, db (1 -J-) > (I-;). (24) Let us denote the set of these integers by B. We have We denote by F the set of integers f E AcP,,jj). Again we define a bipartite graph G” between B and F as follows: We have an edge between a b E B and an f E F if and only if (ab, f) = 1. or an arbitrary b E B. Put E = {ab 1 b E B} and let us Next we estimate (Np(b)j f take an e=abEE. From (16), if g = js(modP,) and p)(e,g), then p>r. Again we have G.N. Shrk6zy I Discrete Mathematics 202 (1999) 227-238 231 We obtain from this, (20) and (24) for large enough n that h(P,., j,,e) > k n (1 - $) dr - Z4s p>r =;-J a P>r (*_$_) 5 (I-g-24* P’? > ( > l--- E2\"_24*> 8 Pr ( > 1-E 14_ 4 P,’ (26) Eqs. (17) and (26) yield that (27) Claim 2. K( I, 1) c G”. Proof of Claim. Using (4), (15), (25) and (27) we get (28) Here we also have I{fEF(deg(f)>l}l since otherwise IE(G”)l$~IBI a$!, +lFlZ<)BI;;, Y (29) a contradiction with (27). To find a lower bound on the number of subsets of B of size 1 with a common neighbor in F, we use Jensen’s inequality, (15), (28) and (29) to obtain ftF 238 G.N. Shrkiizy I Discrete Mathematics 202 (1999) 227-238 However, using (15) there are only (i;j)< (AY)‘< (22) subsets of B of size 1. Hence, there must be a B’ c B such that JB’I=Z and where we used (4), (17) and the fact that c3 is sufficiently small. Denote the elements of B’ by bl , b2, . . . , bl and choose 1 integers f~, f2, . . . , fl from NG” (B’). Then G(‘%, 1..., b&./i 1...,. h) the proof of the claim. By adding a we get the desired is a K(1, I) in G” completing K(l,Z,Z) in G(A). References [l] R. Ahlswede, L.H. Khachatrian, On extremal sets without coprimes, Acta Arith. 66 (1994) -99. [2] R. Ahlswede, L.H. Khachatrian, Maximal sets of numbers not containing k+ 1 pairwise coprime integers, Acta Arith. 72 (1995) 77-100. [3] R. Ahlswede, L.H. Khachatrian, Sets of integers and quasi-integers with pairwise common divisor, Acta Arith. 74 (1996) 141-153. [4] M.J. Baines, D.E. Daykin, Coprime mappings between sets of consecutive integers, Mathematika 10 (1963) 132-136. [5] P. Erdos, Some of my new and almost new problems and results in combinatorial number theory, Proc. 1996 Eger Number Theory Conference. [6] P. Erdos, Some remarks about additive and multiplicative functions, Bull. Amer. Math. Sot. (1946) 527-537. [7] P. Erdijs, Remarks in number theory, IV, Mat. Lapok 13 (1962) 228-255 (in Hungarian). [8] P. ErdGs, R. Freud, N. Hegyvari, Arithmetical properties of permutations of integers, Acta Math. Acad. Sci. Hung. 41 (1983) 169-176. [9] P. Erdiis, C. Pomerance, Matching the natural numbers up to n with distinct multiples in another interval, Nederl. Akad. Wetensch. Proc. Ser. A 83 (1980) 147-161. [IO] P. Erdos, A. Sarkozy, E. Szemeredi, On some extremal properties of sequences of integers, I, Ann. Univ. Sci. Budapest Eiitvos 12 (1969) 131-135; II, Publ. Math. Debrecen 27 (1980) 117-125. [l l] P. Erdos, G.N. Sarkozy, On cycles in the coprime graph of integers, Electron. J. Combin. 4 (2) (1997) R8. [12] R.L. Graham, M. Griitschel, L. Lovasz (Eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995. [13] I. Niven, H.S. Zuckerman, H.L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, New York, 1991. [14] C. Pomerance, On the longest simple path in the divisor graph, Congr. Numer. 40 (1983) 291-304. [15] C. Pomerance, J.L. Selfridge, Proof of D.J. Newman’s coprime mapping conjecture, Mathematika 27 (1980) 69-83. [16] E. Saias, Etude du graphe divisoriel, I, Periodica Math. Hung., to appear. [17] C. Szabo, G. T&h, Maximal Sequences not containing 4 pairwise coprime integers, Mat. Lapok 32 (1985) 253-257 (in Hungarian).

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文