{"id":544,"date":"2024-03-11T17:42:16","date_gmt":"2024-03-11T20:42:16","guid":{"rendered":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/?p=544"},"modified":"2024-03-21T12:17:54","modified_gmt":"2024-03-21T15:17:54","slug":"caminos-de-santiago-small-separating-path-systems-for-complete-graphs","status":"publish","type":"post","link":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/2024\/03\/caminos-de-santiago-small-separating-path-systems-for-complete-graphs\/","title":{"rendered":"Caminos de Santiago: small separating path systems for complete  graphs"},"content":{"rendered":"<h3>Speaker: <a href=\"https:\/\/sites.google.com\/view\/george-kontogeorgiou\/home\" target=\"_blank\" rel=\"noopener\">Georgios Kontogeorgiou<\/a><br \/>\nCenter for Mathematical Modeling, U. de Chile<br \/>\nDate: Tuesday, March 12, 2024 at 2:30 p.m. Santiago time<\/h3>\n<p><strong>Abstract:<\/strong> In a communication network of n nodes, each linked to every other, a single link fails. How can we discover which link is broken without going through the burdensome process of examining separately all \\( \\Theta(n^2)\\) of them? A quick way to determine the faulty link would be to propagate messages through a designated set of paths S, such that for every two links there exists a path in S that contains exactly one of them. We say that such a set S (weakly) separates the network. It is known that a separating path system for a network of n nodes must contain at least n-1 paths. Recently, Fernandes, Oliveira Mota and Sanhueza-Matamala proved that \\((1+o(1))n\\) paths suffice.<\/p>\n<p>I will talk about the history and motivation of this problem and give a short proof that n+2 paths are enough. This is joint work with Maya Stein.<\/p>\n<p><strong>Venue:<\/strong> Sala John Von Neumann, 7th floor, Beauchef 851<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Georgios Kontogeorgiou (CMM, U. de Chile)<\/p>\n","protected":false},"author":2,"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-544","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\/544","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/comments?post=544"}],"version-history":[{"count":5,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/544\/revisions"}],"predecessor-version":[{"id":546,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/544\/revisions\/546"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/media?parent=544"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/categories?post=544"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/tags?post=544"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}