The Library
Cliques in dense in homogeneous random graphs
Tools
Dolezal, M., Hladký, Jan and Máthé, András (2017) Cliques in dense in homogeneous random graphs. Random Structures & Algorithms, 51 (2). pp. 275-314. doi:10.1002/rsa.20715 ISSN 1042-9832.
|
PDF
WRAP-cliques-dense-random-graphs-Mathe-2017.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (763Kb) | Preview |
|
PDF
DolezalHladkyMathe.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (579Kb) |
Official URL: http://doi.org/10.1002/rsa.20715
Abstract
The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant math formula of the Erdős–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of math formula for each fixed n, and give examples of graphons for which math formula exhibits wild long-term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably-partite. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Library of Congress Subject Headings (LCSH): | Random graphs | ||||||||
Journal or Publication Title: | Random Structures & Algorithms | ||||||||
Publisher: | John Wiley & Sons, Inc. | ||||||||
ISSN: | 1042-9832 | ||||||||
Official Date: | September 2017 | ||||||||
Dates: |
|
||||||||
Volume: | 51 | ||||||||
Number: | 2 | ||||||||
Page Range: | pp. 275-314 | ||||||||
DOI: | 10.1002/rsa.20715 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Date of first compliant deposit: | 30 November 2016 | ||||||||
Date of first compliant Open Access: | 14 June 2017 | ||||||||
Funder: | Grantová agentura České republiky [Czech Science Foundation] (AVČR), Rijksdienst voor Ondernemend (RVO), Marie Skłodowska-Curie Actions, Seventh Framework Programme (European Commission) (FP7), Leverhulme Trust (LT). Early Career Fellowship, Hungary. Nemzeti Kutatási Fejlesztés És Innovációs Hivatal [National Research, Development and Innovation Office] (NKFIH) | ||||||||
Grant number: | 6-07378S (AVČR), 67985840 (RVO), 628974 (FP7), 104178 (NKFIH) |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year