Linear equivalence conjecture for hereditary and rooted quasirandomness

From papers

Let HH be a graph, let p[0,1]p\in[0,1], and let GG be a graph. The property PH,p(δ)\mathcal{P}_{H,p}^{*}(\delta) means that every UV(G)U\subseteq V(G) satisfies

c(H,G[U])=pe(H)Uv(H)±δv(G)v(H).c(H,G[U])=p^{e(H)}|U|^{v(H)}\pm\delta v(G)^{v(H)}.

Let RH,p(ε)\mathcal{R}_{H,p}(\varepsilon) denote the rooted quasirandomness condition defined in the paper, requiring the appropriate labelled-copy estimates for vertex subsets associated with the vertices of HH. Linear equivalence conjecture. For every graph HH, every p[0,1]p\in[0,1], and every δ>0\delta>0,

PH,p(δ)    RH,p(ε)\mathcal{P}_{H,p}^{*}(\delta)\implies\mathcal{R}_{H,p}(\varepsilon)

for some ε=OH,p(δ)\varepsilon=O_{H,p}(\delta). The paper states that this conjecture remains open and that, together with its main theorem, it would suffice to establish linear equivalence between PH,p(ε)\mathcal{P}_{H,p}^{*}(\varepsilon) and RH,p(ε)\mathcal{R}_{H,p}(\varepsilon).

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Xiaoyu He, “Linear dependence between hereditary quasirandomness conditions”, arXiv:1707.05396 (2018).

Solutions 0

No solutions have been posted yet.