Li–Szegedy Smooth-Retract Conjecture

Definitions and mathematical statement

For a graph $G$, write $V(G)$ and $E(G)$ for its vertex and edge sets. A graph is bipartite if its vertex set admits a partition into two classes such that every edge joins different classes. An induced subtree $T$ of $H$ is a connected, acyclic induced subgraph of $H$: two vertices of $T$ are adjacent in $T$ exactly when they are adjacent in $H$.

A graph homomorphism $r:H\to T$ is a map $r:V(H)\to V(T)$ preserving adjacency. It is a retraction onto $T$ if \[ r(v)=v\qquad\text{for every }v\in V(T). \] Thus $H$ retracts onto $T$ precisely when such a homomorphism exists.

The supplied record attributes the following conjecture to Li and Szegedy: for every bipartite graph $H$ and every induced subtree $T$ of $H$, \[ \left(\exists\,r:H\to T\text{ a graph homomorphism with }r|_{V(T)}=\mathrm{id}_{V(T)}\right) \ \Longrightarrow\ T\text{ is smooth in }H\text{ in the sense of Li and Szegedy}. \] The supplied record does not define Li--Szegedy smoothness. The conclusion therefore retains the source terminology and is not a self-contained mathematical predicate in this draft. Its exact definition, including any analytic data and quantifiers, must be recovered from the cited sources before a complete formal statement can be given. The record also leaves the graph conventions, including finiteness and whether graphs are simple, unspecified; no additional restrictions are imposed here.

Short English statement

The supplied Li--Szegedy conjecture says that every induced subtree of a bipartite graph onto which the graph retracts is smooth in that graph. The meaning of smoothness and the intended graph conventions require source verification. The supplied open status is dated curation, not an independently verified conclusion.

Sources

• Local UnsolvedMath registry, supplied complete source record for permanent ID $30002314$, title "Li--Szegedy Smooth-Retract Conjecture," exact source problem code catalogue entry. The conjecture is attributed in the record to Li and Szegedy; no separate proposer is supplied. The proposed year is recorded as 2013.
• Supplied report citation: Arbeitsgemeinschaft: Limits of Structures (2014), Oberwolfach Reports, DOI 10.4171/owr/2013/16, pp. 963--1024. https://doi.org/10.4171/owr/2013/16. The literature-source list labels this reference "Oberwolfach Report 16/2013." The discrepancy between the supplied title year 2014 and the report designation 2013 remains unresolved.
• Supplied literature reference: arXiv:1107.1153. https://arxiv.org/abs/1107.1153. No title, author list, or passage defining smoothness is included in the record.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that special cases of the converse are known while the checked primary literature still presents the general statement as a conjecture. This is supplied dated curation derived from the OWR material, not independently verified here. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and supplies a verification note claiming comparison with the official Oberwolfach report and restoration of its hypotheses and notation. These are supplied provenance claims, not verification performed for this draft.