Pebbling in Erdős-Rényi random graphs
| dc.contributor.author | Gutkin, Max | |
| dc.contributor.examiningcommittee | Ferrari, Margherita (Mathematics) | |
| dc.contributor.examiningcommittee | Durocher, Stephane (Computer Science) | |
| dc.contributor.supervisor | Gunderson, Karen | |
| dc.date.accessioned | 2024-01-16T19:17:00Z | |
| dc.date.available | 2024-01-16T19:17:00Z | |
| dc.date.issued | 2023-12-31 | |
| dc.date.submitted | 2024-01-01T00:08:59Z | en_US |
| dc.degree.discipline | Mathematics | en_US |
| dc.degree.level | Master of Science (M.Sc.) | |
| dc.description.abstract | Graph pebbling is a game in which a collection of pebbles is placed on the vertices of a connected graph. A pebbling move consists of removing two pebbles from one vertex and placing a pebble on any adjacent vertex. Of interest is the pebbling number of a graph G: the least k such that for any collection of k pebbles on V(G) and any target v ∈ V(G), there exists a sequence of pebbling moves placing a pebble on v. It is well-known that the pebbling number of a graph G is at least |V(G)| and is, in general, bounded above by an exponential function of |V(G)|. The Erdős-Rényi random graph model has frequently been used to address questions relating to the ‘typical’ behaviour of a graph with regards to some interesting property. This model has been used to show that almost all graphs G with at least a constant fraction of the possible edges have pebbling number |V(G)|. In addition to a survey of selected pebbling results and techniques, this thesis presents a first- of-its-kind result showing that even amongst graphs with a much smaller proportion of edges, graphs of large pebbling number are rare: almost all graphs on n vertices and more than (nlogn)/2 edges have pebbling number bounded above by a linear function of n – significantly smaller than the exponential in n bound for arbitrary graphs. Furthermore, it is shown that almost all graphs on n vertices with more than (n/2)exp(√log n) edges have pebbling number n, an improvement over the current best result. Various additional original results are given, including a strongly improved upper bound on the pebbling number of the Kneser graph Kn(7,3). | |
| dc.description.note | February 2024 | |
| dc.description.sponsorship | University of Manitoba Department of Mathematics | |
| dc.identifier.uri | http://hdl.handle.net/1993/37992 | |
| dc.language.iso | eng | |
| dc.rights | open access | en_US |
| dc.subject | graph theory | |
| dc.subject | graph processes | |
| dc.subject | graph pebbling | |
| dc.subject | random graphs | |
| dc.title | Pebbling in Erdős-Rényi random graphs | |
| dc.type | master thesis | en_US |
| local.subject.manitoba | no | |
| oaire.awardNumber | 575570-2022 | |
| oaire.awardTitle | Alexander Graham Bell Canada Graduate Scholarships - Master's | |
| oaire.awardURI | https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758420 | |
| project.funder.identifier | https://doi.org/10.13039/501100000038 | |
| project.funder.name | Natural Sciences and Engineering Research Council of Canada |