{"id":"arxiv/2602.00278","url":"https://arxiv.org/abs/2602.00278","tags":["math.CO"],"score":0,"title":"Thresholds vs. expectation thresholds for non-spanning graphs","domain":"math.CO","source":"arxiv","authors":["Quentin Dubroff"],"reviews":0,"subject":"math.CO","summary":"The threshold $p_c(H)$ for the event that the binomial random graph $G_{n,p}$ contains a copy of a graph $H$ is the unique $p$ for which $\\mathbb{P}(H \\subseteq G_{n,p}) = 1/2$, and the fractional expectation threshold $q_f(H)$ is roughly the best lower bound on $p_c(H)$ using simple expectation considerations. All previously known $H$'s with $p_c(H)$ substantially larger than $q_f(H)$ have the property that $v_H > n/2$ (where $v_H$ is the number of vertices of $H$). We construct small graphs whose threshold for containment in $G_{n,p}$ is of different order than their corresponding…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-30","reactions":{}}