{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/367915"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/367915","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Phase transition for cutoff for random walks on random graphs","abstract":"In this thesis, we analyse the cutoff phenomenon on two different random graph models. First, we consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has a given number of internal, degint ≥ 3, and outgoing, degout, half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and that they all have comparable sizes, we prove the following dichotomy: a simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q and log n (where n is the number of vertices) diverges. In [5], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove that the same characterisation of cutoff holds for a simple random walk. In the second part of the thesis, we analyse a graph G* obtained from a finite deterministic graph G = (V,E) by considering a random perfect matching of V and adding the corresponding edges to G with weight ε, while assigning weight 1 to the original edges of G. For various sequences of graphs Gn and corresponding weights εn, we establish if the (weighted) random walk on G*n has cutoff. In particular, we show a phase transition for two families of graphs, graphs with polynomial growth of balls, and graphs where the entropy of the simple random walk grows linearly up to the time of order log|Vn|. These include in particular tori, expander families and locally expanding families. We also show that this phase transition is sharp in the case of expander graphs and vertex transitive graphs with polynomial growth of balls.","abstract_html":"In this thesis, we analyse the cutoff phenomenon on two different random graph models. First, we consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has a given number of internal, degint ≥ 3, and outgoing, degout, half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and that they all have comparable sizes, we prove the following dichotomy: a simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q and log n (where n is the number of vertices) diverges. In [5], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove that the same characterisation of cutoff holds for a simple random walk. In the second part of the thesis, we analyse a graph G* obtained from a finite deterministic graph G = (V,E) by considering a random perfect matching of V and adding the corresponding edges to G with weight ε, while assigning weight 1 to the original edges of G. For various sequences of graphs Gn and corresponding weights εn, we establish if the (weighted) random walk on G*n has cutoff. In particular, we show a phase transition for two families of graphs, graphs with polynomial growth of balls, and graphs where the entropy of the simple random walk grows linearly up to the time of order log|Vn|. These include in particular tori, expander families and locally expanding families. We also show that this phase transition is sharp in the case of expander graphs and vertex transitive graphs with polynomial growth of balls.","abstract_has_math":false,"creators":["Šarković, Andela"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Sousi, Perla"],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-07-17","date_published":"2023-07-17","updated_at":"2026-07-22T22:23:54Z","subjects":["cutoff","entropy","mixing time","random graphs"],"languages":["eng"],"rights":[],"rights_urls":["https://www.repository.cam.ac.uk/bitstreams/6504934c-653b-466b-b338-21cd32e0f2f3/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.108327","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Sousi, Perla"]},{"key":"dc:creator","label":"Author","values":["Šarković, Andela"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2023-07-17"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/367915"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["cutoff","entropy","mixing time","random graphs"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://www.repository.cam.ac.uk/bitstreams/6504934c-653b-466b-b338-21cd32e0f2f3/download","https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.108327"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://www.repository.cam.ac.uk/bitstreams/3301f10a-c9f8-4ad6-b0f3-136a17b7de25/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we analyse the cutoff phenomenon on two different random graph models. First, we consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has a given number of internal, degint ≥ 3, and outgoing, degout, half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and that they all have comparable sizes, we prove the following dichotomy: a simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q and log n (where n is the number of vertices) diverges. In [5], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove that the same characterisation of cutoff holds for a simple random walk. In the second part of the thesis, we analyse a graph G* obtained from a finite deterministic graph G = (V,E) by considering a random perfect matching of V and adding the corresponding edges to G with weight ε, while assigning weight 1 to the original edges of G. For various sequences of graphs Gn and corresponding weights εn, we establish if the (weighted) random walk on G*n has cutoff. In particular, we show a phase transition for two families of graphs, graphs with polynomial growth of balls, and graphs where the entropy of the simple random walk grows linearly up to the time of order log|Vn|. These include in particular tori, expander families and locally expanding families. We also show that this phase transition is sharp in the case of expander graphs and vertex transitive graphs with polynomial growth of balls."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["b4f91568ead5b78809fe6cc9a700285e","87eda9de84448d1f82354d60eee3eb5f"]},{"key":"dc:title","label":"Title","values":["Phase transition for cutoff for random walks on random graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Sousi, Perla"],"dc:creator":["Šarković, Andela"],"dc:date.issued":["2023-07-17"],"dc:description.abstract":["In this thesis, we analyse the cutoff phenomenon on two different random graph models. First, we consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has a given number of internal, degint ≥ 3, and outgoing, degout, half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and that they all have comparable sizes, we prove the following dichotomy: a simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q and log n (where n is the number of vertices) diverges. In [5], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove that the same characterisation of cutoff holds for a simple random walk. In the second part of the thesis, we analyse a graph G* obtained from a finite deterministic graph G = (V,E) by considering a random perfect matching of V and adding the corresponding edges to G with weight ε, while assigning weight 1 to the original edges of G. For various sequences of graphs Gn and corresponding weights εn, we establish if the (weighted) random walk on G*n has cutoff. In particular, we show a phase transition for two families of graphs, graphs with polynomial growth of balls, and graphs where the entropy of the simple random walk grows linearly up to the time of order log|Vn|. These include in particular tori, expander families and locally expanding families. We also show that this phase transition is sharp in the case of expander graphs and vertex transitive graphs with polynomial growth of balls."],"dc:format.checksum.md5":["b4f91568ead5b78809fe6cc9a700285e","87eda9de84448d1f82354d60eee3eb5f"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.108327"],"dc:identifier.uri":["https://www.repository.cam.ac.uk/bitstreams/3301f10a-c9f8-4ad6-b0f3-136a17b7de25/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/367915"],"dc:rights":["https://www.repository.cam.ac.uk/bitstreams/6504934c-653b-466b-b338-21cd32e0f2f3/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["cutoff","entropy","mixing time","random graphs"],"dc:title":["Phase transition for cutoff for random walks on random graphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:23:54Z"}