{"id":640,"date":"2024-10-17T12:46:17","date_gmt":"2024-10-17T15:46:17","guid":{"rendered":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/?p=640"},"modified":"2024-10-24T10:51:11","modified_gmt":"2024-10-24T13:51:11","slug":"tree-embedding-problem-for-digraphs","status":"publish","type":"post","link":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/2024\/10\/tree-embedding-problem-for-digraphs\/","title":{"rendered":"Tree Embedding Problem for Digraphs"},"content":{"rendered":"<h3>Speaker: <a href=\"https:\/\/www.cmm.uchile.cl\/?cmm_people=ana-laura-trujillo\">Ana Laura Trujillo<\/a><br \/>\nCenter for Mathematical Modeling, U. de Chile<br \/>\nDate: Monday, October 21, 2024 at 2:30 p.m. Santiago time<\/h3>\n<p style=\"text-align: left\"><strong>Abstract:\u00a0\u00a0<\/strong><\/p>\n<p>The<em> tree embedding problem<\/em> focuses on identifying the minimal conditions a graph $G$ must satisfy to ensure it contains all trees with $k$ edges. Here, a graph $G$ consists of a set $V$ of elements called vertices, and a set $E$ of (unordered) pairs of vertices, called edges. We say that a graph $G$ is a tree if, for any pair of vertices, there is exactly one path connecting them.<\/p>\n<p>Erd\\H{o}s and S\u00f3s conjectured that any graph $G$ with $n$ vertices and more than $(k-1)n\/2$ edges contains every tree with $k$ edges. This conjecture has been generalized into the Antitree Conjecture by Addario-Berry et al., which states that every digraph $D$ with $n$ vertices and more than $(k-1)n$ arcs contains every antidirected tree with $k$ arcs. Here, a digraph $D$ consists of a set $V$ of vertices and a set $A$ of arcs (ordered pairs of vertices), and an antidirected tree is a tree in which the edges are directed so that each vertex has only incoming or outgoing arcs.<\/p>\n<p>In this talk, we present a proof of the Antitree Conjecture for the case where the digraph $D$ does not contain certain orientations of the complete bipartite graph $K_{2,s}$, where $s = k\/12$. Additionally, we explore a proof of this conjecture for antidirected caterpillars. This work is a collaboration with Maya Stein.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Venue:<\/strong> John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor<\/p>\n<div class=\"notranslate\"><\/div>\n<div class=\"notranslate\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Ana Laura Trujillo (CMM, U. de Chile)<\/p>\n","protected":false},"author":103,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[5],"tags":[],"class_list":["post-640","post","type-post","status-publish","format-standard","hentry","category-past-seminar"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/640","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/users\/103"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/comments?post=640"}],"version-history":[{"count":2,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/640\/revisions"}],"predecessor-version":[{"id":642,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/640\/revisions\/642"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/media?parent=640"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/categories?post=640"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/tags?post=640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}