Noticias en español
Canonical colourings in random graphs.
Abstract: The canonical Ramsey theorem of Erdős and Rado impliesthat for a given graph H, if n is sufficiently large then any colouring of the edges of K_n gives rise to copies of H that exhibit certain colour patterns, namely monochromatic, rainbow or lexicographic. I will discuss recent results on the threshold at which the random graph G(n,p) inherits the canonical Ramsey properties of K_n.
Read MoreErd\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...
Read MoreRainbow path separation systems (RPSS)
Abstract: A family of paths P in a graph G is (k,t)-rainbow separating if it can be coloured with k colours such that for every t-tuple of edges e_1, …, e_t there exist t paths P_1, …, P_t of distinct colours such that P_i contains the edge e_i and does not contain any other edge of the t-tuple. Much work has been done on (∞,2)-RPSS, also known as strong path separation systems. In this talk I will present some optimal results on (2,2)-RPSS, together with a more general treatise on (k,2)-RPSS for all values of k.
Read MoreMetric properties of locally connected graphs.
Abstract: A set of n points in the plane which are not all collinear defines at least n distinct lines. In 2008, Chen and Chvátal conjectured that this property holds for all finite metric spaces. This conjecture is still open, even for metric spaces induced by graphs. In this talk, we show that locally connected graphs satisfy this property and an even stronger one.
Read MoreTurán problem for edge-ordered graphs.
Abstract: The Turán-type extremal problem asks how many edges an n-vertex simple graph can have if it does not contain a subgraph isomorphic to a forbidden graph. The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner, Methuku, Nagy, Pálvölgyi, Tardos, and Vizer in 2020. A simple graph is called edge-ordered if its edges are linearly ordered. Gerbner et al. defined a parameter called order chromatic number for edge-ordered graphs and proved an Erdős-Stone-Simonovits-type theorem for edge ordered graphs that determines the Turán number of an...
Read MorePowers of Hamilton cycles in directed and oriented graphs.
Abstract: The P\’osa–Seymour conjecture determines the minimum degree threshold for forcing the $k$th power of a Hamilton cycle in a graph. After numerous partial results, Koml\’os, S\’ark\”ozy and Szemer\’edi proved the conjecture for sufficiently large graphs. We focus on the analogous problem for digraphs and for oriented graphs. For digraphs, we asymptotically determine the minimum total degree threshold for forcing the square of a Hamilton cycle. We also give a conjecture on the corresponding threshold for $k$th powers of a Hamilton cycle more...
Read More