{"id":"arxiv/2608.24520","url":"https://arxiv.org/abs/2608.24520","tags":["math.CO","cs.CC","cs.DM","cs.DS","math.PR"],"score":0,"title":"Homomorphic-core phase transition threshold in Erdős--Rényi random graphs","domain":"math.CO","source":"arxiv","authors":["Jiaheng Wang"],"reviews":0,"subject":"math.CO","summary":"It is shown in this manuscript that a random graph $G$ drawn from the Erdős--Rényi model $\\mathcal{G}(n,p)$ with \\[ p=p(n)\\leq 1/2, \\qquad \\lim_{n\\to+\\infty}(np-\\log n-\\log\\log n)=+\\infty, \\] is a homomorphic core, i.e., every homomorphism from $G$ to itself is an automorphism. This implies tight ETH-based lower bounds of the subgraph isomorphism problem for almost all $k$-vertex patterns with polynomial average degree.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-25","reactions":{}}