Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T12:59:52.078Z Has data issue: false hasContentIssue false

On the treewidth of random geometric graphs and percolated grids

Published online by Cambridge University Press:  17 March 2017

Anshui Li*
Affiliation:
Hangzhou Normal University
Tobias Müller*
Affiliation:
Utrecht University
*
* Postal address: Department of Mathematics, Hangzhou Normal University, Hangzhou, 310000, P.R. China. Email address: anshuili@hznu.edu.cn
** Postal address: Mathematical Institute, Utrecht University, Utrecht, 3508TA, The Netherlands. Email address: t.muller@uu.nl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we study the treewidth of the random geometric graph, obtained by dropping n points onto the square [0,√n]2 and connecting pairs of points by an edge if their distance is at most r=r(n). We prove a conjecture of Mitsche and Perarnau (2014) stating that, with probability going to 1 as n→∞, the treewidth of the random geometric graph is 𝜣(r√n) when lim inf r>r c, where r c is the critical radius for the appearance of the giant component. The proof makes use of a comparison to standard bond percolation and with a little bit of extra work we are also able to show that, with probability tending to 1 as k→∞, the treewidth of the graph we obtain by retaining each edge of the k×k grid with probability p is 𝜣(k) if p>½ and 𝜣(√log k) if p<½.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2017