How unproportional must a graph be?

DOI10.1016/J.EJC.2018.05.007MaRDI QIDQ1663804zbMATHOpenAlexFDO

Authors Humberto Naves, Oleg Pikhurko, Alex Scott

Publication date 24 August 2018

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

binomial random graph

Mathematics Subject Classification ID

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

Abstract: Let $u_k(G,p)$ be the maximum over all $k$-vertex graphs $F$ of by how much the number of induced copies of $F$ in $G$ differs from its expectation in the binomial random graph with the same number of vertices as $G$ and with edge probability $p$. This may be viewed as a measure of how close $G$ is to being $p$-quasirandom. For a positive integer $n$ and $0<p<1$, let $D(n,p)$ be the distance from $$ to the nearest integer. Our main result is that, for fixed $kge4$ and for $n$ large, the minimum of $u_k(G,p)$ over $n$-vertex graphs has order of magnitude $$ provided that $p(1-p)n^{1/2}oinfty$.

Recommendations

• How large is your graph?
• How long can a graph be kept planar?
• Are crossings important for drawing large graphs?
• Brief announcement: How large is your graph?
• How many ways can one draw a graph?
• Graph Drawing
• When is a scale-free graph ultra-small?
• Comparing graphs of different sizes

Cites work

• scientific article; zbMATH DE number 3186884 (Why is no real title available?)
• σ-algebras for quasirandom hypergraphs
• A central limit theorem for decomposable random variables with applications to random graphs
• A functional limit theorem for random graphs with applications to subgraph count statistics
• A graph Fourier transform and proportional graphs
• Cutting a graph into two dissimilar halves
• Discrepancy in graphs and hypergraphs
• Existence of proportional graphs
• Graph norms and Sidorenko's conjecture
• Imbalances in k‐colorations
• Intersections of graphs
• Intersections of hypergraphs
• Large networks and graph limits
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Probabilistic construction of proportional graphs
• Proportional graphs
• Quasi-random graphs
• Random graphs.
• The asymptotic distributions of generalized U-statistics with applications to random graphs
• The poset of hypergraph quasirandomness
• The probabilistic method
• Weak quasi-randomness for uniform hypergraphs

Cited in

(1)

• On a problem of Ahlswede and Katona

This page was built for publication: How unproportional must a graph be?

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