科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-25· math.CO

Homomorphic-core phase transition threshold in Erdős--Rényi random graphs

Jiaheng Wang

原始摘要(英文原文)· Original abstract
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.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Homomorphic-core phase transition threshold in Erdős--Rényi random graphs — 科研速览 Science Skim