Erd\H{o}s-Ko-Rado Problems for Graphs.

Abstract: In this talk, we introduce a new line of research exploring the size and structure of the largest intersecting family of paths in a graph. A family of sets is called intersecting if every pair of its members share an element; such an intersecting family is called a star if some element is in every member of the family. Erd\H{o}s-Ko-Rado famously proved (1938, 1962) that the maximum size intersecting families of r-subsets of {1,2,…,n} (with r<=n/2) are precisely the stars. Here, we consider families of sets where the sets are the vertex sets of paths in a fixed graph. We prove Erd\H{o}s-Ko-Rado type structural results for families of r-paths in a graph G, for several infinite classes of graphs G. This is joint work with James Danielsson and Glenn Hurlbert.

Posted on Dec 4, 2024 in Seminario de Grafos, Seminars