The self-avoiding-walk bunkbed question

Suppose G=(V,E)G=(V,E) is a finite, connected, simple graph. For x,yVx,y\in V, let S(x,y)\mathscr{S}(x,y) be the set of self-avoiding walks from xx to yy, and let S(ui,vj)\mathscr{S}(u_i,v_j) denote the corresponding set on G×K2G\times K_2. Self-avoiding-walk bunkbed question. Is it true that for all distinct u,vV(G)u,v\in V(G),

S(u0,v0)S(u0,v1)?\big|\mathscr{S}(u_0,v_0)\big|\leq \big|\mathscr{S}(u_0,v_1)\big|?

The question has a negative answer in general: the inequality fails for ladder graphs, although it holds for complete bunkbed graphs Kn×K2K_n\times K_2 for all n3n\geq 3 by the stated theorem. Therefore the proposed assertion is refuted.

Sources & referencesView supporting material

Primary source

Pengfei Tang, “Maximum flow and self-avoiding walk on bunkbed graphs”, arXiv:2502.06237 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.