{"id":4401,"date":"2021-10-20T23:55:54","date_gmt":"2021-10-21T03:55:54","guid":{"rendered":"http:\/\/matroidunion.org\/?p=4401"},"modified":"2021-10-27T23:44:32","modified_gmt":"2021-10-28T03:44:32","slug":"online-talk-natalie-behague","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=4401","title":{"rendered":"Online Talk: Natalie Behague"},"content":{"rendered":"\n<p><strong>Tuesday, Oct 26,<\/strong> <strong>3pm ET<\/strong> (8pm BST, 8am Wed NZST)<br \/><strong><a href=\"https:\/\/www.researchgate.net\/profile\/Natalie-Behague\">Natalie Behague<\/a><\/strong>, Ryerson University<br \/><strong>Subgraph Games in the Semi-random Graph Process<\/strong><\/p>\n<div><strong>YouTube: <\/strong><a href=\"https:\/\/youtu.be\/oxWKnYpAzKk\">https:\/\/youtu.be\/oxWKnYpAzKk<\/a><\/div>\n<h5>\u00a0<\/h5>\n<h5><strong>Abstract:<\/strong><\/h5>\n<div>The semi-random graph process can be thought of as a one player game. Starting with an empty graph on $n$ vertices, in each round a random vertex $u$ is presented to the player, who chooses a vertex $v$ and adds the edge $uv$ to the graph. Given a graph property, the objective of the player is to force the graph to satisfy this property in as few rounds as possible.<\/div>\n<div>\u00a0<\/div>\n<div>We will consider the property of constructing a fixed graph $G$ as a subgraph of the semi-random graph. Ben-Eliezer, Gishboliner, Hefetz and Krivelevich proved that the player can asymptotically almost surely construct $G$ given $n^{1\u20131\/d}w$ rounds, where $w$ is any function tending to infinity with $n$ and $d$ is the degeneracy of the graph $G$. We have proved a matching lower bound. I will talk about this result, and discuss a generalisation of our approach to semi-random hypergraphs. I will finish with some open questions.<\/div>\n<div>\u00a0<\/div>\n<div>This is joint work with Trent Marbach, Pawel Pra\u0142at and Andrzej Ruci\u0144ski.<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Tuesday, Oct 26, 3pm ET (8pm BST, 8am Wed NZST)Natalie Behague, Ryerson UniversitySubgraph Games in the Semi-random Graph Process YouTube: https:\/\/youtu.be\/oxWKnYpAzKk \u00a0 Abstract: The semi-random graph process can be thought of as a one player game. Starting with an empty &hellip; <a href=\"https:\/\/matroidunion.org\/?p=4401\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":20,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[11],"class_list":["post-4401","post","type-post","status-publish","format-standard","hentry","category-matroids","tag-online-talks"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4401","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/20"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4401"}],"version-history":[{"count":5,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4401\/revisions"}],"predecessor-version":[{"id":4416,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/4401\/revisions\/4416"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4401"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4401"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4401"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}