Counting extensions revisited. Issue 1 (25th February 2022)
- Record Type:
- Journal Article
- Title:
- Counting extensions revisited. Issue 1 (25th February 2022)
- Main Title:
- Counting extensions revisited
- Authors:
- Šileikis, Matas
Warnke, Lutz - Abstract:
- Abstract: We consider rooted subgraphs in random graphs, that is, extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. In 1989, Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices. For the important strictly balanced case, Spencer also raised the fundamental question as to whether these conditions are necessary. We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open.
- Is Part Of:
- Random structures & algorithms. Volume 61:Issue 1(2022)
- Journal:
- Random structures & algorithms
- Issue:
- Volume 61:Issue 1(2022)
- Issue Display:
- Volume 61, Issue 1 (2022)
- Year:
- 2022
- Volume:
- 61
- Issue:
- 1
- Issue Sort Value:
- 2022-0061-0001-0000
- Page Start:
- 3
- Page End:
- 30
- Publication Date:
- 2022-02-25
- Subjects:
- extreme values -- random graph -- rooted subgraphs -- subgraph counts
Random graphs -- Periodicals
Mathematical analysis -- Periodicals
519 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/rsa.21050 ↗
- Languages:
- English
- ISSNs:
- 1042-9832
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 7254.411950
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 22121.xml