Forcing quasirandomness with triangles

DOI10.1017/FMS.2019.7MaRDI QIDQ4632525zbMATH OpenOpenAlexFDO

Authors Christian Reiher, M. Schacht

Publication date 30 April 2019

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1711.04754

zbMATH Keywords

Sidorenko's conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study forcing pairs for quasirandom graphs. Chung, Graham, and Wilson initiated the study of families $ℱ$ of graphs with the property that if a large graph $G$ has approximately homomorphism density $p^{e(F)}$ for some fixed $pin(0,1]$ for every $FinmathcalF$, then $G$ is quasirandom with density $p$. Such families $mathcalF$ are said to be forcing. Several forcing families were found over the last three decades and characterising all bipartite graphs $F$ such that $(K_2,F)$ is a forcing pair is a well-known open problem in the area of quasirandom graphs, which is closely related to Sidorenko's conjecture. In fact, most of the known forcing families involve bipartite graphs only. We consider forcing pairs containing the triangle $K_3$. In particular, we show that if $(K_2,F)$ is a forcing pair, then so is $(K_3,F^{\prime })$, where $F^{\prime }$ is obtained from $F$ by replacing every edge of $F$ by a triangle (each of which introduces a new vertex). For the proof we first show that $(K_3,C{\text{'}}_4)$ is a forcing pair, which strengthens related results of Simonovits and S'os and of Conlon et al.

Recommendations

• Note on forcing pairs
• On the local approach to Sidorenko's conjecture
• No additional tournaments are quasirandom-forcing
• Lower bound on the size of a quasirandom forcing set of permutations
• Tournament quasirandomness from local counting

Cites work

• σ-algebras for quasirandom hypergraphs
• An approximate version of Sidorenko's conjecture
• Bipartite subgraphs and quasi-randomness
• Cyclotomy and difference families in elementary Abelian groups
• Eigenvalues and expanders
• Eigenvalues and linear quasirandom hypergraphs
• Explicit construction of linear sized tolerant networks
• Extremal results in sparse pseudorandom graphs
• Finite reflection groups and graph norms
• Forcing quasirandomness with triangles
• Graph norms and Sidorenko's conjecture
• Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs
• Hereditary Extended Properties, Quasi-Random Graphs and Induced Subgraphs
• Hereditary quasirandomness without regularity
• scientific article; zbMATH DE number 3885945 (Why is no real title available?)
• scientific article; zbMATH DE number 4216032 (Why is no real title available?)
• scientific article; zbMATH DE number 4027516 (Why is no real title available?)
• scientific article; zbMATH DE number 4099367 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1944144 (Why is no real title available?)
• scientific article; zbMATH DE number 747030 (Why is no real title available?)
• Hypergraphs, quasi-randomness, and conditions for regularity
• Large networks and graph limits
• Linear dependence between hereditary quasirandomness conditions
• More on quasi-random graphs, subgraph counts and graph limits
• Note on forcing pairs
• On universality of graphs with uniformly distributed edges
• Pseudo-random graphs
• Pseudo-random hypergraphs
• Quasi-random graphs
• Quasi-random hypergraphs
• Quasi-random hypergraphs revisited
• Quasi-random oriented graphs
• Quasi-Random Set Systems
• Quasi-random subsets of \(\mathbb{Z}_ n\)
• Quasi-random tournaments
• Quasi-randomness and the distribution of copies of a fixed graph
• Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
• Quasi-randomness of graph balanced cut properties
• Quasirandom Groups
• Quasirandom permutations
• Quasirandomness in hypergraphs
• Quasi‐random classes of hypergraphs
• Quick approximation to matrices and applications
• Regular pairs in sparse random graphs I
• Some advances on Sidorenko's conjecture
• Sparse quasi-random graphs
• Szemerédi's lemma for the analyst
• Szemerédi's partition and quasirandomness
• The number of submatrices of a given type in a Hadamard matrix and related results
• The quasi-randomness of hypergraph cut properties
• Two approaches to Sidorenko's conjecture
• Weak quasi-randomness for uniform hypergraphs

Cited in

(10)

• Note on forcing pairs
• Forcing quasirandomness with triangles
• Lower bound on the size of a quasirandom forcing set of permutations
• Quasirandomness in hypergraphs
• Embedding clique-factors in graphs with low -independence number
• Quasirandom-Forcing Orientations of Cycles
• A limit theorem for small cliques in inhomogeneous random graphs
• Unavoidable order-size pairs in hypergraphs -- positive forcing density
• More non-bipartite forcing pairs
• Forcing generalised quasirandom graphs efficiently

This page was built for publication: Forcing quasirandomness with triangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632525)