\documentstyle[12pt]{article} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 4 (no. 2)(1997), \#R8\hfill} \thispagestyle{empty} \topmargin -0.25in \textheight 9in\textwidth 6.5in\oddsidemargin 0in\evensidemargin 0in % \setlength{\oddsidemargin}{3.25in}\addtolength{\oddsidemargin} %{-0.5\textwidth} % \setlength{\evensidemargin}{3.25in}\addtolength{\evensidemargin} %{-0.5\textwidth} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{fact}{Fact} \newtheorem{sublemma}{Sublemma} \newtheorem{conjecture}{Conjecture} \newtheorem{definition}{Definition} \def\bs{\bigskip}\def\noi{\noindent} \def\bc{\begin{center}}\def\ec{\end{center}} \newcommand{\text}[1]{\quad\mbox{#1}\quad} \def\beq{\begin{equation}}\def\eeq{\end{equation}} \def\beqn{\begin{eqnarray}}\def\eeqn{\end{eqnarray}} \def\bd{\begin{eqnarray*}}\def\ed{\end{eqnarray*}} \def\pont{\hspace{-6pt}{\bf.\ \ }} \def\eps{\varepsilon}\def\:{\!:} \def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi} \title{On cycles in the coprime graph of integers$^1$} \author{Paul Erd\H{o}s\\Mathematics Institute\\ Hungarian Academy of Sciences\\Re\'altanoda u. 13-15, H-1053\\ Budapest, Hungary \and Gabor N. Sarkozy\\Computer Science Department\\ Worcester Polytechnic Institute\\Worcester, MA 01609\\gsarkozy@cs.wpi.edu} \date{Submitted: June 20, 1996; Accepted: December 2, 1996} \begin{document} \maketitle \centerline{\sl Dedicated to Herbert S. Wilf on the occasion of his 65$^{th}$ birthday} \footnotetext[1]{Mathematics Subject Classification 11B75,05C38} \begin{abstract} In this paper we study cycles in the coprime graph of integers. We denote by $f(n,k)$ the number of positive integers $m\leq n$ with a prime factor among the first $k$ primes. We show that there exists a constant $c$ such that if $A\subset \{1, 2, \ldots , n\}$ with $|A| > f(n,2)$ (if $6|n$ then $f(n,2)=\frac{2}{3} n$), then the coprime graph induced by $A$ not only contains a triangle, but also a cycle of length $2 l + 1$ for every positive integer $l\leq c n$. \end{abstract} \section{Introduction} \subsection{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 only if $(a, b) = 1$. Let $A\subset \{1, 2, \ldots ,n\}$ be a set of positive integers. The {\em coprime graph} of $A$, denoted by $G(A)$, is the induced coprime graph on $A$. $A_{(m,u)}$ denotes the integers $a_i\in A, a_i\equiv u \; (mod \; m)$. $\phi(n)$ denotes Euler's function, $\omega(n)$ denotes the number of distinct prime factors of $n$ and $\mu(n)$ is the Moebius function. $V(G)$ and $E(G)$ denote the vertex set and edge set of a graph $G$. $K_n$ is the complete graph on $n$ vertices, $C_n$ is the cycle on $n$ vertices and $K(m, n)$ denotes the complete bipartite graph between $U$ and $V$, where $|U| = m, |V| = n$. $H$ is a subgraph of $G$, denoted by $H\subset G$, if $V(H)\subset V(G)$ and $E(H)\subset E(G)$. \subsection{The coprime graph of integers} Recently the investigation of various graphs on the integers has received significant attention (see e.g. {\em ``Graphs on the integers''} in \cite{GGL}). The most popular graph seems to be the coprime graph, altough there are many attractive problems and results concerning the divisor graph (\cite{EFH}, \cite{EP}, \cite{P} and \cite{S}). Several reasearchers studied special subgraphs of the coprime graph. Perhaps the first problem of this type was raised by the first author in 1962 (\cite{E2}): What is largest set $A\subset \{1, 2, \ldots ,n\}$ such that $K_k \not\subset G(A)$? Of course, the set of $m\leq n$ 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-1)$), and the first author conjectured that this set gives the maximum. For $k = 2, 3$ this is trivial, and for $k=4$ it was recently proved by Szab\'{o} and T\'{o}th \cite{ST}. However, the conjecture recently was disproved by Ahlswede and Khachatrian \cite{AK}. They also gave some positive results in \cite{AK1} and \cite{AK2}. Another interesting question is what conditions guarantee a perfect matching in the coprime graph. Newman conjectured more than 25 years ago, that if $I_1 = \{1, 2, \ldots ,n\}$ and $I_2$ is any interval of $n$ consecutive integers, then there is a perfect coprime matching from $I_1$ to $I_2$. This conjecture was proved by Pomerance and Selfridge \cite{PS} (see also \cite{BD}). Note that the statement is not true if $I_1$ is also an arbitrary interval of $n$ consecutive integers. Example: $I_1 = \{2, 3, 4\}$ and $I_2 = \{8, 9, 10\}$, any one-to-one correspondance between $I_1$ and $I_2$ must have at least one pair of even numbers in the correspondance. In this paper we are going to investigate another natural question of this type (also initiated by the first author), namely what can we say about cycles in $G(A)$. The case of even cycles is not hard from earlier results (at least for not too long cycles). In fact, if $l \leq \lfloor\frac{1}{10} \log \log n\rfloor$, for the largest set $A\subset \{1, 2, \ldots , n\}$ with $C_{2l} \not\subset G(A)$, we have $|A| = f(n,1) + (l-1) = \lfloor\frac{1}{2} n \rfloor + (l-1)$. This cardinality can be obtained by taking all the even numbers and the first $l-1$ odd primes, then obviously $C_{2l} \not\subset G(A)$. The upper bound follows from the following theorem in \cite{ESS}: If $n\geq n_0$, $|A_{(2,1)}| = s > 0$, $|A| > f(n,1)$ and $r = \min \{ s, \lfloor\frac{1}{10} \log \log n\rfloor\}$, then $K(r, r) \subset G(A)$. The case of odd cycles is more interesting. As it was mentioned above to guarantee a triangle we need at least $f(n,2) + 1= \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor - \lfloor \frac{n}{6} \rfloor + 1$ ($= \frac{2}{3} n + 1$ if $6|n$) numbers. Somewhat surprisingly this cardinality already guarantees the existence of odd cycles of ``almost'' every length. More precisely: \begin{theorem}\pont There exist contants $c, n_0$ such that if $n\geq n_0$, $A\subset \{1, 2, \ldots , n \}$ and $|A| > f(n,2)$, then $C_{2l+1} \subset G(A)$ for every positive integer $l\leq c n$. \end{theorem} It would be interesting to determine here the best possible value of the constant $c$. Perhaps it is $c=\frac{1}{6}$. One may obtain this trivial upper bound for $6|n$ by taking all the even numbers and the first $\frac{n}{6} + 1$ odd numbers for $A$; clearly $C_{2l+1}\not\subset G(A)$ for $l > \frac{n}{6}$. In the proof we will distinguish two cases depending on the size of $|A_{(6,1)}| + |A_{(6,5)}|$. The theorem will be an immediate consequence of the following two theorems: \begin{theorem}\pont There exist constants $c_1, c_2, n_1$ such that if $n\geq n_1$, \[ |A_{(6,1)}| = s_1, |A_{(6,5)}| = s_2, \; 1 \leq s_1 + s_2 \leq c_1 n, \] and \[ |A| > f(n,2), \] then $C_{2l+1} \subset G(A)$ for every positive integer $l\leq c_2 n$. \end{theorem} \begin{theorem}\pont For every $\epsilon > 0$, there exist constants $c_3 = c_3(\epsilon)$ and $n_2 = n_2(\epsilon)$ such that if $n\geq n_2$, \[ |A_{(6,1)}| = s_1, |A_{(6,5)}| = s_2, s_1 + s_2 \geq \epsilon n, \] and \[ |A| > f(n,2), \] then $C_{2l+1} \subset G(A)$ for every positive integer $l\leq c_3 n$. \end{theorem} \section{Proofs} \subsection{Proof of Theorem 2} We may assume without loss of generality that $s_1 = \max (s_1, s_2)$. We take an arbitrary $1\leq l \leq c_2 n$ positive integer. The rough outline of the construction of a $C_{2l+1}$ in $G(A)$ is the following: First we will pick a number $a\in A_{(6,1)}$ with relatively large $\phi(a)$ and the remaining $2l$ numbers will be chosen alternately from $A_{(6,2)}$ and $A_{(6,3)}$. We need the following lemma: \begin{lemma}\label{phi}\pont The number of integers $1\leq k \leq n$ satisfying $\frac{\phi(k)}{k} < \frac{1}{t}$ is less than $$n \exp ( - \exp c_4 t )$$ (where $\exp z = e^z$), uniformly in $t>2$. \end{lemma} This lemma can be found in \cite{E1}. We apply Lemma \ref{phi} with \begin{eqnarray}\label{te} t = \frac{1}{c_4} \log \log \frac{2n}{s_1} \end{eqnarray} ($t>2$ holds for small enough $c_1$). Then the number of integers $1\leq k \leq n$ for which $\frac{\phi(k)}{k} < \frac{1}{t}$ (where $t$ is defined by (\ref{te})) is less than $\frac{s_1}{2}$. Hence there exists an integer $a\in A_{(6,1)}$ satisfying $\frac{\phi(a)}{a} \geq \frac{1}{t}$. The number of those integers $u$, for which \[ 0 < 6 u + 2 \leq n \; \; \mbox{and} \; \; (6u + 2, a) = 1\] hold, is given by the following sieve formula \begin{eqnarray}\label{szita} \sum_{d | a} \mu(d) g_1(n, d), \end{eqnarray} where $g_1(n, d)$ denotes the number of those integers $v$, for which \[ 6 v + 2 \leq n \; \; \mbox{and} \; \; d | 6 v + 2. \] (i.e. $6 v \equiv - 2 \; \; (mod \; d)$.) It is clear from $(a, 6) = 1$, that \[ |g_1(n, d) - \frac{n - 2}{6 d}| \leq 1. \] We also use the following lemma: \begin{lemma}\label{omega}{\bf (see \cite{NZM}, page 394)} \pont There exists an $n_3$ such that if $n\geq n_3$ then $$\omega(n) < 2 \frac{\log n}{\log \log n}.$$ \end{lemma} This lemma implies that in (\ref{szita}), for large enough $n$, the number of terms is \[ 2^{\omega(a)} < 2^{2 \frac{\log n}{\log \log n}}. \] Indeed, if $a \frac{1}{t}.\] We choose $b_1$ arbitrarily from these integers. Applying Lemma \ref{phi} with \[ t'' = \frac{1}{c_4} \log \log \frac{1}{c_1}, \] the number of integers $1\leq k \leq n$ for which $\frac{\phi(k)}{k} < \frac{1}{t''}$ is at most $c_1 n$. Therefore the number of integers $1\leq k \leq n$ for which \begin{eqnarray}\label{bor} k\in A_{(6,2)} \; \; \mbox{and} \; \; \frac{\phi(k)}{k} \geq \frac{1}{t''} \end{eqnarray} is at least \[ \{1,2, \ldots ,n\}_{(6,2)} - ( s_1 + s_2 ) - c_1 n \geq \lfloor \frac{n-2}{6} \rfloor + 1 - 2 c_1 n \geq \frac{n}{7}, \] if $c_1$ is small enough. We choose $b_2, b_3, \ldots ,b_l$ as arbitrary numbers from the numbers satisfying (\ref{bor}). Let $b_{l+1} = a$. Put $e_i = [b_i, b_{i+1}]$ for all $1\leq i \leq l$. The number of those integers $u$, for which \[ 6 u + 3 \leq n \; \; \mbox{and} \; \; (6 u + 3, e_i) = 1\] is again clearly the following: \begin{eqnarray}\label{gszita} \sum_{d|e_i} \mu(d) g_2(n, d), \end{eqnarray} where $g_2(n, d)$ denotes the number of those integers $v$, for which \[ 6 v + 3 \leq n \; \; \mbox{and} \; \; d| 6 v + 3 \] (i.e. $6 v \equiv - 3 \; (mod \; d)$). Since $(6, a) = 1$, and $2|b_i$, but $3\not| b_i$ for all $1\leq i \leq l$, it is easy to see that \[ g_2(n, d) = \left\{ \begin{array}{ll} 0 \hspace{0.5in} &\mbox{if} \; \; 2| d\\ \frac{n-3}{6 d} + \epsilon &\mbox{otherwise,} \end{array} \right. \] where $|\epsilon| \leq 1$. Furthermore, in (\ref{gszita}) for large enough $n$ the number of terms is \[ 2^{\omega (e_i)} < 2^{2 \frac{\log (n^2)}{\log \log (n^2)}} < 2^{4 \frac{\log n}{\log \log n}}, \] where we again used Lemma \ref{omega}, $e_i \leq n^2$ and the fact that $g(u) = 2 \frac{\log u}{\log \log u}$ is increasing if $u$ is large enough. Therefore \[ \sum_{\begin{array}{c} u: 6u+3\leq n\\ (6u+3, e_i)=1 \end{array}} 1 = \sum_{\begin{array}{c} d|e_i, \\ 2\not| d \end{array}} \mu(d) g_2(n, d) \geq \] \[ \geq \frac{n - 3}{6} \prod_{ \begin{array}{c} p|e_i\\ 2\not|p \end{array}} \left( 1 - \frac{1}{p}\right) - 2^{4 \frac{\log n}{\log \log n}} \geq \] \[ \geq \frac{n - 3}{6} \prod_{p|e_i} \left( 1 - \frac{1}{p}\right) - 2^{4 \frac{\log n}{\log \log n}} \geq \] \[ \geq \frac{n - 3}{6} \prod_{p|b_i} \left( 1 - \frac{1}{p}\right) \prod_{p|b_{i+1}} \left( 1 - \frac{1}{p}\right) - 2^{4 \frac{\log n} {\log \log n}}. \] Hence for $i=1$ we have \[ \sum_{\begin{array}{c} u: 6u+3\leq n,\\ (6u+3, e_1)=1,\\ 6u+3\in A_{(6,3)} \end{array}} 1 \geq \frac{n-3}{6 t' t''} - 2^{4 \frac{\log n}{\log \log n}} - ( s_1 + s_2) \geq \frac{n} {7 t t''} - ( s_1 + s_2) \geq \frac{n}{8 t t''}. \] For $i=l$ we get \[ \sum_{\begin{array}{c} u: 6u+3\leq n,\\ (6u+3, e_l)=1,\\ 6u+3\in A_{(6,3)} \end{array}} 1 \geq \frac{n-3}{6 t'' t} - 2^{4 \frac{\log n}{\log \log n}} - ( s_1 + s_2) \geq \frac{n} {7 t'' t} - ( s_1 + s_2) \geq \frac{n}{8 t'' t}. \] Finally for $1< i < l$ \[ \sum_{\begin{array}{c} u: 6u+3\leq n,\\ (6u+3, e_i)=1,\\ 6u+3\in A_{(6,3)} \end{array}} 1 \geq \frac{n-3}{6 (t'')^2} - 2^{4 \frac{\log n}{\log \log n}} - ( s_1 + s_2) \geq \frac{n} {7 (t'')^2} - ( s_1 + s_2) \geq \frac{n}{8 (t'')^2}. \] Thus it is not hard to see that if $c$ is small enough then we may choose a different $f_i$ for each $1\leq i \leq l$ such that \[ (b_i, f_i) = (b_{i+1}, f_i) = 1 \; \; \mbox{and} \; \; f_i \in A_{(6,3)}. \] Then \[ a, b_1, f_1, b_2, f_2, \ldots , b_l , f_l, a \] is a $C_{2l+1}$ in $G(A)$ completing the proof of Theorem 2. \subsection{Proof of Theorem 3} Here we assume that $s_2 \geq \frac{\epsilon}{2} n$, the case $s_1 \geq \frac{\epsilon}{2} n$ is similar. Denote by $P_r$ the product of the primes not exceeding $r$. The rough outline of the proof will be the following: First we find 3 positive integers $j_1, j_2$ and $j_3$ such that $(j_1, j_2) = (j_1, j_3) = (j_2, j_3) = 1$ and $|A_{(P_r, j_i)}|$ is relatively large for each $i = 1,2,3$. Then if $1\leq l \leq c_3 n$, to construct a $C_{2l+1}$ in $G(A)$ first we pick a number $a\in A_{(P_r, j_1)}$ and then the remaining $2l$ numbers will be chosen alternately from $A_{(P_r, j_2)}$ and $A_{(P_r, j_3)}$. We will need the following lemma \begin{lemma}. For every $\sigma > 0$ and $\delta > 0$, there exists an $r_0 = r_0(\sigma, \delta)$ such that if $r\geq r_0, n\geq n_4(\sigma, \delta, r)$ and $u = 1, 2, \ldots , P_r$, then for all but $\sigma \frac{n}{P_r}$ integers $k$ satisfying \[ 1\leq k \leq n, \; \; k \equiv u \; \; (mod \; \; P_r ), \] we have \[ \alpha (k) = \prod_{ \begin{array}{c} p|k\\ p>r \end{array}} \left( 1 - \frac{1}{p} \right) > 1 - \delta. \] \end{lemma} This lemma can be found in \cite{ESS}. Now we prove Theorem 3. Let $r$ denote a positive integer for which $r \geq r_0(\frac{\epsilon}{8} , \frac{\epsilon}{8})$. We evidently have \[ \sum_{i=1}^{\frac{1}{6}P_r} \left( |A_{(P_r, 6i-1)}| + |A_{(P_r, 6i)}| + \ldots + |A_{(P_r, 6i+5)}| \right) = \] \[ = |A_{(6, 0)}| + |A_{(6, 1)}| + \ldots + |A_{(6, 4)}| + 2 |A_{(6, 5)}| = |A| + |A_{(6,5)}| > f(n,2) + s_2 > \frac{2}{3} n -2 + \frac{\epsilon}{2} n. \] Hence there exists an $i_0$ for which \begin{eqnarray}\label{i0} |A_{(P_r, 6i_0-1)}| + |A_{(P_r, 6i_0)}| + \ldots + |A_{(P_r, 6i_0+5)}| > \frac{\frac{2}{3}n + \frac{\epsilon}{2}n - 2} {\frac{P_r}{6}} = \frac{4 n}{P_r} + 3 \epsilon \frac{n}{P_r} - \frac{12}{P_r}. \end{eqnarray} Clearly for every $u$ \begin{eqnarray}\label{egyu} |A_{(P_r, u)}| < \frac{n}{P_r} + 1. \end{eqnarray} We claim that (\ref{i0}) and (\ref{egyu}) imply that there exist three integers $j_1, j_2$ and $j_3$ such that \begin{eqnarray}\label{jek} 6 i_0 - 1 \leq j_1 < j_2 < j_3 \leq 6 i_0 + 5, \; (j_1, j_2) = (j_1, j_3) = (j_2, j_3) = 1, \end{eqnarray} and \begin{eqnarray}\label{sok} |A_{(P_r, j_i)}| > \frac{\epsilon}{2} \frac{n}{P_r} \; \; \mbox{for all} \; \; i= 1, 2, 3. \end{eqnarray} Indeed, if $|A_{(P_r, 6i_0-1)}| \leq \frac{\epsilon}{2} \frac{n}{P_r} $, then \begin{eqnarray}\label{nagy} |A_{(P_r, 6i_0)}| + \ldots + |A_{(P_r, 6i_0+5)}| > \frac{4n}{P_r} + \frac{5\epsilon}{2} \frac{n}{P_r} - \frac{12}{P_r}. \end{eqnarray} But then (\ref{egyu}) and (\ref{nagy}) imply that there exist integers $u_1, \ldots , u_5$ such that \begin{eqnarray}\label{uk} 0\leq u_1 < \ldots < u_5 \leq 5, \end{eqnarray} and \[ |A_{(P_r, 6i_0+u_i)}| > \frac{\epsilon}{2} \frac{n}{P_r} \; \; \mbox{for all} \; \; i = 1, \ldots ,5, \] since otherwise \[ |A_{(P_r, 6i_0)}| + \ldots + |A_{(P_r, 6i_0+5)}| \leq 4 \left( \frac{n}{P_r} + 1\right) + 2 \frac{\epsilon}{2} \frac{n}{P_r} = 4 \frac{n}{P_r} + \epsilon \frac{n}{P_r} + 4 \] would hold in contradiction with (\ref{nagy}). From (\ref{uk}) it follows that the sequence $\{6i_0+u_1, \ldots , 6i_0+u_5\}$ contains a subsequence $\{j_1, j_2, j_3\}$ of 3 terms which are pairwise relatively prime, proving our claim in this case. The case when $|A_{(P_r, 6i_0+5)}| \leq \frac{\epsilon}{2} \frac{n}{P_r}$ is similar. Thus now we may assume that \[ |A_{(P_r, 6i_0-1)}| > \frac{\epsilon}{2} \frac{n}{P_r} \; \; \mbox{and} \; \; |A_{(P_r, 6i_0+5)}| > \frac{\epsilon}{2} \frac{n}{P_r}. \] In this case we choose $j_1 = 6 i_0 - 1$ and $j_3 = 6 i_0 + 5$. For $j_2$ we choose one from the integers $6i_0 + 1, 6i_0 + 2$ and $6 i_0 +3$ for which \[ |A_{(P_r, j_2)}| > \frac{\epsilon}{2} \frac{n}{P_r}. \] (there must be one such a $j_2$) and then (\ref{jek}) and (\ref{sok}) clearly hold. Thus the claim is proved, we have $j_1, j_2$ and $j_3$ satisfying (\ref{jek}) and (\ref{sok}). Let $a$ denote a positive integer for which \begin{eqnarray}\label{11} a\in A_{(P_r, j_1)}\; \; \mbox{and} \; \; \prod_{ \begin{array}{c} p|a\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) > 1 - \frac{\epsilon}{8}. \end{eqnarray} Lemma 2 and the choice of $r$ guarantee that such an $a$ exists. We are going to estimate from below the number of solutions of \begin{eqnarray}\label{12} (a, b_x) = 1, \; b_x\in A_{(P_r, j_2)}. \end{eqnarray} Assume that $p|(a, d)$ for some $d\equiv j_2 ( mod \; \; P_r)$. Since $(j_1, j_2) =1$ we clearly have $p>r$. Denote by $h(P_r, j, z)$ the number of those integers $d$ for which $d\leq n, d\equiv j (mod \; \; P_r)$ and $(z, d) =1$. It is not hard to see that \[ \left|h(P_r, j_2, a) - \frac{n}{P_r} \prod_{ \begin{array}{c} p|a\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) \right| \leq 2^{\omega(a)} < 2^{2 \frac{\log n}{\log \log n}}. \] From this and (\ref{11}) we get for large $n$ \[ h(P_r, j_2, a) > \frac{n}{P_r} \prod_{ \begin{array}{c} p|a\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) - 2^{2 \frac{\log n}{\log \log n}} > \] \begin{eqnarray}\label{13} > \left( 1 - \frac{\epsilon}{8} \right) \frac{n}{P_r} - 2^{2 \frac{\log n}{\log \log n}} > \left( 1 - \frac{\epsilon}{4} \right) \frac{n}{P_r}. \end{eqnarray} Denoting the number of solutions of (\ref{12}) by $X$, we have by (\ref{egyu}), (\ref{sok}) and (\ref{13}) \[ X \geq |A_{(P_r, j_2)}| - \sum_{ \begin{array}{c} d\leq n\\ d\equiv j_2 (mod \; P_r)\\ (a,d)>1 \end{array}} 1 =\] \[ = |A_{(P_r, j_2)}| - \left( \sum_{ \begin{array}{c} d\leq n\\ d\equiv j_2 (mod \;P_r)\\ \end{array}} 1 - h(P_r, j_2, a) \right) > \] \begin{eqnarray}\label{14} > \frac{\epsilon}{2}\frac{n}{P_r} - \left( \frac{n}{P_r} + 1\right) + \left( 1 - \frac{\epsilon}{4} \right) \frac{n}{P_r} = \frac{\epsilon}{4} \frac{n} {P_r} - 1 > \frac{\epsilon}{5} \frac{n}{P_r}. \end{eqnarray} Therefore using Lemma 2 and (\ref{14}), if $c_3$ is small enough, then we can choose integers $b_1, b_2, \ldots b_l$ satisfying \[ (a, b_i) = 1, b_i\in A_{(P_r, j_2)}, \] and \begin{eqnarray}\label{15} \prod_{ \begin{array}{c} p|b_i\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) > \left( 1 - \frac{\epsilon}{8} \right) \; \; \mbox{for all} \; \; 1\leq i \leq l. \end{eqnarray} Put $e_i = [ b_i, b_{i+1}]$ for all $1\leq i \leq l$ where $b_{l+1}$ is defined to be $a$. Let us denote the number of solutions of \[ (e_i, f_y) = 1, f_y \in A_{(P_r, j_3)} \] by $Y_i$. From (\ref{jek}), if $g \equiv j_3 (mod \; P_r)$ and $p| (e_i, g)$, then $p > r$. Again we have \[ \left|h(P_r, j_3, e_i) - \frac{n}{P_r} \prod_{ \begin{array}{c} p|e_i\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) \right| \leq 2^{\omega(e_i)} < 2^{2 \frac{\log (n^2)}{\log \log (n^2)}} < \] \[ < 2^{4 \frac{\log n}{\log \log n}} . \] We obtain from this and (\ref{15}) for large enough $n$ that \[ h(P_r, j_3, e_i) > \frac{n}{P_r} \prod_{ \begin{array}{c} p|e_i\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) - 2^{4 \frac{\log n}{\log \log n}} \geq \] \[ \geq \frac{n}{P_r} \prod_{ \begin{array}{c} p|b_i\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) \prod_{ \begin{array}{c} p|b_{i+1}\\ p>r \end{array} } \left( 1 - \frac{1}{p} \right) - 2^{4 \frac{\log n}{\log \log n}} > \] \begin{eqnarray}\label{16} > \left( 1 - \frac{\epsilon}{8} \right)^2 \frac{n}{P_r} - 2^{4 \frac{\log n} {\log \log n}} > \left( 1 - \frac{\epsilon}{4} \right) \frac{n}{P_r}. \end{eqnarray} (\ref{egyu}), (\ref{sok}) and (\ref{16}) yield that \[ Y_i \geq |A_{(P_r, j_3)}| - \left( \sum_{ \begin{array}{c} g\leq n\\ g\equiv j_3 (mod \;P_r)\\ \end{array}} 1 - h(P_r, j_3, e_i) \right) > \] \[ > \frac{\epsilon}{2}\frac{n}{P_r} - \left( \frac{n}{P_r} + 1\right) + \left( 1 - \frac{\epsilon}{4} \right) \frac{n}{P_r} = \frac{\epsilon}{4} \frac{n} {P_r} - 1 > \frac{\epsilon}{5} \frac{n}{P_r}. \] Hence we can choose an integer $h_i$ satisfying \[ (b_i, h_i) = (b_{i+1}, h_i) = 1 \; \; \mbox{and} \; \; h_i \in A_{(P_r, j_3)} \] for all $1\leq i \leq l$. Then \[ a, b_1, h_1, b_2, h_2, \ldots , b_l, h_l, a \] form a $C_{2l+1}$ in $G(A)$ and this completes the proof of Theorem 3. \begin{thebibliography}{99} \bibitem{AK} R. Ahlswede and L.H. Khachatrian, On extremal sets without coprimes, {\em Acta Arithmetica}, LXVI.1 (1994), 89-99. \bibitem{AK1} R. Ahlswede and L.H. Khachatrian, Maximal sets of numbers not containing $k+1$ pairwise coprime integers, {\em Acta Arithmetica}, to appear. \bibitem{AK2} R. Ahlswede and L.H. Khachatrian, Sets of integers and quasi-integers with pairwise common divisor, {\em Acta Arithmetica}, to appear. \bibitem{BD} M.J. Baines and D.E. Daykin, Coprime mappings between sets of consecutive integers, {\em Mathematika}, 10 (1963), 132-136. \bibitem{E1} P. Erd\H{o}s, Some remarks about additive and multiplicative functions, {\em Bull. Amer. Math. Soc.}, (1946), 527-537. \bibitem{E2} P. Erd\H{o}s, Remarks in number theory, IV (in Hungarian), {\em Mat. Lapok}, 13 (1962), 228-255. \bibitem{EFH} P. Erd\H{o}s, R. Freud and N. Hegyv\'{a}ri, Arithmetical properties of permutations of integers, {\em Acta Math. Acad. Sci. Hung.}, 41 (1983), 169-176. \bibitem{EP} P. Erd\H{o}s and C. Pomerance, Matching the natural numbers up to $n$ with distinct multiples in another interval, {\em Nederl. Akad. Wetensch. Proc. Ser. A}, 83 (1980), 147-161. \bibitem{ESS} P. Erd\H{o}s, A. S\'{a}rk\"{o}zy and E. Szemer\'{e}di, On some extremal properties of sequences of integers, I, {\em Ann. Univ. Sci. Budapest E\"{o}tv\"{o}s}, 12 (1969), 131-135, II., {\em Publ. Math. Debrecen}, 27 (1980), 117-125. \bibitem{GGL} R.L. Graham, M. Gr\"{o}tschel, L. Lov\'{a}sz (editors), Handbook of Combinatorics, MIT Press. \bibitem{NZM} I. Niven, H.S. Zuckerman, H.L. Montgomery, An introduction to the theory of numbers, 5th edition, John Wiley \& Sons, 1991. \bibitem{P} C. Pomerance, On the longest simple path in the divisor graph, {\em Congressus Numerantium}, 40 (1983), 291-304. \bibitem{PS} C. Pomerance and J.L. Selfridge, Proof of D.J. Newman's coprime mapping conjecture, {\em Mathematika}, 27 (1980), 69-83. \bibitem{S} E. Saias, Etude du graphe divisoriel, I, {\em Periodica Math. Hung.}, to appear. \bibitem{ST} C. Szab\'{o} and G. T\'{o}th, Maximal Sequences not containing 4 pairwise coprime integers (in Hungarian), {\em Mat. Lapok}, 32 (1985), 253-257. \end{thebibliography} \end{document}