DIR Return Create A Forum - Home
---------------------------------------------------------
knight tours
HTML https://knighttours.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: general Hamiltonian cycles problem
*****************************************************
#Post#: 52--------------------------------------------------
50%-Hamiltonicity-threashold/phase-transition in balanced
regular random graphs
DIR By: gsgs
Date: June 9, 2026, 8:21 pm
---------------------------------------------------------
2025-12-12, chatgpt
Here is a short, clean, ASCII-safe summary of all the main
results
you and I developed or confirmed for Hamiltonicity thresholds in
random (2,3)-regular graphs, both undirected and directed.
Everything below fits in a few precise statements.
===============================================================
SUMMARY: UNDIRECTED (2,3)-REGULAR RANDOM GRAPHS
Model:
n vertices
fraction p have degree 2
fraction (1 - p) have degree 3
Key obstruction:
A degree-3 vertex with 3 neighbors of degree-2 forces a
contradiction:
it would need 3 edges in the Hamilton cycle - impossible.
If such a vertex exists - graph is not Hamiltonian.
Probability of obstruction:
q = pow( (2*p)/(3 - p), 3 );
lambda = (1 - p) * n * q;
Pr(obstruction) = 1 - exp( -lambda );
Threshold for Hamiltonicity:
Solve lambda = log(2) - 50% Hamiltonian.
For small p:
p_50(n) = pow( (27 * log(2)) / (8*n), 1.0/3.0 );
avg_degree_50(n) = 3 - p_50(n);
for large n :
p_50(n) = Theta(n^(-1/3));
avg_degree_50(n) = 3 - Theta(n^(-1/3));
Interpretation:
You must make p extremely small.
Almost all degree-2 vertices must disappear.
Threshold average degree - 3 from below.
===============================================================
SUMMARY: DIRECTED (2,2)-REGULAR RANDOM DIGRAPHS
Model:
n vertices
indegree = outdegree = 2 for all vertices
optionally add m random extra arcs, but enforce:
no loops
no 2-cycles (no u->v and v->u)
max indegree/outdegree = 3
Empirical Hamiltonicity without extra arcs:
P_Ham(n,m=0) decreases with n
n = 50 - ~0.39
n = 100 - ~0.29
n = 1000 - ~0.096
n = 5000 - ~0.045
Adding random arcs dramatically increases Hamiltonicity.
Observed 50% thresholds (m = number of extra arcs):
n= 50 - m_50 m= 1.5
n= 100 - m_50 m= 3.7
n= 1000 - m_50 m= 10.5
n= 2000 - m_50 m= 12.5
n= 5000 - m_50 m= 15.0
n=10000 - m_50 m= 16.7
These fit the formula:
m_50(n) = 2.9 * log(n) - 9.7 /* natural log */
m_50(n) = 6.7 * log10(n) - 9.7 /* base-10 log */
Corresponding average degree:
avg_degree_50(n) = 2 + m_50(n)/n;
As n increases:
avg_degree_50(n) = 2 + O( (log n)/n ) - 2.
Interpretation:
Bare 2,2-digraphs are often not Hamiltonian.
Adding only O(log n) random arcs almost always fixes all
bottlenecks.
This creates enough expansion to merge all cycle components.
Threshold is extremely close to average degree = 2.
===============================================================
COMPARISON: UNDIRECTED vs DIRECTED
UNDIRECTED (2,3)-regular:
Local obstruction (degree-3 vertex with 3 deg-2 neighbors)
dominates.
Hamiltonicity threshold tends to 3 from below.
Need p = O(n^(-1/3)) degree-2 vertices → almost 3-regular.
DIRECTED 2,2-regular:
No analogous local obstruction.
Obstruction is global (weak expansion, cycle cover not
mergeable).
Adding ~2.9 * log(n) arcs “heals” connectivity.
Hamiltonicity threshold tends to 2 from above.
So:
Undirected threshold: ~3 - Theta(n^(-1/3))
Directed threshold: ~2 + Theta(log(n)/n)
===============================================================
ALGORITHMIC OBSERVATIONS
After conversion to the 3n undirected gadget, Chalaturnyk's
solver
handles the instances extremely fast (even up to n = 10000).
Reason: many forced edges, low branching, good expansion.
Lack of Hamiltonicity for small m correlates with lack of
biconnectedness in the gadget graph.
Testing biconnectivity is an effective filter for
non-Hamiltonian cases.
===============================================================
*****************************************************
Page 1 of 1