\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath,amssymb,amsrefs} \usepackage{graphicx} \usepackage{tikz} %\usepackage[T1]{fontenc} %\usepackage[utf8]{inputenc} %\usepackage{fixltx2e} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %\usepackage{cite} %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Sept 26, 2016}{Apr 02, 2018}{TBD} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05C35} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{Independent sets in the union of two Hamiltonian cycles} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. %\author{Ron Aharoni} %\address{Department of Mathematics\\ Technion, Haifa, Israel} %\email[Ron Aharoni]{raharoni@gmail.com} %\thanks{\noindent The research of the first author was %supported by BSF grant no. $2006099$, by GIF grant no. I %$-879-124.6/2005$, by the Technion's research promotion fund, and by %the Discont Bank chair.} \author{Ron Aharoni \thanks{Supported by BSF grant no. $2006099$, by GIF grant no. I $-879-124.6/2005$, by the Technion's research promotion fund, and by the Discont Bank chair.}\\ \small Department of Mathematics\\[-0.8ex] \small Technion \\[-0.8ex] \small Haifa, Israel\\ \small\tt raharoni@gmail.com\\ \and Dániel Soltész \thanks{Supported by the National Research, Development and Innovation Office NKFIH, No. K-120706, No. K-108947 and No. KH-126853}\\ \small Alfréd Rényi Institute of Mathematica\\[-0.8ex] \small Hungarian Academy of Sciences \\[-0.8ex] \small Budapest, hungary\\ \small\tt solteszd@renyi.hu } \newtheorem{step}{Step} \begin{document} %\title{Independent sets in the union of two Hamiltonian cycles} % %\makeatother %\author{Ron Aharoni} %\address{Department of Mathematics\\ Technion, Haifa, Israel} %\email[Ron Aharoni]{raharoni@gmail.com} %\thanks{\noindent The research of the first author was %supported by BSF grant no. $2006099$, by GIF grant no. I %$-879-124.6/2005$, by the Technion's research promotion fund, and by %the Discont Bank chair.} % %\author{Daniel Soltész} %\address{Department of Computer Science and Information Theory \\ Budapest University of Technology and Economics} %\email[Daniel Soltész]{solteszd@math.bme.hu} %\thanks{\noindent The research of the second author was %supported by the Hungarian Foundation for Scientific Research Grant (OTKA) No. 108947} \begin{abstract} Motivated by a question on the maximal number of vertex disjoint Schrijver graphs in the Kneser graph, we investigate the following function, denoted by $f(n,k)$: the maximal number of Hamiltonian cycles on an $n$ element set, such that no two cycles share a common independent set of size more than $k$. We shall mainly be interested in the behavior of $f(n,k)$ when $k$ is a linear function of $n$, namely $k=cn$. We show a threshold phenomenon: there exists a constant $c_t$ such that for $c12$ vertices is the union of two Hamiltonian cycles and $\alpha(G)=n/4$, then $V(G)$ can be covered by vertex-disjoint $K_4$ subgraphs. % We also solve the problem exactly for $c=1/4$, and give a nice characterisation of the solutions. \end{abstract} %\keywords{ Independent set, Hamiltonian cycle, union, threshold.} \maketitle \section{Introduction} In this paper we study a ``pigeonhole'' phenomenon for Hamiltonian cycles - in a large enough set of such cycles there are necessarily two that are close, in the sense that their union contains a large independent set (meaning that they are similar to each other). The motivation comes from Schrijver subgraphs of the Kneser graph. The {\em Kneser graph} $KG[n,k]$ has as vertices the $k$-subsets of $[n]$, two vertices being connected if the sets are disjoint. A celebrated result of Lov\'asz \cite{lovasz} is that the chromatic number of $KG[n,k]$ is $n-2k+2$ when $k \leq n/2$. His proof used topology, and it gave birth to the field of topological combinatorics. Later Schrijver proved that a relatively small induced subgraph of $KG[n,k]$ already has the same chromatic number. The vertices of this subgraph are those $k$-sets that are independent on a given, fixed, Hamiltonian cycle on $[n]$. The question we are interested in is what is the largest size of a set of vertex disjoint Schrijver subgraphs of $KG[n,k]$. Two Schrijver subgraphs are vertex disjoint if their Hamiltonian cycles do not share an independent set of size $k$, meaning that the union of their Hamiltonian cycles has independence number less than $k$. So, the question is on the maximal number of Hamiltonian cycles with a given bound on the independence number of each pairwise union. Throughout the paper, unless otherwise stated the size of the vertex set of any graph mentioned is denoted by $n$. As usual, $\alpha(G)$ denotes the maximal size of an independent set in a graph $G$. If $G$ and $H$ are graphs on the same ground set $V$, we write $G \cup H$ for the graph on $V$ with $E(G) \cup E(H)$ as edge set. A {\em Hamiltonian cycle} on $V$ is a simple cycle containing all vertices of $V$. \begin{definition} $f(n,k)$ is the maximal size of a set $\mathcal{H}$ of Hamiltonian cycles on $n$ vertices, such that $\alpha(H_1 \cup H_2) \le k$ for every $H_1\neq H_2 \in \mathcal{H}$. \end{definition} Observe that the maximal number of pairwise vertex disjoint Schrijver subgraphs in the Kneser graph $KG[n,k+1]$ is exactly $f(n,k).$ We study $f(n,k)$ in the case where $k$ is a linear function of $n$, namely $k=cn$. This is very natural as the independence number of a Hamiltonian cycle grows roughly like a linear function of $n$. Our main observation is the following threshold phenomenon. \begin{theorem}\label{threshold} There is a constant $c_t$, such that for $c5$ then $f(n,cn)=1$, %since by Brooks theorem if $G$ is two-miltonian then $\alpha(G) \ge \frac{n}{4}$. We will soon see why are we excluding $K_5$. Besides the value of $c_t$, we are also interested in the first non-trivial values of the function $f$, namely $f(n,n/2-1)$ and $f(n,n/4)$. We will show by an easy argument that $f(n,n/2-1) \sim 2^n$, and by a surprisingly hard one that $f(n,n/4) = 2$ except for $n=4,8$, where $f(4,1)=f(8,2)=3$. Since a two-miltonian graph satisfies $\Delta \leq 4$, the following results will be useful for us: \begin{theorem} \label{7/26}[Locke, Lou] \cite{7/26} If $G$ is a connected $K_4$-free simple graph satisfying $\Delta(G) \le 4$, then $\alpha(G) \geq (7n-4)/26 \approx 0.2692n.$ % \quad (\sim 7n/26 > n/4).$ \end{theorem} Theorem~\ref{7/26} points towards the importance of $K_4$ subgraphs when $c$ is near $1/4$. We excluded $K_5$ from the definition of two-miltonian graphs because the structure of $K_4$s is different in $K_5$ than in other graphs that are the union of two Hamiltonian cycles. \begin{claim} \label{exception} In a two-miltonian graph $G$ every pair of $K_4$ subgraphs is vertex disjoint unless the graph is $K_5$ \end{claim} \begin{proof} Two $K_4$s can not share $1$ or $2$ vertices as the maximum degree in a two miltonian graph is at most $4$. Suppose that there are two $K_4$s, let $S$ be the subset of $V(G)$ covered by these two $K_4$s. Clearly $|S|=5$. Suppose that $|V(G)|>5$. Each of the two Hamiltonian cycles that form $G$ have at least two edges connecting $S$ to $V(G) \setminus S$. Therefore the sum of degrees of the induced subgraph of $G$ on the vertices of $S$ is at most $10-4=6$. But by our assumptions that $S$ contains two $K_4$s that intersect in three vertices this sum of degrees is $9$, a contradiction. It is not hard to see that the graph on $5$5 vertices that consists of two $K_4$s that share three vertices (which is actually $K_5$ minus an edge) is not two-miltonian. Therefore if such a subgraph is contained in a two-miltonian graph it must contain additional edges thus it must be $K_5$. \end{proof} \begin{definition} Given a two-miltonian graph $G$, we write $\zeta(G)$ for the number of copies of $K_4$s in $G$. If $\zeta(G)=n/4$ (namely if the vertices of $G$ can be covered by $K_4$s) then we say that $G$ is {\em $K_4$-covered}. \end{definition} The most useful tool used in this paper is the following rather technical lemma. %The proof that $f(n,n/4)\leq 2$ uses the following structural result, which might be of independent interest. \begin{lemma} \label{technical} Let $G$ be a two-miltonian graph on $n>13$ vertices. Let $G'$ be obtained from $G$ by removing all vertices in all copies of $K_4$. Then there exists a graph $H$ with $V(H)=V(G')$ and $E(G') \subseteq E(H)$, satisfying: \begin{enumerate} \item $H$ is connected. \label{connected} \item $H$ is $K_4$-free. \item $d_H(v) \leq d_G(v)$ for every vertex $v \in V(H)$, with strict inequality at least for one vertex $v$ if $G$ is not $K_4$-free. \item For every independent set $I$ of $H$ there exists a set $J$ consisting of a choice of one vertex from each $K_4$ in $G$, such that $I \cup J$ is independent in $G$. \label{strong} \end{enumerate} \end{lemma} Intuitively Lemma \ref{technical} states that if $G$ is two miltonian, we can use theorem \ref{7/26} on the $K_4$-free part of $G$ to obtain a large independent set and we can further enlarge it by adding a vertex from each $K_4$ maintaining independence. The authors feel that in Lemma \ref{technical} the assumption that $G$ is two-miltonian can be replaced by different assumptions, see Remark \ref{two-miltonian}. This Lemma is the core of the argument for the lower bound in Theorem \ref{bounds} and in the proof of the following theorem. \begin{theorem} \label{structural} Let $G$ be a two-miltonian graph on $n>12$ vertices. Then $\alpha(G) =\frac{n}{4}$ if and only if $G$ is $K_4$-covered. \end{theorem} Theorem \ref{structural} is sharp in the following sense: for $n=8,12$ there exist two-miltonian graphs with $\alpha=n/4$ and $\zeta=n/4-1$. For general, not necessarily two-miltonian but $\Delta(G) \leq 4$ graphs, the statement of Lemma \ref{technical} and Theorem \ref{structural} are false. There exist non two-miltonian graphs on arbitrarily large ground sets with $\alpha=n/4$ and $\zeta \le n/8$, see Figure \ref{counterexample}. \begin{figure}[htbp,scale=0.5] \begin{center} \begin{tikzpicture} %\tikzstyle{vertex}=[draw,circle,fill=black,minimum size=4,inner sep=0] \begin{scope}[shift={(0,0)}] \filldraw[black] (0,0) circle (2pt); %K4 \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,0) circle (2pt); \filldraw[black] (1,1) circle (2pt); \draw (0,0) -- (0,1); %K4 edges \draw (0,0) -- (1,0); \draw (0,0) -- (1,1); \draw (0,1) -- (1,0); \draw (0,1) -- (1,1); \draw (1,0) -- (1,1); \filldraw[black] (0,-1.5) circle (2pt); \filldraw[black] (1,-1.5) circle (2pt); \draw (0,0) to[out=200,in=150] (0,-1.5); \draw (0,1) to[out=200,in=150] (0,-1.5); \draw (1,0) to[out=-20,in=20] (1,-1.5); \draw (1,1) to[out=-20,in=20] (1,-1.5); \filldraw[black] (0,-2.5) circle (2pt); %lower K4 \filldraw[black] (1,-2.5) circle (2pt); \draw (0,-1.5) -- (0,-2.5); %lowerK4 edges \draw (0,-1.5) -- (1,-2.5); \draw (1,-1.5) -- (0,-2.5); \draw (1,-1.5) -- (1,-2.5); \draw (1,-2.5) -- (0,-2.5); \end{scope} \begin{scope}[shift={(3,0)}] \filldraw[black] (0,0) circle (2pt); %K4 \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,0) circle (2pt); \filldraw[black] (1,1) circle (2pt); \draw (0,0) -- (0,1); %K4 edges \draw (0,0) -- (1,0); \draw (0,0) -- (1,1); \draw (0,1) -- (1,0); \draw (0,1) -- (1,1); \draw (1,0) -- (1,1); \filldraw[black] (0,-1.5) circle (2pt); \filldraw[black] (1,-1.5) circle (2pt); \draw (0,0) to[out=200,in=150] (0,-1.5); \draw (0,1) to[out=200,in=150] (0,-1.5); \draw (1,0) to[out=-20,in=20] (1,-1.5); \draw (1,1) to[out=-20,in=20] (1,-1.5); \filldraw[black] (0,-2.5) circle (2pt); %lower K4 \filldraw[black] (1,-2.5) circle (2pt); \draw (0,-1.5) -- (0,-2.5); %lowerK4 edges \draw (0,-1.5) -- (1,-2.5); \draw (1,-1.5) -- (0,-2.5); \draw (1,-1.5) -- (1,-2.5); \draw (1,-2.5) -- (0,-2.5); \end{scope} \begin{scope}[shift={(6,0)}] \filldraw[black] (0,0) circle (2pt); %K4 \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,0) circle (2pt); \filldraw[black] (1,1) circle (2pt); \draw (0,0) -- (0,1); %K4 edges \draw (0,0) -- (1,0); \draw (0,0) -- (1,1); \draw (0,1) -- (1,0); \draw (0,1) -- (1,1); \draw (1,0) -- (1,1); \filldraw[black] (0,-1.5) circle (2pt); \filldraw[black] (1,-1.5) circle (2pt); \draw (0,0) to[out=200,in=150] (0,-1.5); \draw (0,1) to[out=200,in=150] (0,-1.5); \draw (1,0) to[out=-20,in=20] (1,-1.5); \draw (1,1) to[out=-20,in=20] (1,-1.5); \filldraw[black] (0,-2.5) circle (2pt); %lower K4 \filldraw[black] (1,-2.5) circle (2pt); \draw (0,-1.5) -- (0,-2.5); %lowerK4 edges \draw (0,-1.5) -- (1,-2.5); \draw (1,-1.5) -- (0,-2.5); \draw (1,-1.5) -- (1,-2.5); \draw (1,-2.5) -- (0,-2.5); \end{scope} \draw (-1,-2.6) to[out=0,in=200] (0,-2.5); \draw (1,-2.5) to[out=-20,in=200] (3,-2.5); \draw (4,-2.5) to[out=-20,in=200] (6,-2.5); \draw (7,-2.5) to[out=-20,in=180] (8,-2.6); \end{tikzpicture} \end{center} \caption{The strip closes on itself. This is a connected graph that is not the union of two Hamiltonian cycles and it has independence number $n/4$ while only half of its vertices can be covered by $K_4$s. } \label{counterexample} \end{figure} The paper is organized as follows. In Section \ref{sec:threshold} we prove the threshold phenomenon in the behavior of $f(n,cn)$, and using probabilistic arguments we prove upper bounds on the threshold value $c_t$. In Section \ref{sec:k4free} we prove Lemma \ref{technical}. In Section \ref{sec:nover4} we calculate $f(n,n/4)$ for all $n$. In Section \ref{sec:lowerbounds} we prove lower bounds on $c_t$. %Thus $c_t \in [1/4,1/2]$. An easy probabilistic reasoning gives that $c_t <1/2$, and obtaining the exact value of $f(n,n/2-1)$ for even $n$ is a one minute exercise. It is considerably harder to say anything near $1/4$. We will present an interesting construction that shows that $f(n,n/4) \geq 2$ if $n$ is divisible by four, (otherwise it is equal to $1$ by an easy argument). The construction is interesting, as it presents a clearly visible reason why the two Hamiltonian cycles cannot have the same independent set of size more than $n/4$: Their union is covered by vertex disjoint $k_4$'s. Later we will prove that in some sense this construction is optimal: $f(n,n/4)=2$ if $n > 12$ and divisible by four, and in this case it can only be achieved if the union of the two cycles is covered by disjoint $K_4$s. Supporting the viewpoint that these graphs would like to form a clicque, but two Hamiltonian cycles are too sparse to do this, the best that they can do is a $K_4$, so they are making as many $K_4$s as possible. %We will also present two proofs for the fact that $1/4 0$ and $n_0,k_0$ be integers and $c_0 \leq 1/2$ a constant. If $f(n_0, c_0n_0) \ge k_0$ then the function $f\left(n,\left(\frac{1}{k_0}\frac{1}{2}+\frac{k_0-1}{k_0}c_0+\frac{1}{2n_0} +\varepsilon \right)n \right)$ grows exponentially in $n$. \end{lemma} The proof will use a standard concentration result: \begin{lemma}\label{average} If the elements of two sequences $\sigma, \tau$ of length $N$ are chosen at random from a set of size $k$ then for every $a$, $$Pr \left( |\{a: \sigma(a) = \tau(a)\}| > \frac{N}{k}+\varepsilon N \right) < \exp(-2 \varepsilon N).$$ \end{lemma} \begin{proof} : See Theorem A.1.4. in \cite{alonspencer}. \end{proof} \begin{proof} [Proof of Lemma \ref{semi-random}] Let $S_1, \ldots ,S_N$ be disjoint copies of a set of size $n_0$, where $N$ is an even number to be specified below. Let $V=\bigcup_{i \le N}S_i$, and write $n=|V|=Nn_0$. Let $\mathcal{C}$ be the collection of $k_0$ cycles on $n_0$ vertices where each pairwise union has independence number at most $c_0n_0$. An {\em $N$-chain} is an $N$-tuple of cycles ${\mathcal{D}}=(C_{1}, \ldots ,C_{N})$, where $C_{a} \in \mathcal{C}$ is a Hamiltonian cycle chosen from $\mathcal{C}$ on $S_a$. Let $m=\frac{1}{k_0}\exp( \varepsilon N)=\frac{1}{k_0} \exp(\varepsilon n/n_0)$. Choose $m$ random $N$-chains $\mathcal{D}^1, \ldots ,\mathcal{D}^m$ as follows, for each $h \leq m$ let $\mathcal{D}^h$ consists of $N$ random cycles $C_i^h (i \leq N)$ chosen from $\mathcal{C}$ on $S_i$ uniformly and independently. % forming each $\D^h, ~h \le m$ by choosing a cycle %$C^h_i~~(i\le N)$ in each $\D^h$ at random from $\C$, %Writing $\D_j=(D_j^{i_1}, \ldots ,D_j^{i_k})$ (where each $D_j^{i_k}$ is some $C_i$) By Lemma \ref{average} the probability that among the $m$ chains there exists a pair $\mathcal{D}^j, \mathcal{D}^h$ for which $|\{i \mid C^j_{i}=C^h_{i}\}| > \frac{N}{k_0}+\varepsilon N $ is smaller than $\binom{m}{2} k_0 \exp(-2 \varepsilon N)$, which is less than $1$. Thus for every $N$ there exist $\frac{1}{k_0} \exp( \varepsilon N)$ $N$-chains $\mathcal{D}^j$, such that $|\{i \mid C^j_{i}=C^h_{i}\}| \le \frac{N}{k_0}+\varepsilon N $ whenever $j \neq h$ therefore %Writing $F_j=\bigcup \D_j$, we then have, for every pair $j, h \le m$: $$\alpha(\mathcal{D}^j \cup \mathcal{D}^h) \le (N/k_0+\varepsilon N)n_0/2 + (N(k_0-1)/k_0 - \varepsilon N)c_0n_0. $$ Here the first term comes from the cycles for indices $i$ for which $C^j_{i}=C^h_{i}$. The second term comes from the other cycles, applying the assumption of the theorem, that for $C_a, C_b \in \mathcal{C} $ , $\alpha(C_a \cup C_b) \le c_0n_0$. The next step is to turn each $\mathcal{D}^j$ into a Hamiltonian cycle. Pick a vertex $v_a$ in each copy $S_a$ of $S$, and for each $j$ delete an edge of $\mathcal{D}^j$ incident with $v_a$. This changes $\mathcal{D}_j$ into the union of $N$ paths, each having a vertex $v_a$ as one of its endpoints. Put a matching arbitrarily on the vertices $v_a$ (this is where we are using the fact that $N$ is even), thus making $\mathcal{D}^j$ to be the union $\mathcal{D}'^j$ of $N/2$ disjoint paths. Now form a Hamiltonian cycle $B_j$ by adding $N/2$ new edges, to $\mathcal{D}'^j$. Since the vertices $v_a$ are connected by a matching, for every pair $(j,h)$ of indices an independent set in $B_j \cup B_h$ contains at most $\frac{N}{2}$ vertices $v_a$, and hence $$\alpha(B_j \cup B_h)\le \sum_{a \le N}\alpha(C^j_{i_a} \cup C^h_{i_a})+\frac{N}{2}\le $$ $$(N/k_0+\varepsilon N)n_0/2 + (N(k_0-1)/k_0 - \varepsilon N)c_0n_0 + N/2 $$ yielding the independence ratio $$\frac{(N/k_0+\varepsilon N)n_0/2 + (N(k_0-1)/k_0 - \varepsilon N)c_0n_0 + N/2}{n}= $$ $$\left(\frac{1}{k_0}+\varepsilon \right) \frac{1}{2}+\left(\frac{k_0-1}{k_0}-\varepsilon \right)c_0+\frac{1}{2n_0}\leq \frac{1}{k_0}\frac{1}{2}+\frac{k_0-1}{k_0}c_0+\frac{1}{2n_0} +\varepsilon_2. $$ This proves the existence of exponentially large systems of Hamiltonian cycles with the appropriate size of independent sets in each union of two Hamiltonian cycles, for ground sets divisible by $2n_0$. The lemma for ground sets of general size follows directly. \end{proof} To deduce Theorem \ref{threshold} from Lemma~\ref{semi-random}, let us first re-formulate the theorem to an equivalent form: \begin{theorem} \label{sharp}(re-formulated)~~ If $\limsup_{n \rightarrow \infty} f(n,c_0n) = \infty$ then for every $\varepsilon >0$ there exists $\gamma=\gamma(\varepsilon) >1$ such that for large enough $n$ we have: $$ f(n,(c_0+\varepsilon)n) > \gamma^n. $$ \end{theorem} \begin{proof} Let $k_0 \geq \frac{3}{2\varepsilon}$ and we use $\frac{\varepsilon}{3}$ instead of $\varepsilon$. By the assumption there exists $n_0 \geq \frac{3}{2\varepsilon}$ for which $f(n_0,c_0n_0) \geq k_0$. For large enough $k_0$ we have $ \frac{1}{k_0}\frac{1}{2}+\frac{k_0-1}{k_0}c_0+\frac{1}{2n_0} +\frac{\varepsilon}{3} \leq c_0+\varepsilon $, and thus the theorem follows by Lemma \ref{semi-random}. \end{proof} Lemma \ref{semi-random} can be used to yield not only the existence of the threshold $c_t$, but also an upper bound. We prove the upper bound in theorem \ref{bounds}. \begin{claim} \label{bestupper} $c_t \leq 11/30 \approx 0.3666$ \end{claim} \begin{proof} Let $n$ be odd and divisible by $3$. Take as ground set the elements of $\mathbb{Z}_n$ (residue classes modulo $n$). We define the edge sets of two cycles and three forests on $n$ vertices as follows. $$E(C_1) := \{ (k,k+1) | k \in \mathbb{Z}_n\} \quad E(C_2):= \{(k,k+2) | k \in \mathbb{Z}_n \} $$ $$E(C'_{3}) := \{(3k,3k+2),(3k,3k+4) | k \in \mathbb{Z}_n\} $$ $$E(C'_{4}) := \{(3k+1,3k+3),(3k+1,3k+5) | k \in \mathbb{Z}_n\} $$ $$E(C'_{5}) := \{(3k+2,3k+4),(3k+2,3k+6) | k \in \mathbb{Z}_n\} $$ Connect the connected components of $C'_{3},C'_{4},C'_{5}$ to form Hamiltonian cycles $C_{3},C_{4},C_{5}$ arbitrarily. It is easy to verify that for $1 \leq i < j \leq 5$ the graph $C_i \cup C_j$ can be covered by vertex disjoint triangles, thus it has independence number at most $n/3$. Now we can use Lemma \ref{semi-random} with $k_0=5$, $c_0 = 1/3$ and $n_0$ odd and divisible by three, thus we get that for every $\varepsilon$ $$f\left(n,\left(\frac{1}{k_0}\frac{1}{2}+\frac{k_0-1}{k_0}c_0+\frac{1}{2n_0} +\varepsilon \right)n \right)=f\left(n,\left(\frac{11}{30}+\frac{1}{2n_0} +\varepsilon \right)n \right)$$ is exponentially large in $n$. Since we can choose $n_0$ to be arbitrarily large, we conclude that $c_t \leq 11/30$. \end{proof} \section{\texorpdfstring{$K_4$}-free graphs}\label{sec:k4free} A tool we shall use in two contexts is: \begin{theorem}\label{notevenmyfinalform}[Locke, Lou] \cite{7/26} Let $G$ be a connected $K_4$-free simple graph satisfying $\Delta(G) \leq 4$, if $e=|E(G)|$ then $$e-9n+26\alpha(G) \geq -4. $$ \end{theorem} \begin{remark} Theorem \ref{7/26} follows from Theorem \ref{notevenmyfinalform} and the observation that $\Delta(G) \le 4$ implies $e \le 2n$. Theorem \ref{notevenmyfinalform} is best possible in the sense that there are infinitely many graphs for which equality is attained. For a characterisation of these graphs, and a slight improvement on the constant $-4$ for other graphs, see \cite{7/26}. By contrast, it is not known whether Theorem \ref{7/26} is best possible for large $n$. \end{remark} Now we prove Lemma \ref{technical}. \begin{proof} In the proof below, $G$ will always denote a two-miltonian graph. \begin{definition} A connected $K_4$-covered induced subgraph of $G$ is called an {\em archipelago}. An archipelago is said to be {\em cyclic} if contains an induced cycle of length at least $4$, and otherwise it is called {\em acyclic}. The set of edges in an archipelago $K$ that do not lie in a $K_4$ is denoted by $M(K)$. \end{definition} Since $G$ is two-miltonian $\Delta(G)\le 4$, implying that the $K_4$s in $K$ are vertex disjoint, and that $M(K)$ is a matching, consisting of edges connecting $K_4$s. In an acyclic archipelago the $K_4$s are connected in a tree-like fashion. \begin{definition} The {\em neighborhood} $N(S)$ of a set $S$ of vertices is the set of vertices connected to $S$ and not belonging to $S$ itself. \end{definition} In other words, $N(S)$ is the {\em open} version of ``neighborhood''. Since every $K_4$ in $G$ sends out at least $4$ edges, we have: \begin{claim}\label{4edgesout} An acyclic archipelago sends at least four edges to its neighborhood. \end{claim} We shall remove the $K_4$s from $G$ one archipelago at a time. The next observation and claim explain why if the archipelago is cyclic we can plainly remove it, without having to worry about property (\ref{strong}) in Lemma \ref{technical}. \begin{observation} \label{greedy} Let $J$ be a connected graph with $\Delta(J) \le 4$, and let $I$ be a non-empty independent set in $J$. Then there is an independent set $I'$ of $J$ containing $I$, of size at least $|I|+ |V(J) \setminus N[I]|/4$. \end{observation} \begin{proof} If $N(I) =V(J)$, then taking $I'=I$ does the job. Otherwise, by the assumption of connectivity, there exists $v_1 \in V(J) \setminus N(I)$ connected to $N(I)$ by an edge. Let $I_1=I\cup \{v_1\}$. By the assumption that $\Delta(J) \le 4$ and by the fact that $v_1$ is connected to $N(I)$, we have $|N(I_1)|\le |N(I)|+4$. If $N(I_1)=V(J)$ then we can take $I'=I_1$. Otherwise we add to $I_1$ a vertex $v_2 \in V(J) \setminus N(I_1)$ that is connected to $N(I_1)$, and continue. \end{proof} \begin{claim} \label{k4cycles} If $K$ is a cyclic archipelago, then there exists an independent set $I \subseteq V(K)$ of size $|V(K)|/4$ (namely, $I$ contains one vertex from each $K_4$) such that $N(I) \subseteq V(K)$. \end{claim} \begin{proof} Let $M=M(K)$. Since $K$ is cyclic, there exists in $K$ an induced cycle $C$ of length at least $4$. The edges of $C$ alternate between $M$ and $E(K) \setminus M$, and hence $C$ is even. The set $I_0$ consisting of the odd vertices in $C$ is then independent, and $N(I_0) \subseteq V(K)$. %For every $u \in I_0$ let $K(u)$ be the vertex set of the $K_4$ containing $u$. Let $I$ be the independent set obtained by using Observation \ref{greedy} starting from $I_0$ in the graph induced by the vertices of $K$. Thus $|I| \ge |V(K)|/4$, and since $K$ is $K_4$-covered, in fact $|I|=|V(K)|/4$. %Note that if $v \in I_0$ is connected to a vertex $u$ then $u$ belongs to a $K_4$ participating in $C$, and thus $K(u) \subseteq N(I_0)$. Observe that every vertex added to $I$ in the algorithm of Observation \ref{greedy} has a neighbor among the previous vertices, which belong to $V(K)$, and three neighbors in its own $K_4$. Thus the newly vertex cannot have a neighbor outside $K$. \end{proof} The same argument yields: \begin{claim} \label{tooeasy} If $K$ is an archipelago then for each vertex $v \in V(K)$ having a neighbor in $V(G) \setminus V(K)$ there is an independent set $I \subseteq V(K)$ containing $v$, such that $|I|=|V(K)|/4$ and no vertex in $I \setminus \{v\}$ has a neighbor in $V(G) \setminus V(K)$. \end{claim} %\begin{proof} %Apply the algorithm in Observation \ref{greedy} to the graph $K$ with the initial independent set $v$. As in the proof of Claim %\ref{k4cycles}, when the algorithm of Observation \ref{greedy} adds a vertex, it has one of its neighbors in the neighborhood of %the previous vertices (Thus inside $V(K)$), and three other neighbors inside its own $K_4$. Thus a newly added vertex cannot have %a neighbor outside $K$. By Observation \ref{greedy}, $|I|=|K|/4$. %\end{proof} Claim \ref{tooeasy} is the main tool we shall use in the proof of the lemma, allowing us to take care of acyclic archipelagos $K$ that have non-independent neighborhoods. For such $K$ every independent set $J$ in our future $H$ omits a vertex in its neighborhood, and thus by Claim \ref{tooeasy} there exists an independent set $I_K \subseteq V(K)$ of size $|V(K)|/4$, such that $I_K \cup J$ is independent. Thus Claims \ref{k4cycles} and \ref{tooeasy} allow us to remove with no penalty all cyclic archipelagos and all archipelagos with non-independent neighborhoods, towards the removal of all $K_4$s. Thus, the problem is posed by acyclic archipelagos with independent neighborhood. Our strategy in this case is to add an edge inside this neighborhood, taking care not to generate a new $K_4$. \begin{remark}\label{constantneighborhood} The set $N(K)$ of vertices in the neighborhood of an archipelago $K$ remains the same throughout the process, since the edges we add are inside the neighborhood of a deleted archipelago, and as such they do not belong to $K$. Edges may be added inside $N(K)$, but as remarked this is in our favor. \end{remark} We shall remove the archipelagos in a special order, aimed to preserve useful properties of $G$. \begin{claim} If $K$ is an acyclic archipelago with an independent neighborhood of size $2$ and $\zeta(K)>1$ then $V(K)\cup N(K)=V(G)$. \end{claim} \begin{proof} Since $K$ is acyclic, $|M(K)| = \zeta(K)-1$. But there are exactly four edges leaving every $K_4$. Thus there are $4 \zeta(K)-2(\zeta(K)-1)=2\zeta(K)+2 \ge 6$ edges between $K$ and $N(K)$. Since $|N(K)|\le 2$ there is a vertex $v \in N(K)$ that receives $3$ edges from $K$, two of them being from the same Hamiltonian cycle $H_1$. Assume for contradiction that $V(K) \cup N(K)\neq V(G)$. Then deleting the other vertex of $N(K)$, if such exists, disconnects $V(K)\cup \{v\}$ from the rest of $V(G)$ in $H_1$ (remembering that there are no other vertices in $N(K)$). This contradicts the fact that $H_1$ is $2$-connected. \end{proof} By the claim, we may assume that every acyclic archipelago with an independent neighborhood of size two has only one $K_4$. We call such an archipelago {\em small} (see Figure \ref{first case1}). \begin{figure}[htbp,scale=0.5] \begin{center} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt); %K4 \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,0) circle (2pt); \filldraw[black] (1,1) circle (2pt); \draw (0,0) -- (0,1); %K4 edges \draw (0,0) -- (1,0); \draw (0,0) -- (1,1); \draw (0,1) -- (1,0); \draw (0,1) -- (1,1); \draw (1,0) -- (1,1); \filldraw[black] (0,-1.5) circle (2pt)node[anchor=south] {$A$}; \filldraw[black] (1,-1.5) circle (2pt)node[anchor=south] {$B$}; \draw (0,0) to[out=200,in=150] (0,-1.5); \draw (0,1) to[out=200,in=150] (0,-1.5); \draw (1,0) to[out=-20,in=20] (1,-1.5); \draw (1,1) to[out=-20,in=20] (1,-1.5); \end{tikzpicture} \caption{A small archipelago.} \label{first case1} \end{center} \end{figure} \begin{step}\label{smallnbd} Removing small archipelagos. \end{step}\label{removingn2} We delete all small archipelagos one by one, connecting their two neighbors at each step. Each such deletion+connecting is called below an {\em operation}. %\begin{claim} % This turned out to be not necessary, as the definition of small $K_4$ archipelagos changed. %We can assume that every small archipelago consists of a single $K_4$. %\end{claim} %\begin{proof} %A $K_4$-tree-archipelago where the number of $K_4$s is exactly $v$ sends exactly $2v+2$ edges to its neighborhood. Thus by the fact that the maximum degree is at most four, a small archipelago consists of at most three $K_4$s. Suppose that we have a small archipelago which consists of exactly three $K_4$s. Then the two vertices in the independent neighborhood have degree four, thus our graph consists of $14$ vertices, and by deleting the archipelago and connecting the two remaining vertices, the conditions of Lemma \ref{technical} are satisfied (it is a fun exercise to construct such a graph on $14$ vertices). Now suppose that we have a small archipelago which consists of exactly two $K_4$s. Then the vertices in the independent neighborhood send at least $6$ edges to the small archipelago, thus there are at most two edges connecting the subgraph consisting of the small archipelago and its neighborhood to the rest of the graph. Since the two independent vertices have degree four, this contradicts the fact that $G$ is a two-miltonian graph unless there are no more vertices, ie our graph consists of $10$ vertices. In this case we can also finish by saying that the conditions of Lemma \ref{technical} are satisfied if we delete the small archipelago and connect the vertices in its neighborhood. But one can also show easily that unlike the $14$ vertices case this case is not possible. %\end{proof} \begin{claim} No new $K_4$s are formed by this step. \end{claim} \begin{proof} Consider first the first operation. It could result in a new $K_4$ only if $G$ contains the graph in Figure \ref{first case2} as a subgraph. Since $n>13$, each of the two Hamiltonian cycles whose union is $G$ must reach this subgraph from the rest of the graph via $C$ or $D$, and leave it from the other vertex in this pair. Thus neither cycle can contain the edge $CD$, a contradiction. \begin{figure}[htbp,scale=0.5] \begin{center} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt); %K4 \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,0) circle (2pt); \filldraw[black] (1,1) circle (2pt); \draw (0,0) -- (0,1); %K4 edges \draw (0,0) -- (1,0); \draw (0,0) -- (1,1); \draw (0,1) -- (1,0); \draw (0,1) -- (1,1); \draw (1,0) -- (1,1); \filldraw[black] (0,-1.5) circle (2pt)node[anchor=south] {$A$}; \filldraw[black] (1,-1.5) circle (2pt)node[anchor=south] {$B$}; \draw (0,0) to[out=200,in=150] (0,-1.5); \draw (0,1) to[out=200,in=150] (0,-1.5); \draw (1,0) to[out=-20,in=20] (1,-1.5); \draw (1,1) to[out=-20,in=20] (1,-1.5); \filldraw[black] (0,-2.5) circle (2pt)node[anchor=north] {$C$}; %lower K4 \filldraw[black] (1,-2.5) circle (2pt)node[anchor=north] {$D$}; \draw (0,-1.5) -- (0,-2.5); %lowerK4 edges \draw (0,-1.5) -- (1,-2.5); \draw (1,-1.5) -- (0,-2.5); \draw (1,-1.5) -- (1,-2.5); \draw (1,-2.5) -- (0,-2.5); \end{tikzpicture} \caption{Impossible at the first replacement.} \label{first case2} \end{center} \end{figure} Suppose, for contradiction, that in the chain of operations a new $K_4$ is generated. As before, the graph obtained so far necessarily is as in Figure \ref{first case2}. Since such a subgraph cannot be present in $G$, some edges have to come from previous operations on small archipelagos. Observe that each such operaton reduces the degrees of the vertices of the newly added edge. Thus the only edge in Figure \ref{first case2} that could come from a previous deletion is the edge connecting $C$ to $D$. In this case, before that deletion our graph had to look like in figure \ref{first case3}. \begin{figure}[htbp,scale=0.5] \begin{center} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt); %K4 \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,0) circle (2pt); \filldraw[black] (1,1) circle (2pt); \draw (0,0) -- (0,1); %K4 edges \draw (0,0) -- (1,0); \draw (0,0) -- (1,1); \draw (0,1) -- (1,0); \draw (0,1) -- (1,1); \draw (1,0) -- (1,1); \filldraw[black] (0,-1.5) circle (2pt)node[anchor=south] {$A$}; \filldraw[black] (1,-1.5) circle (2pt)node[anchor=south] {$B$}; \draw (0,0) to[out=200,in=150] (0,-1.5); \draw (0,1) to[out=200,in=150] (0,-1.5); \draw (1,0) to[out=-20,in=20] (1,-1.5); \draw (1,1) to[out=-20,in=20] (1,-1.5); \filldraw[black] (0,-2.5) circle (2pt)node[anchor=north] {$C$}; %lower K4 \filldraw[black] (1,-2.5) circle (2pt)node[anchor=north] {$D$}; \draw (0,-1.5) -- (0,-2.5); %lowerK4 edges \draw (0,-1.5) -- (1,-2.5); \draw (1,-1.5) -- (0,-2.5); \draw (1,-1.5) -- (1,-2.5); \filldraw[black] (0,-4) circle (2pt); %K4 \filldraw[black] (1,-4) circle (2pt); \filldraw[black] (0,-5) circle (2pt); \filldraw[black] (1,-5) circle (2pt); \draw (0,-4) -- (1,-4); \draw (0,-4) -- (0,-5); \draw (0,-4) -- (1,-5); \draw (1,-4) -- (0,-5); \draw (1,-4) -- (1,-5); \draw (0,-5) -- (1,-5); \draw (0,-4) to[out=160,in=200] (0,-2.5); \draw (0,-5) to[out=160,in=200] (0,-2.5); \draw (1,-4) to[out=20,in=-20] (1,-2.5); \draw (1,-5) to[out=20,in=-20] (1,-2.5); \end{tikzpicture} \caption{Impossible, unless $n=12$.} \label{first case3} \end{center} \end{figure} But in this case every vertex has degree four, thus $G$ consists of just these $12$ vertices, contradicting our assumption that $n>13$. \end{proof} \begin{claim}\label{twmpreserved} Each operation results in a two-miltonian graph. \end{claim} \begin{proof} By induction on the number of operations. Assuming that after a deletion the resulting graph is the union of two Hamiltonian cycles $H_1$ and $H_2$, replace in each of $H_1, H_2$ the detour through the archipelago by the newly added edge. \end{proof} %The next operation is deleting all non-small archipelagos having %neighborhoods of size two and connecting the two vertices in the %neighborhood. These deletions cannot result in a new $K_4$, since if %the archipelago contains more than one $K_4$, it sends out at least %six edges to its neighborhood, thus after the deletion at most two %edges can leave its neighborhood. This cannot happen when the two %vertices are in a $K_4$. % (It is a fun exercise to construct a graph on $14$ vertices that has a small archipelago which consists of three $K_4$s.) This concludes Step \ref{smallnbd}. The resulting graph $G_1$ is two-miltonian by Claim \ref{twmpreserved}, and it contains no acyclic archipelagos with independent neighborhoods of size two. Note also that $G_1$ is a supergraph of $G'$, and hence it is enough to prove Lemma \ref{technical} with $G_1$ replacing $G$. \begin{step} \label{conn} Taking care of connectedness. \end{step} In this step we add edges, so as to make the graph $G_1$ connected. These edges will remain in the next steps, and so we shall not have to worry about connectedness from this point on. Let $H_1$ be one of the two Hamiltonian cycles forming $G_1$. Let $G_1'$ be the graph obtained from $G_1$ by removing all $K_4$s from it, and let $C_1, \ldots, C_m$ be the connected components of $G'_1$. Define an auxiliary graph $A$ on the vertex set $V(A):= \{C_1, \ldots, C_m\}$, two vertices $C_i$ and $C_j$ being connected if there is a path contained in $H_1$, whose one endpoint is in $C_i$ and the other in $C_j$ and all the other vertices lie in a single archipelago. Since $H_1$ is Hamiltonian, the graph $A$ is connected. Choose a spanning tree of $A$, and let $P_1, \ldots , P_{m-1}$ be subpaths of $H_1$ associated with each edge of the spanning tree. For each path $P_i$ going through an archipelago $K_i$ connect the endpoints of $P_i$ in the graph $G_1$, and delete all vertices of the archipelago $K_i$. The graph $G_2$ obtained this way is connected, it does not contain any new $K_4$s and $\Delta(G_2) \le 4$. \begin{remark}\label{decreasingdegree} If $G_1'$ was not connected then the degree of some vertices decreases. This is true since removing an archipelago reduces the total degree of the vertices adjacent to it by at least $4$, and the addition of an edge increases it only by $2$. \end{remark} The construction also yields: \begin{remark}\label{non2con} Edges added in this process do not belong to a cycle in $G_2$ \end{remark} %\begin{step} %Removing all cyclic archipelagos and all archipelagos with non independent neighborhoods. %\end{step} %By Claim \ref{k4cycles} for every cyclic archipelago and every independent set $J$ in our future $H$ there exists an independent set $I_K \subseteq V(K)$ of size $|V(K)|/4$, such that $I_K \cup J$ is independent. By Claim \ref{tooeasy}, this is also true for archipelagos $K$ with non-independent neighborhoods, since for such $K$ the independent set $J$ omits a neighbor of some $v \in V(K)$. %\begin{step}\label{largeneighborhoods} %Removing acyclic archipelagos with large neighborhoods. %\end{step} \begin{claim} \label{happy} Let $K$ be an acyclic archipelago in a graph of maximum degree at most four. Suppose that the neighborhood $N(K)$ is independent and has size $4$ or more. Then we can delete $K$ and connect two vertices in $N(K)$ by an edge, so that the new edge doesn't generate a new $K_4$. \end{claim} \begin{proof} Assuming negation, for every pair $p=\{x, y\}$ of vertices in $N(K) \setminus V(K)$ there exists a pair $q(p) = \{u,v\} \subseteq V(G)\setminus N(K)$ such that all pairs among $x,y,u,v$ apart from $xy$ are edges in $G$. We say that $q(p)$ is a {\em complementary pair} of $p$. Suppose first that there exist two pairs $p_1,p_2$ such that $q(p_1) \neq q(p_2)$. If $p_1 \cap p_2 =\emptyset$ let $p_3$ be a pair meeting both. Then $q(p_3) \neq q(p_i)$ for $i=1$ or $i=2$ (or both), proving that there exist non-disjoint pairs $p,p'$ with $q(p)\neq q(p')$. Let $v^*$ be the vertex in $p \cap p'$. If $q(p) \cap q(p')=\emptyset$ , then $v^*$ is connected to the four vertices in $q(p) \cup q(p')$, and since as a member of $I$ it is also connected to a vertex in $K$, its degree in $G$ is at least $5$, a contradiction. On the other hand, if there exists a vertex $v^{**} \in q(p) \cap q(p')$, then $v^{**}$ is connected to the five vertices in $q(p) \cup q(p') \cup p \cup p' \setminus \{v^{**}\}$, again a contradiction. \end{proof} \begin{remark} \label{weakened} The proof yields a stronger result: it suffices to assume that in the independent neighborhood of the acyclic archipelago not all pairs have the same complementary pair. \end{remark} \begin{step} \label{hard} Deleting acyclic archipelagos with independent neighborhoods of size $3$. %define, special-archipelagos that are $K_4$-tree-archipelagos have an independent neighborhood of size exactly $3$ ($A,B,C$), all connected to two vertices ($O_1,O_2$) that might or might not be connected, see Figure \ref{last case}. %In this step, we delete special-archipelagos. \end{step} Let $K$ be an acyclic archipelago such that $N(K)$ is independent and has size $3$, say $N(K)=\{A,B,C\}$. By Remark \ref{weakened} if no pair in $N(K)$ can be connected without generating a $K_4$, all pairs must have the same complementary pair, and thus $A,B,C$ are all connected to two vertices, $O_1$ and $O_2$. In such a case we call $K$ {\em forbidden} and the $5$-vertex subgraph showing this {\em forbidding for $K$}. \begin{figure}[htbp,scale=0.5] \begin{center} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt)node[anchor=east] {$A$}; %independent vertices \filldraw[black] (1,0) circle (2pt)node[anchor=east] {$B$}; \filldraw[black] (2,0) circle (2pt)node[anchor=east] {$C$}; \filldraw[black] (0.5,-1) circle (2pt)node[anchor=north] {$O_1$};%opponents \filldraw[black] (1.5,-1) circle (2pt)node[anchor=north] {$O_2$}; \draw (0,0) -- (-0.2,0.3); %A \draw (0,0) -- (0.2,0.3); %A \draw (1,0) -- (1,0.3); %B \draw (2,0) -- (2,0.3); %C \draw (0,0) -- (0.5,-1); %K4 edges \draw (0,0) -- (1.5,-1); \draw (1,0) -- (0.5,-1); \draw (1,0) -- (1.5,-1); \draw (2,0) -- (0.5,-1); \draw (2,0) -- (1.5,-1); \draw (0.5,-1) -- (1.5,-1); \node[](The forbidden graph.) at (1,-2){A forbidding subgraph}; \end{tikzpicture} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt)node[anchor=east] {$A'$}; %independent vertices \filldraw[black] (1,0) circle (2pt)node[anchor=east] {$B'$}; \filldraw[black] (2,0) circle (2pt)node[anchor=east] {$C'$}; \filldraw[black] (0.5,-1) circle (2pt)node[anchor=north] {$O'_1$};%opponents \filldraw[black] (1.5,-1) circle (2pt)node[anchor=north] {$O'_2$}; \draw (0,0) -- (-0.2,0.3); %A \draw (0,0) -- (0.2,0.3); %A \draw (1,0) -- (1,0.3); %B \draw (2,0) -- (2,0.3); %C \draw (0,0) -- (0.5,-1); %K4 edges \draw (0,0) -- (1.5,-1); \draw (1,0) -- (0.5,-1); \draw (1,0) -- (1.5,-1); \draw (2,0) -- (0.5,-1); \draw (2,0) -- (1.5,-1); \node[](Type $1$) at (1,-2){Type $1$}; \end{tikzpicture} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt)node[anchor=east] {$A'$}; %independent vertices \filldraw[black] (1,0) circle (2pt)node[anchor=east] {$B'$}; \filldraw[black] (2,0) circle (2pt)node[anchor=east] {$C'$}; \filldraw[black] (0.5,-1) circle (2pt)node[anchor=north] {$O'_1$};%opponents \filldraw[black] (1.5,-1) circle (2pt)node[anchor=north] {$O'_2$}; \draw (0,0) -- (-0.2,0.3); %A \draw (0,0) -- (0.2,0.3); %A \draw (1,0) -- (1,0.3); %B \draw (2,0) -- (2,0.3); %C \draw (0,0) -- (0.5,-1); %K4 edges \draw (0,0) -- (1.5,-1); %\draw (1,0) -- (0.5,-1); \draw (1,0) -- (1.5,-1); \draw (2,0) -- (0.5,-1); \draw (2,0) -- (1.5,-1); \draw (0.5,-1) -- (1.5,-1); \node[](Type $2$) at (1,-2){Type $2$}; \end{tikzpicture} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt)node[anchor=east] {$A'$}; %independent vertices \filldraw[black] (1,0) circle (2pt)node[anchor=east] {$B'$}; \filldraw[black] (2,0) circle (2pt)node[anchor=east] {$C'$}; \filldraw[black] (0.5,-1) circle (2pt)node[anchor=north] {$O'_1$};%opponents \filldraw[black] (1.5,-1) circle (2pt)node[anchor=north] {$O'_2$}; \draw (0,0) -- (-0.2,0.3); %A \draw (0,0) -- (0.2,0.3); %A \draw (1,0) -- (1,0.3); %B \draw (2,0) -- (2,0.3); %C %\draw (0,0) -- (0.5,-1); %K4 edges \draw (0,0) -- (1.5,-1); \draw (1,0) -- (0.5,-1); \draw (1,0) -- (1.5,-1); \draw (2,0) -- (0.5,-1); \draw (2,0) -- (1.5,-1); \draw (0.5,-1) -- (1.5,-1); \node[](Type $3$) at (1,-2){Type $3$}; \end{tikzpicture} \caption{The forbidden subgraph $K$ is invisible in the picture. The Type $1,2,3$ \textit{risking} subgraphs are the three graphs (up to isomorphism) that are one edge short to be forbidding.} \label{disgusting} \end{center} \end{figure} \begin{claim} $G_2$ does not contain a forbidden archipelago. \end{claim} \begin{proof} Suppose that $G_2$ contains a forbidden archipelago with forbidding subgraph $F$, with vertices denoted as in the figure. Since $A,B,C \in N(K)$, they do not belong to any archipelago $J$, or else $K$ and $J$, being connected, would be contained in the same archipelago. The same is true for $O_1,O_2$, since they are of degree $4$ in $F$. By Remark \ref{non2con} no edges in $F$ were added in Step \ref{conn}. Also, no edges inside $F$ was added in Step \ref{removingn2}, since the endpoints of any edge that is added in Step \ref{removingn2} have maximum degree three. Thus $F$ is also a subgraph of $G$. The archipelago $K$ consists of at most two $K_4$s, since otherwise the degrees of some of the $A,B,C$ would be larger than four. But then the subgraph consisting of the union of $K$ and the vertices $A,B,C,O_1,O_2$ has at most $13$ vertices, and it is connected to the rest of the graph by at most two edges. Since the endpoints of these two edges have degree $4$, this contradicts the fact that $G$ is two-miltonian on more than $13$ vertices. \end{proof} We next delete archipelagos one by one, taking care not to generate a forbidden archipelago. The risk is that connecting two neighbors of a deleted archipelago may create a forbidding subgraph for some other archipelago. Up to isomorphism, there are three subgraphs that are one edge short of the forbidding subgraph, see the graphs named Type $1,2,3$ in Figure \ref{disgusting} (a step that helps in realizing this is noting that in the forbidding subgraph the role of $O_1,O_2$ and $B,C$ is symmetric). We will say that an acyclic archipelago $K'$ is {\em risky} if it has an independent neighborhood consisting of three vertices that are connected, besides to vertices in $K'$, to vertices $O_1, O_2$, forming a graph $Y$ of one of these three types. We say that the subgraph $Y$ is {\em risking} for $K$. By Claim \ref{4edgesout} $K$ sends at least four edges to its neighborhood, and hence at least one of the vertices $A,B,C$ receives from $K$ two edges. As in the figure, we denote this vertex by $A$, and whenever ``$A$'' is used in this context we assume that it has degree at least $2$ to the risky archipelago. \begin{claim} \label{worst part} Let $K'$ be a risky archipelago contained in $G_2$, and denote the vertices in its risking subgraph as in Figure \ref{disgusting}. Then deleting $K'$ and connecting $A'$ to $B'$ does not generate a forbidding subgraph for some other archipelago. \end{claim} \begin{proof} Let $Y$ be the risking subgraph of $K'$. Suppose, by negation, that deleting $K'$ and adding the edge $e=A'B'$ generates a forbidden archipelago $K$. This was born from a risking graph $Z$ for $K$. Denote the vertices of $Z$ by $A,B,C,O_1,O_2$, as in the figure. Since at least two edges were removed from the star of $A'$ and only one edge was added, the degree of $A'$ strictly decreases by the operation. If $Z$ is of type $1$, then the edge added is between $O_1$ and $O_2$, both of which become of degree $4$, and thus the one that is identical to $A'$ had degree at least $5$ before the operation. This is impossible, since throughout the process degrees of vertices do not increase, and $\Delta(G) \le 4$. A similar argument applies if $Z$ is of type $3$, and the added edge is $AO_1$. Thus we may assume that $Z$ is of type $2$, and that $e=B'O_1'$, see Figure \ref{In the end}. Since the degree of $A'$ decreased, and after the addition of $e$ the vertex $O'_1$ has degree $4$, it is impossible that $A'=O'_1$. Hence $A'=B$ and $B'=O_1$, see Figure \ref{In the end}. If $Y$ is of Type $1$ or $2$, then $A'$ is connected to the two opponents which are not inside any archipelago. But $A'$ has already $3$ different neighbors in archipelagos (two from $Y$ and at least one from $Z$), implying that $A'$ has degree at least $5$ in $G$, a contradiction. Thus we may assume that $Y$ is of type $3$. \begin{figure}[htbp] %,scale=0.5 \begin{center} \begin{tikzpicture} \filldraw[black] (0,0) circle (2pt)node[anchor=east] {$A$}; %independent vertices \filldraw[black] (1,0) circle (2pt)node[anchor=east] {$B$}; \filldraw[black] (2,0) circle (2pt)node[anchor=east] {$C$}; \filldraw[black] (0.5,-1) circle (2pt)node[anchor=north] {$O_1$};%opponents \filldraw[black] (1.5,-1) circle (2pt)node[anchor=north] {$O_2$}; \draw (0,0) -- (-0.2,0.3); %A \draw (0,0) -- (0.2,0.3); %A \draw (1,0) -- (1,0.3); %B \draw (2,0) -- (2,0.3); %C \draw (0,0) -- (0.5,-1); %K4 edges \draw (0,0) -- (1.5,-1); \draw[dashed] (1,0) -- (0.5,-1); \draw (1,0) -- (1.5,-1); \draw (2,0) -- (0.5,-1); \draw (2,0) -- (1.5,-1); \draw (0.5,-1) -- (1.5,-1); %End of the \filldraw[black] (-0.5,-1) circle (2pt); \filldraw[black] (-1,-1) circle (2pt); \filldraw[black] (-0.5,-1.5) circle (2pt); \filldraw[black] (-1,-1.5) circle (2pt); \draw (-0.5,-1) -- (-1,-1);%K4 begins \draw (-0.5,-1) -- (-0.5,-1.5); \draw (-0.5,-1) -- (-1,-1.5); \draw (-1,-1) -- (-0.5,-1.5); \draw (-1,-1) -- (-1,-1.5); \draw (-0.5,-1.5) -- (-1,-1.5);%K4 ends \draw (-0.5,-1) -- (1,0); \draw (-1,-1) -- (1,0); \draw (-0.5,-1.5) -- (0.5,-1); \node[](A') at (0.75,0.70){$A'$}; %additional nodes \node[rotate=90](=1) at (0.75,0.35){$=$}; \node[](B') at (0.5,-1.95){$B'$}; \node[rotate=90](=2) at (0.5,-1.6){=}; \node[](O'_2) at (2.3,-1.35){$O'_2$}; \node[](=3) at (1.9,-1.35){=}; \end{tikzpicture} \caption{$C'$ can not be any vertex in this picture, and it must also be connected to $O'_2$, a contradiction.} \label{In the end} \end{center} \end{figure} Since in a Type $3$ subgraph, $A'$ is connected to $O'_2$, we conclude that $O_2=O'_2$ or else $A'$ would have degree $5$. Since $A',B',C'$ are independent, $C'$ must be a vertex different from $A,B,C,O_1,O_2$, and since in a Type $3$ subgraph $C'$ is connected to $O'_2$ which is equal to $O_2$, this means that $O_2$ has degree $5$, again a contradiction. \end{proof} By the claim it is possible to delete all risky acyclic archipelagos one by one, We now remove acyclic archipelagos with neighborhoods of size $3$, adding an edge at each stage, as follows. If at the current stage there are no risky acyclic archipelagos we delete any archipelago with independent neighborhood of size $3$ and connect two of its neighbors, without risking the generation of a $K_4$ (since there are no forbidden archipelagos), and without generating a forbidden archipelago (since there are no risky archipelagos). At stages in which there is a risky archipelago we use the claim to remove such an archipelago, while not generating a risky archipelago, and not generating a $K_4$ (the latter following from the non-existence of a forbidden archipelago). Let $G_3$ be the graph obtained after these operations. Then $G_3$ is connected, it does not contain any new $K_4$s, and $\Delta(G_3) \le 4$. %The graph $G_2$ is connected, it does not contain any new $K_4$s and it has maximum degree at most four. If $m>1$ then the degree of some vertices is decreased in the process by the following argument. The edges that we added in this step, can only compensate for the decrease of degree caused by losing an edge corresponding to $K$, but not for the other Hamiltonian cycle. Thus from now on we don't have to worry about the connectedness of the graph $H$. \begin{step} Removing all remaining archipelagos. \end{step} Since $G_3$ does not contain any acyclic archipelagos with independent neighborhoods of size two or three, by Lemma \ref{happy} we can delete every acyclic archipelago with an independent neighborhood one by one, and after each deletion we can connect some vertices in their neighborhood without creating a new $K_4$. After we deleted every acyclic archipelago with an independent neighborhood, we delete every other acyclic archipelago and every other cyclic archipelago without adding any additional edges. Let $H$ be the graph obtained from $G_3$ this way. We claim that $H$ satisfies the requirements of the lemma. Clearly, it is $K_4$-free, and Step \ref{conn} saw to it that it is connected. At each step of our construction degrees of vertices only went down. If in Steps $1$ or $3$ any archipelagos were deleted, the degree of some vertices strictly decreased, since only one edge is added, while at least $4$ edges were removed as the result of the removal of the archipelago. By Remark \ref{decreasingdegree} each deletion of archipelagos in Step $2$ also decreased the degree of at least one vertex. Condition \ref{strong} in the lemma follows from our construction and Claim \ref{k4cycles}. \end{proof} \begin{remark} \label{two-miltonian} The two-miltonian property of $G$ was used: \begin{itemize} \item For the property that $\Delta(G) \leq 4$ . \item For the property that the $K_4$s in $G$ are vertex disjoint. \item For the property that an acyclic archipelago sends a certain number of edges to its neighbourhood. This can be avoided since if it would send less, we could treat it as if it is a cyclic archipelago. \item In Step $1$ to forbid subgraphs like in figure \ref{first case2}. This is important since we have to forbid graphs like \ref{counterexample} as Lemma \ref{technical} can not be applied to such graphs. \item In Step 2 to guarantee connectedness. This could be avoided by paying attention to the connectedness of the $K_4$-free part at each deletion. (Although this would make the proof even more unpleasant to read.) \end{itemize} Thus the authors feel that results similar to Lemma \ref{technical} should hold with assumptions on $G$ that can replace the role of two-miltonicity at the above mentioned parts of the proof. \end{remark} \begin{corollary} \label{smooth} In a two-miltonian graph $G$ on $n$ vertices $$ \alpha(G) \geq \zeta(G) + \frac{7}{26}(n-4\zeta(G)) - O(1).$$ \end{corollary} \begin{proof} Let $H$ be the graph obtained from $G$ as in Lemma \ref{technical}. By Theorem \ref{7/26} $\alpha(H) \ge \frac{7}{26}|V(H)|-O(1)=\frac{7}{26}(n-4\zeta(G))-O(1)$, and by part (4) in the conclusion of the lemma $\alpha(G) \ge \alpha(H)+\zeta(G)$. \end{proof} \section{Calculating \texorpdfstring{$f(n,n/4)$}{}}\label{sec:nover4} We will use a theorem that was proved by Albertson, Bollob\'as and Tucker. We state it in a simplified form, tailored to our needs. For the more general version see \cite{abt}. \begin{theorem}[M. Albertson, B. Bollobás, S. Tucker] \label{stoneage} If $G$ is $K_4$-free, $\Delta (G) \leq 4$ and $G$ is not $4$-regular, then $\alpha(G)>\frac{n}{4}$. \end{theorem} The value of $f(n,n/4)$ can be determined for all $n$. \begin{theorem} \label{values} \hfill \begin{enumerate} \item If $4 \nmid n$ and $n \neq 5$ then $f(n,n/4)=1$. \item $f(4,1)=f(8,2)=3$. \item $f(4k,k)= 2$ for $k\geq3$. \end{enumerate} \end{theorem} \begin{proof} Part (1) follows from Brooks' theorem. The following figure shows that for every $k$ there exists a two-miltonian graph $G$ with $n=4k$ and $\alpha(G) = \zeta(G)=k$. This means that $f(4k,k) \ge 2$. \begin{figure}[htbp,scale=0.5] \begin{center} \begin{tikzpicture} %%%%%%%%%%%%%%%%%%%VERTICES \filldraw[black] (0,0) circle (2pt);%firstfour \filldraw[black] (1,0) circle (2pt); \filldraw[black] (0,1) circle (2pt); \filldraw[black] (1,1) circle (2pt); \filldraw[black] (2.5,0) circle (2pt);%secondfour \filldraw[black] (3.5,0) circle (2pt); \filldraw[black] (2.5,1) circle (2pt); \filldraw[black] (3.5,1) circle (2pt); \filldraw[black] (5,0) circle (2pt);%thirdfour \filldraw[black] (6,0) circle (2pt); \filldraw[black] (5,1) circle (2pt); \filldraw[black] (6,1) circle (2pt); %%%%%%%%%%%%%%%%%%%%%EDGES \draw[thin] (-0.5,-0.1) to[out=0,in=200] (0,0); \draw[ultra thick] (-0.5,1.1) to[out=0,in=160] (0,1); \draw[line width =2.5pt] (0,0) -- (0,1);%firstK4 \draw[line width =2.5pt] (0,0) -- (1,0); \draw[thin] (0,0) -- (1,1); \draw[thin] (0,1) -- (1,0); \draw[thin] (0,1) -- (1,1); \draw[line width =2.5pt] (1,0) -- (1,1);%firstK4end \draw[thin] (1,0) to[out=-20,in=200] (2.5,0); \draw[line width =2.5pt] (1,1) to[out=20,in=160] (2.5,1); \draw[line width =2.5pt] (2.5,0) -- (3.5,0);%secondK4 \draw[line width =2.5pt] (2.5,0) -- (2.5,1); \draw[thin] (2.5,0) -- (3.5,1); \draw[thin] (3.5,0) -- (2.5,1); \draw[line width =2.5pt] (3.5,0) -- (3.5,1); \draw[thin] (2.5,1) -- (3.5,1);%secondK4end \draw[thin] (3.5,0) to[out=-20,in=200] (5,0); \draw[line width =2.5pt] (3.5,1) to[out=20,in=160] (5,1); \draw[line width =2.5pt] (5,0) -- (6,0);%thirdK4 \draw[line width =2.5pt] (5,0) -- (5,1); \draw[thin] (5,0) -- (6,1); \draw[thin] (6,0) -- (5,1); \draw[line width =2.5pt] (6,0) -- (6,1); \draw[thin] (5,1) -- (6,1);%thirdK4end \draw[thin] (6,0) to[out=-20,in=180] (6.5,-0.1); \draw[line width =2.5pt] (6,1) to[out=20,in=180] (6.5,1.1); \end{tikzpicture} \caption{The two strips eventually close on themselves.} \label{covered} \end{center} \end{figure} Since there are only three distinct Hamiltonian cycles on $4$ vertices, the fact that $f(4,1)= 3$ is easy. Figure~\ref{3example} is an example of three Hamiltonian cycles on the same vertex set of size $8$, having each pairwise union $K_4$ -covered, thus $\alpha(C_i \cup C_j)=2$ for $1 \le i 0$ be fixed and $S=\{S_1, \ldots, S_m\}$ be a set system on a ground set of size $n$ with the following properties. \begin{itemize} \item $\forall i: $ $|S_i| \geq xn$ \item $\forall i\neq j: $ $(1-\varepsilon)x^2n \geq|S_i \cap S_j|$ \end{itemize} Then $m$ is bounded by a number independent of $n$: $$m \leq q(x,\varepsilon)= \frac{1-x(1-\varepsilon)}{x\varepsilon}.$$ \end{lemma} \begin{proof} Let $z=xm$. Let $\{X_1,X_2\}$ be an unordered pair of different sets from $S$, chosen uniformly from the $\binom{m}{2}$ possible pairs. Let us denote by $l_i$ the number of sets in $S$ which contain the element $i$. Now we have $$ \mathbb{E}(|X_1 \cap X_2|)= \sum_{i=1}^n\mathbb{P}(i \in X_1 \cap X_2)=\sum_{i=1}^n \frac{\binom{l_i}{2}}{\binom{m}{2}} $$ Since the average of the $l_i$ is at least $z$, and the function $\frac{x(x-1)}{2}$ is convex, by Jensen's inequality we have the following $$ \sum_{i=1}^n \frac{\binom{l_i}{2}}{\binom{m}{2}} \geq n \frac{\binom{z}{2}}{\binom{m}{2}}=n\frac{z(z-1)}{\frac{z}{x}\left(\frac{z}{x}-1\right)} =n \frac{z-1}{\frac{z}{x^2}-\frac{1}{x}}=nx^2 \frac{z-1}{z-x}. $$ Elementary calculation yields that the inequality $$\frac{z-1}{z-x}\leq (1-\varepsilon)$$ holds if and only if $ m=\frac{z}{x} \leq \frac{1-x(1-\varepsilon)}{x\varepsilon}$, finishing the proof. \end{proof} \begin{remark} If in Lemma \ref{johnson} we replace $(1-\varepsilon)x^2n$ by $(1+\varepsilon)x^2n$, we can construct set systems of exponential size by a uniform random construction. \end{remark} For $00$ let $$\delta(x,\varepsilon)= \left(q\left(\frac{x}{4},\varepsilon \right)+1\right)^{-1} =\left(\frac{4-x(1-\varepsilon)}{x\varepsilon}+1\right)^{-1}.$$ \begin{lemma} \label{iterating} For every $00$ there exists a number $\theta(x,\varepsilon)$ such that if $k > \theta(x,\varepsilon)$ and $X=\{C_1 , \ldots , C_{k}\}$ is a collection of Hamiltonian cycles satisfying $\frac{xn}{4} \leq \zeta(C_i \cup C_j)$ whenever $1 \leq i < j \leq k$ then there exists a subcollection $X_2 \subseteq X$ of size at least $|X|^{\delta(x,\varepsilon)}$, such that $\frac{(1-\varepsilon)x^2n}{16}\leq \psi(C_k \cup C_l)$ for every pair of cycles $C_k,C_l \in X_2$. \end{lemma} \begin{proof} Let $A$ be a graph whose vertex set is $X$, and two cycles $C_i$ and $C_j$ are connected by an edge if and only if $\frac{(1-\varepsilon)x^2n}{16} \leq \psi(C_i \cup C_j)$. Our aim is to show that $|X|^{\delta(x,\varepsilon)} \leq \omega(A)$ (the latter denoting the largest size of a clique in $A$). This will follow from Ramsey's theorem and an upper bound we shall obtain on $\alpha(A)$. \begin{claim}\label{smallalpha} $\alpha(A) \le q(\frac{x}{4},\varepsilon)+1=\frac{4-x(1-\varepsilon)}{x\varepsilon}+1$. \end{claim} \begin{proof} Suppose to the contrary that there exists an independent set $D_1,D_2, \ldots D_p$ in $A$, where $p=\lceil q(\frac{x}{4},\varepsilon)\rceil+2$. By relabeling the vertices, we can assume that $D_1$ is the cycle $(1,2,\ldots,n)$. For every $1< j \le p$ let $S_j$ be the set of those $1 \le i \le n$ for which $D_1 \cup D_j$ contains a $K_4$ on the vertices $i, i+1, i+2, i+3 (\bmod n)$. By the assumption of the lemma $\zeta(D_1 \cup D_j) \ge \frac{xn}{4}$, and hence $|S_j| \ge \frac{xn}{4} $ for all $j \le p$. Since the cycles $D_j$ are independent in $A$, $\psi(D_i\cup D_j) < \frac{(1-\varepsilon)x^2}{16}$ whenever $i \neq j$. By Observation \ref{psizeta} this implies that $|S_i \cap S_j| < \frac{(1-\varepsilon)x^2}{16}n$. \\ These combined yield a contradiction to Lemma \ref{johnson}. \end{proof} By a result of Ajtai, Komlos and Szemeredi \cite{aks}, for fixed $s$ and $t$ large enough we have the following bound on the Ramsey numbers: $$R(s,t) \leq c_s \frac{t^{s-1}}{\log(t)^{s-2}}, $$ implying $R(s+1,t) \leq t^s$ for fixed $s$ and large enough $t$. Thus for fixed $s$ and large enough $n$ if G is a graph on $n$ vertices with $\alpha(G)\leq s$ then $\omega(G)\geq n^{\frac{1}{s}}$. Applying this to the graph $A$, and using Claim \ref{smallalpha}, we obtain that $\omega(A) \geq |X|^{\left(q(\frac{x}{4},\varepsilon)+1\right)^{-1}}=|X|^{\delta(x, \varepsilon)}$ and the proof is complete. \end{proof} For a family $X$ of Hamiltonian cycles let $m(X)=\min_{C \neq D \in X}\frac{\zeta(C \cup D)}{n} \in [0,1]$. For the sake of readability, we will often write $m$ for $m(X)$. \begin{lemma} \label{step} Let $X$ be a set of Hamiltonian cycles, if $\frac{\psi(C\cup D)}{n} < (1-\varepsilon)\left( \frac{\zeta(C \cup D)}{n}\right)^2-\varepsilon$ for every pair $C\neq D$ of cycles in $X$ then there exists a subset $Y$ of $X$ of size at least $|X|^{\delta(4m, \varepsilon)}$ such that $$ m(Y)^2 > m(X)^2 +\frac{ \varepsilon}{(1-\varepsilon)}. $$ \end{lemma} \begin{proof} By Lemma \ref{quality_indep} and the fact that $d$ is positive $m>0$. Applying Lemma \ref{iterating} with $x=4m$, we obtain $Y \subseteq X$ of size at least $ |X|^{\delta(4m,\varepsilon )}$, such that every pair of cycles $C,D \in Y$ satisfies $\frac{\psi(C \cup D)}{n} \geq (1-\varepsilon)m^2$. Let $C,D \in Y$ be such that $\frac{\zeta(C\cup D)}{n}=m(Y)$. By the assumption of the lemma $$ (1-\varepsilon)m(Y)^2-\varepsilon = (1-\varepsilon)\left( \frac{\zeta(C\cup D)}{n}\right)^2-\varepsilon > \frac{\psi(C \cup D)}{n} \geq (1-\varepsilon)m^2, $$ which yields the desired result. \end{proof} \begin{corollary}\label{exists} If $X$ is a set of Hamiltonian cycles satisfying $$|X|^{\left( \delta(4m,\varepsilon)^{\frac{1-\varepsilon}{\varepsilon}}\right)} > \theta(m, \varepsilon)$$ then there exists a pair $C\neq D$ of cycles in $X$ such that $$\frac{\psi(C\cup D)}{n} \geq (1-\varepsilon)\left( \frac{\zeta(C \cup D)}{n}\right)^2-\varepsilon.$$ \end{corollary} \begin{proof} Assume negation. Applying Lemma \ref{step} repeatedly, we obtain then a sequence $X=X_1 \supseteq X_2 \supseteq \ldots \supseteq X_p$ of sets of Hamiltonian cycles, such that $m(X_{i+1})^2 \ge m(X_{i})^2 + \frac{\varepsilon}{(1-\varepsilon)}$ and $|X_{i+1}| \ge |X|^{\delta(4m(X_i), \varepsilon)}$ for all $i1$, which is impossible since by definition $m \in [0,1]$. \end{proof} We can now obtain our goal - a lower bound on the threshold constant $c_t$. Remember that $c_t$ is a real number such that for $cc_n$ this value is exponential in $n$. \begin{theorem} $c_t\ge\frac{45}{169} \approx 0.26627.$ \end{theorem} \begin{proof} Let $\varepsilon>0$ be fixed, and let $d$ be positive such that $c_t<\frac{7}{26}-d$. Let $n$ be large and $X$ be a large collection of Hamiltonian cycles on $n$ vertices such that for every pair $C\neq D$ of cycles in $X$ we have $\alpha(C \cup D)\leq (\frac{7}{26}-d)n$. Here ``large'' is dictated by Corollary \ref{exists} By Corollary \ref{exists} there exist cycles $C\neq D \in X$ for which $\frac{\psi(C\cup D)}{n} \geq (1-\varepsilon)\left( \frac{\zeta(C\cup D)}{n} \right)^2-\varepsilon$. By Lemma \ref{quality_indep} $$\left(\frac{7}{26}-d\right)n \geq \alpha(C \cup D) \geq \frac{7}{26}n- \frac{1}{13}\zeta(C \cup D)+\frac{1}{2}\psi(C \cup D) -O(1) $$ and thus $$-d \geq -\frac{1}{13}\frac{\zeta(C \cup D)}{n}+\frac{1}{2}\frac{\psi(C \cup D)}{n} -\frac{O(1)}{n}$$ $$-d \geq -\frac{1}{13}\frac{\zeta(C \cup D)}{n}+\frac{1}{2}((1+\varepsilon)\left(\frac{\zeta(C\cup D)}{n}\right)^2-\varepsilon) -O(1)$$ Since we can choose $n$ arbitrarily large and $\varepsilon$ arbitrarily small, it follows that $$-d \geq -\frac{1}{13}\frac{\zeta(C \cup D)}{n}+\frac{1}{2}\left(\frac{\zeta(C\cup D)}{n}\right)^2$$ by taking the minimum of the right hand side we get that $$d \leq \frac{1}{338} \approx 0.002958 $$ for every choice of $d$ where $\frac{7}{26}-d >c_t$, thus $c_t \geq \frac{7}{26}-\frac{1}{338}=\frac{45}{169} \approx 0.266272$ \end{proof} %\left(\frac{a_k^2}{8}-\varepsilon\right) \begin{bibdiv} \begin{biblist} \bib{abt}{article}{ title={The independence ratio and maximum degree of a graph}, author={M. Albertson}, author={B. Bollobás}, author={S. Tucker}, journal={Congressus Numerantium}, date={1976}, } \bib{alonspencer}{book}{ title={The probabilistic method - Fourth edition}, author={N. Alon}, author={J. H. Spencer}, date={2016}, publisher={Wiley}, address={Tel-Aviv}, } \bib{aks}{article}{ title={A note on Ramsey numbers}, author={M. Ajtai}, author={J. Komlós}, author={E. Szemerédi}, journal={J. Combin. Theory Ser. A}, volume={29}, pages={354-360}, date={1980}, } \bib{csoka}{article}{ title={Independent sets and cuts in large-girth regular graphs}, author={E. Csóka}, journal={\tt arXiv:1602.02747 [math.CO]}, date={2016}, } \bib{janson}{book}{ title={Random graphs}, author={S. Janson}, author={T. Luczak}, author={A. Rucinski}, date={2000}, publisher={Wiley}, address={New York}, } \bib{7/26}{article}{ title={Finding independent sets in $K_4$-free $4$-regular connected graphs}, author={S. C. Locke}, author={F. Lou}, journal={Journal of combinatorial theory, Series B}, volume={71}, pages={85-110}, date={1997}, } \bib{lovasz}{article}{ title={A note on Ramsey numbers}, author={L. Lovász}, journal={J. Combin. Theory Ser. A}, volume={25}, pages={319-324}, date={1978}, } \bib{schrijver}{article}{ title={Vertex-critical subgraphs of Kneser graphs}, author={A. Schrijver}, journal={Nieuw Arch. Wiskd.}, volume={26}, pages={ 454-461}, date={1978}, } \end{biblist} \end{bibdiv} \end{document} % %\begin{abstract} % The reconstruction conjecture states that the multiset of % vertex-deleted subgraphs of a graph determines the graph, provided % it has at least 3 vertices. This problem was independently introduced % by Stanis\l aw Ulam (1960) and Paul Kelly (1957). In this paper, % we prove the conjecture by elementary methods. % It is only necessary % to integrate the Lenkle potential of the Broglington manifold over % the quantum supervacillatory measure in order to reduce the set of % possible counterexamples to a small number (less than a trillion). % A simple computer program that implements Pipletti's classification % theorem for torsion-free Aramaic groups with simplectic socles can % then finish the remaining cases. %\end{abstract} % %\section{Introduction} % %The reconstruction conjecture states that the multiset of unlabeled %vertex-deleted subgraphs of a graph determines the graph, provided it %has at least three vertices. This problem was independently introduced %by Ulam~\cite{Ulam} and Kelly~\cite{Kelly}. The reconstruction %conjecture is widely studied %\cite{Bollobas,FGH,HHRT,KSU,Stockmeyer,WS} and is very interesting %because it is. See \cite{BH} for more about the %reconstruction conjecture. % %\begin{definition} % A graph is \emph{fabulous} if \emph{rest of definition here}. %\end{definition} % %\begin{theorem} % \label{Thm:FabGraphs} % All planar graphs are fabulous. %\end{theorem} % %\begin{proof} % Suppose on the contrary that some planar graph is not fabulous. % Then we have a contradiction. %\end{proof} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Broglington Manifolds} % %This section describes background information about Broglington %Manifolds. % %\begin{lemma} % \label{lem:Technical} % Broglington manifolds are abundant. %\end{lemma} % %\begin{proof} % A proof is given here. %\end{proof} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Proof of Theorem~\ref{Thm:FabGraphs}} % %In this section we complete the proof of Theorem~\ref{Thm:FabGraphs}. % %\begin{proof}[Proof of Theorem~\ref{Thm:FabGraphs}] %Let $G$ be a graph. We have % % The align environment for multi-line equations is defined in the amsmath package. % \begin{align} % |X| &= a+b+c \nonumber\\ % &= \alpha\beta\gamma. % \end{align} % This completes the proof of Theorem~\ref{Thm:FabGraphs}. %\end{proof} % %\begin{figure}[ht] % \centering % % Use \includegraphics to import figures; for example % % \includegraphics[scale=0.6]{filename} % \caption{Here is an informative figure.\label{fig:InformativeFigure}} %\end{figure} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\subsection*{Acknowledgements} % %Thanks to Professor Querty for suggesting the proof of %Lemma~\ref{lem:Technical}. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% You do not have to use the same format for your references, but %% include everything in this file. Don't use natbib please. %% If you use BibTeX to create a bibliography, copy the .bbl file into here. % %\begin{thebibliography}{99} % %\bibitem{Bollobas} B. Bollob{\'a}s. \newblock Almost every % graph has reconstruction number three. \newblock \emph{J. Graph Theory}, % 14(1):1--4, 1990. % %\bibitem{BH} J.~A. Bondy and R. Hemminger, %\newblock Graph reconstruction---a survey. %\emph{J. Graph Theory}, 1:227--268, 1977. \doi{10.1002/jgt.3190010306}. % %\bibitem{FGH} J.~Fisher, R.~L. Graham, and F.~Harary. \newblock A % simpler counterexample to the reconstruction conjecture for % denumerable graphs. \newblock \emph{J. Combinatorial Theory, Ser. B}, % 12:203--204, 1972. % %\bibitem{HHRT} E. Hemaspaandra, L.~A. Hemaspaandra, % S.~P. Radziszowski, and R. Tripathi. \newblock % Complexity results in graph reconstruction. \newblock \emph{Discrete % Appl. Math.}, 155(2):103--118, 2007. % %\bibitem{Kelly} P.~J. Kelly. \newblock A congruence theorem for % trees. \newblock \emph{Pacific J. Math.}, 7:961--968, 1957. % %\bibitem{KSU} M. Kiyomi, T. Saitoh, and R. Uehara. % \newblock Reconstruction of interval graphs. \newblock In % \emph{Computing and combinatorics}, volume 5609 of % \emph{Lecture Notes in Comput. Sci.}, pages 106--115. Springer, 2009. % %\bibitem{Stockmeyer} P.~K. Stockmeyer. \newblock The falsity of the % reconstruction conjecture for tournaments. \newblock \emph{J. Graph % Theory}, 1(1):19--25, 1977. % %\bibitem{Ulam} S.~M. Ulam. \newblock \newblock {A collection of % mathematical problems}. \newblock Interscience Tracts in Pure and % Applied Mathematics, no. 8. Interscience Publishers, New % York-London, 1960. % %\bibitem{WS} D.~B. West and H. Spinoza. % \newblock Reconstruction from $k$-decks for graphs with maximum degree~2. % \newblock \arxiv{1609.00284vi}, 2016. % %\end{thebibliography} % %\end{document}