Understanding the finale of the proof of Komlós’ and Szemerédi’s limit distribution of Hamiltonian random graphs

My question is about the end of the proof of Theorem 1 in (Komlós, Szemerédi (1983)), more precisely the arguments in Subsection 2.3. Let me state the beautiful theorem I am trying to understand in my own words:

Theorem 1. With the vertex set ${1, 2, dots, n}$ and edges drawn independently with probability
$$frac{frac{1}{2}nln(n) + frac{1}{2}nln(ln(n) + nc_n}{binom{n}{2}}$$
for a real sequence $(c_n)$ converging to $cinmathbb{R}cup{-infty, infty}$ the probability of the event that the graph has a Hamiltonian cycle converges to the limit distribution $e^{-e^{-c}}$ (extended continuously to $0$ and $infty$ for $c=mpinfty$, respectively) for $ntoinfty$.

The limit distribution is the one for graphs with minimal degree $2$, so this necessary condition for being Hamiltonian is almost sufficient. In the proof a series of additional graph theoretical conditions is defined, which force the graph to be Hamiltonian and all of whose probabilities converge to one.

My question is about the arguments at the end of the proof in Subsection 2.3. I have understood the beginning of the subsection where the existence of many paths of maximal length which contain certain fixed sections $M_1$ and $M_2$ of vertices is shown. But then the existence of a series of sets of new endpoints $K_p^isubset M_1$ of growing sizes is shown. I don’t even understand the construction of the first set $K_p^1$ which “can be seen easily” using the logical opposite of condition $D_3$. Which sets $S_1$ and $S_2$ is condition $neg D_3$ applied to? I suspect that $neg D_3$ is applied several times to different choices of $S_1$ and $S_2$ in order to get a disjoint union $bigcup_{pin L_1} K_p^1$. Or, are these sets automatically disjoint for some other reason? The choices of the sets $K^2_p$ and so on become even more mysterious to me. How is $neg D_4$ used, and which set $S$ is it applied to?

After that I am fine again: the same thing is done from the other end with $M_2$, and finally the cycle is obtained leading to a contradiction.

Thank you for reading that far. Some help or some hints would be appreciated very much.

graphs – Algorithm to not pass through forbidden edges in a complete hamiltonian digraph

I have a complete directed graph with ${n}$ nodes and ${n(n-1)}$ edges. A completed digraph can contain ${(n-1)!}$ hamiltonian cycles. The problem states that there is a particular hamiltonian cycle (A forbidden hamiltonian cycle) wherein the edges are “forbidden”. More specifically, there are ${n}$ forbidden edges and ${n(n − 2)}$ edges that are not forbidden.

What kind of randomized algorithm can I devise that goes through only ${n-1}$ non-forbidden edges? If the algorithm goes through a forbidden edge, the program must terminate.

Here is an algorithm that I referenced from How to not find a Hamiltonian Cycle:

Choose an arbitrary vertex and mark it as vertex 1
Choose an arbitrary unmarked neighbor of vertex 1, move to it, and mark it as vertex 2
Repeat step (2) while the current iteration i < n and vertex i has unmarked neighbors
If vertex n is adjacent to vertex 1, move to vertex 1 and terminate

Can this algorithm be applied to my case? If not, what changes should I make?

Some of the similar questions are:



What do HC and HL (hamiltonian graph problems) stand for?

Hopefully, this question is fine.

I’m referring to the NP-complete problems regarding hamiltonian graphs.

  • I suppose the C in HC is from Cycle or Circuit. It seems like Circuit is more popular.
  • HL (called HAMPATH sometimes) is a bit more difficult. HL deals with hamiltonian paths (HP is already in use, of course). My best guess is that since path graphs are also called linear graphs, the L may stand for Linear. Another possibility is Line.

differential equations – How to put the following J_C Hamiltonian in the matrix form

I am trying to get the Matrix form of the following Hamiltonian for a finite dimension of $hat a$
$$H = wc{hat a^dagger}hat a + wa{{{{hat sigma }_z}} over 2} + g({hat sigma _ – }{hat a^dagger} + hat a{hat sigma _ + }),$$
where ${hat a^dagger}, hat a$ are the creation and annihilation operators, ${hat sigma +}, {hat sigma _ – }$ are rising and lowring operators.

I used the following Mathematica code but I am not sure:

σx = PauliMatrix(1); σy = PauliMatrix(2);    σz =
  PauliMatrix(3);     σI = IdentityMatrix(2);
σp = 1/2 (σx + I*σy);

dim = 2;

Idim(dim_) := IdentityMatrix(dim, SparseArray);

a(dim_) := 
  SparseArray({Band({1, 2}) -> Sqrt(Range(dim - 1))}, {dim, dim}))
adag(dim_) := ConjugateTranspose(a(dim))
nhat(dim_) := ConjugateTranspose(a(dim)).a(dim);

sigmap(dim_) := KroneckerProduct(σp, Idim(dim))
sigman(dim_) := ConjugateTranspose(sigmap(dim))

HHc = ωc nhat(dim);
HHa = 1/2 ωa sigmap(dim).sigman(dim);
HHac = g (adag(dim).sigman(dim) + a(dim).sigmap(dim));

HJC = HHa + HHc + HHac;

Given graph G and vertices v and w can you non-deterministically walk the “least Hamiltonian path” from v to w, if it exists?

My understanding of non-deterministic algorithms is that they’re “as lucky as you want”.

…you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices v and w, if there’s a vw path, then you can non-deterministically walk a vw path, luckily correctly guessing the vertices to walk in a vw path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I’m not sure.

Therefore, my first question is: if you can non-deterministically walk a vw path, can you non-deterministically walk a Hamiltonian path from v to w, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I’m calling a “least Hamiltonian path.” I would think so, but I’m not sure.

Define the least Hamiltonian path from v to w to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider K5 the graph with vertices {1,2,3,4,5} and all possible edges, then the least Hamiltonian path for (v,w) = (2,3) is 21453. If you were at vertex 2, the next least vertex would be 1. Then, the next least vertex would 4. etc.

Therefore, my actual question is: Given graph G and vertices v and w can you non-deterministically walk the least Hamiltonian path from v to w, if it exists?

Motivation: If so, then perhaps there’s a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices v and w, and go through each pair of vertices such that v<w, checking for the existence of a least Hamiltonian path. To ensure all vertices in G are reached, keep a counter for the number of vertices walked (this should equal N if there are N vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from v to w will be unique, therefore it can be walked multiple times (each time you walk through it, starting at v, you’ll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated – one for the vertex you’re checking to see if it’s unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).

differential equations – time dependent hamiltonian with random numbers

I have a Hamiltonian (Z) in matrix form, I solved it for time independent random real numbers, now want to introduce time dependent in such a way at any time the random real numbers change between the range {-Sqrt(3sigma2), Sqrt(3sigma2)}, here is my code

Nmax = 100; (*Number of sites*)

tini = 0; (*initial time*)

tmax = 200; (*maximal time*)

(Sigma)2 = 0.1; (*Variance*)

n0 = 50; (*initial condition*)

ra = 1; (*coupling range*)

(Psi)ini = Table(KroneckerDelta(n0 - i), {i, 1, Nmax});

RR = RandomReal({-Sqrt(3*(Sigma)2), Sqrt(3*(Sigma)2)}, Nmax);

Z = Table(
    Sum(KroneckerDelta(i - j + k), {k, 1, ra}) + 
     Sum(KroneckerDelta(i - j - k), {k, 1, ra}), {i, 1, Nmax}, {j, 1, 
     Nmax}) + DiagonalMatrix(RR);

usol = NDSolveValue({I D((Psi)(t), t) == 
     Z.(Psi)(t), (Psi)(0) == (Psi)ini}, (Psi), {t, tini, tmax});

What can I do for introduce this time dependent and solve the differential equation(usol)? I hope my question is clear

symplectic topology – Higher genus (Hamiltonian perturbed) holomorphic curves in cotangent bundle of S^1

Consider $T^*S^1$ as symplectic manifold, with hamiltonian function $H(x,y) = y^2$ (y is the fiber direction, I know this is morse bott but it can be perturbed). consider the set of maps $u: Sigma rightarrow T^*S^1$ satisfying floer’s equation:
$(du+X_Hotimes dt)^{0,1} =0$ (with approrpiate modifications for when $Sigma$ is a punctured riemann surface with higher genus). Is this set of maps understood? asked differently, is there an invariant (floer homology theory, gromov witten etc etc) defined by counting these maps that has been computed?
(I know symplectic homology of $T^*S^1$ has been computed and is shown to be isomorphic to string topology of $S^1$ (with corresponding product/coproduct structures, but that’s in genus 0), but what about these potentially “higher genus” invariants?

Command for finding maximum weight Hamiltonian path between two vertices

A Hamiltonian path is a graph path between two vertices of a graph that visits each vertex exactly once.
Finding a single Hamiltonian path of a graph $g$ is implemented in the Wolfram Language as FindHamiltonianPath[$g$]Hamiltonian path.

What command could be used to find the Hamiltonian path with maximum path weight between the starting vertex $s$ and the terminating vertex $t$ in the following edge labeled graph?

enter image description here