As my first math project, I have been working on Sheehan's Conjecture and am stuck for weeks. I wonder if I am at a dead end.
Sheehan's Conjecture states that every Hamiltonian 4-regular simple graph has at least two Hamiltonian cycles.
So far the best known results are from Thomassen's theorem. Let $G$ be a 2-edge-colouring graph in red and blue. A set $S$ of vertices of $G$ is called red-stable if no two vertices of $S$ are joined by a red edge, and blue-dominating if every vertex of $V\backslash S$ is adjacent by a blue edge to at least one vertex of $S$.
Let $G$ be a graph and $C$ be a Hamilton cycle of $G$. Colour the edges of $C$ red and the remaining edges of $G$ blue. Thomassen's theorem states that $G$ must have a second Hamilton cycle if there is a red-stable blue-dominating set $S$ in $G$.
Using Thomassen's theorem it has been proved that there is a non zero probability of red-stable blue-dominating set for any $k$-regular graphs ($k$$\geq$23).
I tried to directly calculate the probability of red-stable blue-dominating set for 4-regular graphs.
If the probability of red-stable sets, blue-dominating sets, and non red-stable non blue-dominating sets add up to be larger than 1, then Sheehan's Conjecture holds by Thomassen's theorem.
Clearly, if we delete all red edges from $G$, there will remain a 2-regular graph, which contains one or more disconnected blue loops, as shown in the figure bellow.
Suppose the Hamilton cycle $C$ has $n$ vertices, let $P(n)$ be the probability of red-stable sets in $C$.
For any Hamilton path $H$ in the Hamilton cycle $C$, let $P'(n)$ be the probability of red-stable sets in $H$.
Figure bellow is an example of a path, where each 1 represents a vertex in set $S$, and each 0 represents a vertex not in set $S$, so $S$ is red-stable.
$S$ would not be a red-stable set if the graph is not a path but a cycle, for both ends of the path will be joined by a red edge directly.
We have
$P(n)=\frac{1}{4}P'(n-2)+\frac{1}{4}P'(n-3)\ \ \ \ \ (1)$
$P'(n)=P(n)+\frac{1}{16}P'(n-4)\ \ \ \ \ (2)$
$P'(1)=1,P'(2)=\frac{3}{4},P'(3)=\frac{5}{8},P'(4)=\frac{1}{2}\ \ \ \ \ (3)$
For set $S$ to be red-stable on a cycle with $n$ vertices, there are three cases as illuminated in the figure bellow, where we draw the cycle as a line by taking any pair of adjacent vertices as the ends of the line. The choose of the end vertices are irrelevant.
The first case is such that both ends of the line are not in $S$. The probability of this case is $\frac{1}{4}P'(n-2)$, where $\frac{1}{4}$ is the probability of both ends being 0, and $P'(n-2)$ is the probability of $S$ being red-stable in the path consisting of the remaining $n-2$ vertices.
The second case is such that one end of the line is in $S$, but the other end is not. The probability of this case is $\frac{1}{8}P'(n-3)$, where $\frac{1}{8}$ is the probability of one end being 0 and the other end being 10, and $P'(n-3)$ is the probability of $S$ being red-stable in the path consisting of the remaining $n-3$ vertices. The third case is similar to the second case with a probability $\frac{1}{8}P'(n-3)$.
Therefore, the total probability is as equation (1).
For set $S$ to be red-stable on a path with $n$ vertices, there are four cases where three cases as illuminated in the figure above, and the fourth case is shown in the figure bellow.
The fourth case is such that both ends of the line are in $S$. The probability of this case is $\frac{1}{16}P'(n-4)$, where $\frac{1}{16}$ is the probability of one end being 01 and the other end being 10, and $P'(n-4)$ is the probability of $S$ being red-stable in the path consisting of the remaining $n-4$ vertices.
Therefore, the total probability is as equation (2).
Equation (3) contains the basic cases where $n$ is 1, 2, 3 or 4.
For blue-dominating sets, by similar methods, we have
$Q(n)=\frac{1}{4}Q'(n-2)+\frac{1}{4}Q'(n-3)+\frac{3}{16}Q'(n-4)\ \ \ \ \ (4)$
$Q'(n)=Q(n)+\frac{1}{16}Q'(n-5)+\frac{1}{64}Q'(n-6)\ \ \ \ \ (5)$
$Q'(1)=1,Q'(2)=1,Q'(3)=\frac{7}{8},Q'(4)=\frac{13}{16},Q'(5)=\frac{3}{4},Q'(6)=\frac{11}{16}\ \ \ \ \ (6)$
, $Q(n)$ is the probability of blue-dominating sets in $C$.
Equation (4) is the probability of blue-dominating set on one blue cycle. However, there may have more blue cycles in $G$. It seems difficult to have a systematical result of a comparison of probabilities of blue-dominating sets in a single-cycle graph and in a multiple-cycles graph with same amount of vertices.
Suppose $G$ contains a single blue cycle as shown on the left of the figure bellow. We split $G$ into $G'$ with two blue cycles at vertices $a$ and $b$, and $c$ and $d$, as shown on the right of the figure bellow. Suppose the two parts have $n_{1}$ and $n_{2}$ vertices respectively.
Whether or not $Q(n_{1})Q(n_{2})-Q(n)>0$ is variable by $n_{1}$ and $n_{2}$. I have checked for three cases: (a) $n_{1}=6\ n_{2}=6$; (b) $n_{1}=6\ n_{2}=7$; (c) $n_{1}=7\ n_{2}=7$.
For (a), $Q(n_{1})Q(n_{2})-Q(n)=\frac{11}{2048}$; for (b), $Q(n_{1})Q(n_{2})-Q(n)=\frac{3}{2048}$; for (c), $Q(n_{1})Q(n_{2})-Q(n)=-\frac{15}{8192}$.
We can directly calculate the number of blue-dominating sets by an inclusion-exclusion argument and the star and bar method. The result is:
$\sum_{1\leq m\leq n}(\sum_{1\leq l\leq j,m_{1}+\ldots+m_{j}=m,m_{i}\geq\lceil\frac{n_{l}}{3}\rceil}(\prod_{1\leq l\leq j}(\frac{n_{l}}{m_{l}}\cdot\sum_{i\geq0}(-1)^{i}\tbinom{m_{l}}{i}\tbinom{n-1-3i}{m_{l}-1}))).$
The next step is to calculate the probability of non red-stable non blue-dominating sets, which seems a difficult task. I have tried for weeks with no luck so far.
