Noticias en español
The Ramsey Number of Hypergraph Cycles.
Abstract: In 1999, Łuczak proved that the three-coloured Ramsey number of the cycle of length $n$ is less than $(4+o(1))n$, presenting a technique that, conceptually, through the use of Szemerédi’s regularity lemma, reduces the problem to that of finding the Ramsey number of a connected matching. Ever since then, Łuczak’s method has been applied successfully in many results. There are many natural ways to generalize cycles for $k$-uniform hypergraphs. In this talk, we first present a brief survey of the Ramsey numbers of Berge, loose, and tight cycles. Then we examine the use...
Read MoreAbstract: For a family of graphs H, a graph G is H-free if no induced subgraph of G is isomorphic to a graph in H. In this talk, I will present a new decomposition theorem and coloring algorithm for(2P_3,C_4,C_6)-free graphs. I will also give some background on Truemper configurations (thetas, pyramids, prisms, and wheels) and on proving decomposition theorems in general
Read MoreCanonical Ramsey numbers for partite hypergraphs.
Abstract: Ramsey’s theorem states that for sufficiently large n, any r-colouring of the edges of the complete k-uniform hypergraph on n vertices contains a monochromatic copy of the complete k-uniform hypergraph on t vertices. Erdős and Rado generalised this result to an unbounded number of colours. They characterised all canonical colour patterns that are unavoidable in edge colourings of sufficiently large complete hypergraphs. We consider quantitative aspects of this result. For Erdős and Rado’s theorem, both the lower and upper bound on n grow as (k-1)-times iterated...
Read MoreChromatic threshold via combinatorial convexity, and beyond.
Abstract: We establish a novel connection between the well-known chromatic threshold problem in extremal combinatorics and the celebrated (p,q)-theorem in discrete geometry. In particular, for graphs with bounded clique number and certain natural density condition, we prove a (p,q)-theorem for the dual of its maximal independent sets hypergraph. Our result strengthens those of Thomassen and Nikiforov on the chromatic threshold of cliques. We further show that the graphs under study in fact have `bounded complexity’ in the sense that they are blow-ups of constant size graphs with the same...
Read MoreCanonical 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 More