We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that $\delta_{\mathrm{hom}}(\{C_3,C_5\},\{C_3\})=\frac{1}{9}$. Equivalently, for every $\varepsilon>0$, every $n$-vertex graph of odd girth at least $7$ and minimum degree at least $(1/9+\varepsilon...
Romain Bourneuf, Raphael Steiner, Stéphan Thomassé et al.· 0 citations
We determine the critical probability for Bernoulli bond percolation on essentially any finite graph. Namely, letting $\lambda(G)$ denote the spectral radius (maximum eigenvalue) of $G$, we prove that the critical probability is at $1/\lambda(G)$: above this probability there is typically a component of order $\Omega(\...
Many important results in extremal graph theory can be roughly summarized as “if a triangle‐free graph G$$ G $$ has certain properties, then it has a homomorphism to a triangle‐free graph Γ$$ \Gamma $$ of bounded size.” For example, bounds on homomorphism thresholds give such a statement if G$$ G $$ has sufficiently hi...
Lior Gishboliner, Eoin Hurley, Yuval Wigderson· Random Structures & Algo...· 2 citations· ⚡2
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
