Twin-width of random graphs
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ahn, Jungho | - |
dc.contributor.author | Chakraborti, Debsoumya | - |
dc.contributor.author | Kevin Hendrey | - |
dc.contributor.author | Donggyu Kim | - |
dc.contributor.author | Sang-il Oum | - |
dc.date.accessioned | 2024-12-12T07:00:54Z | - |
dc.date.available | 2024-12-12T07:00:54Z | - |
dc.date.created | 2024-06-24 | - |
dc.date.issued | 2024-12 | - |
dc.identifier.issn | 1042-9832 | - |
dc.identifier.uri | https://pr.ibs.re.kr/handle/8788114/15554 | - |
dc.description.abstract | We investigate the twin-width of the Erdos-Renyi random graph G n,p). We unveil a surprising behavior of this parameter by showing the existence of a constant p & lowast;approximate to 0.4such that with high probability, when p & lowast;<= p <= 1-p & lowast;,the twin-width is asymptotically 2p(1-p)n, whereas, when0<p<p & lowast;or 1>p>1-p & lowast;, the twin-width is significantly higher than 2p(1-p)n. In addition, we show that the twin-width of G(n,1/2)is concentrated aroundn/2-root 3nlogn/2 within an interval of length o(root n log n).For the sparse random graph, we show that with high probability, the twin-width of G(n,p) is Theta (n root p) when (726 ln n)/ n <= p <= 1/2 | - |
dc.language | 영어 | - |
dc.publisher | John Wiley & Sons Inc. | - |
dc.title | Twin-width of random graphs | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 001248187800001 | - |
dc.identifier.scopusid | 2-s2.0-85196109476 | - |
dc.identifier.rimsid | 83329 | - |
dc.contributor.affiliatedAuthor | Kevin Hendrey | - |
dc.contributor.affiliatedAuthor | Donggyu Kim | - |
dc.contributor.affiliatedAuthor | Sang-il Oum | - |
dc.identifier.doi | 10.1002/rsa.21247 | - |
dc.identifier.bibliographicCitation | Random Structures and Algorithms, v.65, no.4, pp.794 - 831 | - |
dc.relation.isPartOf | Random Structures and Algorithms | - |
dc.citation.title | Random Structures and Algorithms | - |
dc.citation.volume | 65 | - |
dc.citation.number | 4 | - |
dc.citation.startPage | 794 | - |
dc.citation.endPage | 831 | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Software Engineering | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.relation.journalWebOfScienceCategory | Mathematics | - |
dc.subject.keywordAuthor | random graph | - |
dc.subject.keywordAuthor | threshold | - |
dc.subject.keywordAuthor | twin-width | - |