The Library
How unproportional must a graph be?
Tools
Naves, Humberto, Pikhurko, Oleg and Scott, Alex (2018) How unproportional must a graph be? European Journal of Combinatorics, 73 . pp. 138-152. doi:10.1016/j.ejc.2018.05.007 ISSN 0195-6698.
|
PDF
WRAP-how-unproportional-must-graph-be-Pikhurko-2018.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (683Kb) | Preview |
Official URL: https://doi.org/10.1016/j.ejc.2018.05.007
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 p (n 2) to the nearest integer. Our main result is that, for fixed k ≥ 4 and for n large, the minimum of u k ( G,p ) over n -vertex graphs has order of magnitude Θ (max {D (n,p) ,p (1 − p) } n k – 2) provided that p (1 − p) n 1 / 2 →∞
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Graph theory | |||||||||
Journal or Publication Title: | European Journal of Combinatorics | |||||||||
Publisher: | Academic Press | |||||||||
ISSN: | 0195-6698 | |||||||||
Official Date: | October 2018 | |||||||||
Dates: |
|
|||||||||
Volume: | 73 | |||||||||
Page Range: | pp. 138-152 | |||||||||
DOI: | 10.1016/j.ejc.2018.05.007 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 4 June 2018 | |||||||||
Date of first compliant Open Access: | 19 October 2018 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Related URLs: | ||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year