pith. sign in

arxiv: 1806.06609 · v2 · pith:ATBISSRDnew · submitted 2018-06-18 · 🧮 math.CO

A generalized Tur\'an problem in random graphs

classification 🧮 math.CO
keywords randomcasegraphscopiesgeneralizationgivenmathrmproblem
0
0 comments X p. Extension
pith:ATBISSRD Add to your LaTeX paper What is a Pith Number?
\usepackage{pith}
\pithnumber{ATBISSRD}

Prints a linked pith:ATBISSRD badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original abstract

We study the following generalization of the Tur\'an problem in sparse random graphs. Given graphs $T$ and $H$, let $\mathrm{ex}\big(G(n,p), T, H\big)$ be the random variable that counts the largest number of copies of $T$ in a subgraph of $G(n,p)$ that does not contain $H$. We study the threshold phenomena arising in the evolution of the typical value of this random variable, for every $H$ and an arbitrary $2$-balanced $T$. Our results in the case when $m_2(H) > m_2(T)$ are a natural generalization of the Erd\H{o}s--Stone theorem for $G(n,p)$, which was proved several years ago by Conlon and Gowers and by Schacht; the case $T = K_m$ has been recently resolved by Alon, Kostochka, and Shikhelman. More interestingly, the case when $m_2(H) \le m_2(T)$ exhibits a more complex and subtle behavior. Namely, the location(s) of the (possibly multiple) threshold(s) are determined by densities of various coverings of $H$ with copies of $T$ and the typical value(s) of $\mathrm{ex}\big(G(n,p), T, H\big)$ are given by solutions to deterministic hypergraph Tur\'an-type problems that we are unable to solve in full generality.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.