How unproportional must a graph be?

DOI10.1016/J.EJC.2018.05.007zbMATH Open1393.05242arXiv1404.1206OpenAlexW2962916897MaRDI QIDQ1663804FDOQ1663804

Alex Scott, Oleg Pikhurko, Humberto Naves

Publication date: 24 August 2018

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

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$.

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)

Cites Work

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

Cited In (1)

• On a problem of Ahlswede and Katona

Recommendations

• How many ways can one draw a graph? 👍 👎
• How long can a graph be kept planar? 👍 👎
• When is a scale-free graph ultra-small? 👍 👎
• Are Crossings Important for Drawing Large Graphs? 👍 👎
• Graph Drawing 👍 👎
• Comparing Graphs of Different Sizes 👍 👎
• Brief Announcement 👍 👎
• How large is your graph? 👍 👎

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)