Ben Barber and Eoin Long, The Electronic Journal of Combinatorics, 20(4) (2013), #P25<\/a>\u00a0PDF<\/a><\/p>\n

Take a long (proportional to ) random walk in a quasirandom graph . Must the subgraph of edges traversed by be quasirandom? We’d like to say yes, for the following reason: visits every vertex about the same number of times, so we pick up the same number of random edges at every vertex. In the case where the minimum degree of is large, this argument is essentially correct. If has some vertices of very low degree then it breaks down because the random walk can get stuck in clusters of low degree vertices. However, a more sophisticated argument can recover a result that is almost as strong.<\/p>\n

The proofs both fall into two parts: first show that the random walk does not differ too much from a process that has much more independence, then exploit that independence by applying standard concentration results to show that things work with high probability. It turns out that our results can be tweaked to apply to the more general case of random homomorphisms of trees (rather than paths) provided the maximum degree of the tree isn’t too large, so we indicate the necessary changes at the end of the paper.<\/p>\n","protected":false},"excerpt":{"rendered":"

Ben Barber and Eoin Long, The Electronic Journal of Combinatorics, 20(4) (2013), #P25\u00a0PDF Take a long (proportional to ) random walk in a quasirandom graph . Must the subgraph of edges traversed by be quasirandom? We’d like to say yes, for the following reason: visits every vertex about the same number of times, so we … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[3],"tags":[17,28,31],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/92"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=92"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/92\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=92"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=92"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=92"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}