Person : more non-bipartite forcing pairs

2019 
We study pairs of graphs (H1, H2) such that every graph with the densities of H1 and H2 close to the densities ofH1andH2in a random graph is quasi random; such pairs (H1, H2) are called forcing. Non-bipartite forcing pairs were first discovered by Conlon, Han, Person and Schacht [Weak quasi-randomness for uniform hypergraphs, Random Structures Algorithms 40(2012), no. 1, 1–38]: they showed that (Kt, F) is forcing where F is the graph that arises from Kt by iteratively doubling its vertices and edges in a prescribed way t times. Reiher and Schacht [Forcing quasirandomness with triangles, Forum of Mathematics, Sigma. Vol.7, 2019] strengthened this result for t= 3 by proving that two doublings suffice and asked for the minimum number of doublings needed fort >3.We show that⌈(t+ 1)/2⌉doublings always suffice.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    0
    References
    1
    Citations
    NaN
    KQI
    []