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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-25 Page: https://delphi.science/r/arxiv/2608.24520 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.