3
$\begingroup$

We say that $G\sim G_{n,f}$ (for $f=f(n)$) if $G$ is chosen uniformly at random from all graphs on $n$ vertices with girth $g(G)\ge f(n)$. Is there any threshold function $F(n)$ such that when $f\ll F$ then $G_{n,f}$ is with high probability Hamiltonian, and when $f\gg F$ then $G_{n,f}$ is with high probability non-Hamiltonian?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

It's possible (perhaps even likely) that the threshold is $f(n)=3$. Certainly a typical graph is Hamiltonian (girth $3$). But a typical girth $\ge 4$ graph is just a typical triangle-free graph, which Kleitman and Rothschild showed is asymptotically almost surely bipartite. A typical bipartite graph is not Hamiltonian, since the part sizes are likely to be slightly unbalanced.

For the model $G_{n,f}$ with $f\ge 5$ constant I don't know of any further results. I would be fairly confident that a typical girth $6$ graph is not Hamiltonian: we know (Keevash-Sudakov-Verstra\"ete) that the corresponding extremal problem has an essentially bipartite extremal example, we conjecture that the answer really is bipartite, and it's then reasonable to believe a typical example will also be bipartite and will likely have unbalanced parts. For girth $5$ I would be less confident (Brown showed the corresponding extremal example cannot be bipartite) but would believe that the answer is that these graphs are typically not Hamiltonian, and that this pattern continues.

For $f(n)\ge n/2$ it's trivial that typical graphs are not Hamiltonian (there are many fewer Hamilton cycles than trees) and it seems likely that if $f$ is reasonably large one can prove that $G_{n,f}$ is typically not Hamiltonian --- perhaps even for $f\ge\log n$.

It might be more interesting to ask this question replacing girth with even girth (i.e.\ forbidding only even cycles); call that model $E_{n,f}$. Then I think the answer would be that any constant $f$ gives $E_{n,f}$ typically Hamiltonian, and for sufficiently fast growing $f$ it is easy to show that typical graphs are not Hamiltonian. I would guess (with not much support!) that there would then be a threshold and it would be $\Theta(\log n)$.

These are very nice questions, but they are probably extremely difficult. The best constructions we know of graphs with large constant girth and many edges are algebraic, and hence all kinds of things that one would think should not matter turn out to affect what we can prove (like whether the number of vertices is a prime power). I would quite seriously expect the Riemann Hypothesis to be resolved before your question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.