Search Research Symposium Abstracts

The rainbow saturation number is linear

Given a graph H, we say that an edge-coloured graph G is H-rainbow saturated if it does not contain a rainbow copy of H, but the addition of any non-edge in any colour creates a rainbow copy of H. The rainbow saturation number rsat(n, H) is the minimum number of edges among all H-rainbow saturated edge-coloured graphs on n vertices. We prove that for any [Read More...]

Presenter: Natasha Morrison, University of Victoria
Authors: Joint work with Natalie Behague (University of Victoria), Tom Johnston, (University of Bristol) Shannon Ogden (University of Victoria), and Shoham Letzter (University College London)
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: September 30, 2023; 9:45 am

The Iterative Independent Model

Deterministic complex networks that use iterative generation algorithms have been found to more closely mirror properties found in real world networks than the standard uniform random graph models. In this talk I will introduce a new, Iterative Independent Model (IIM), significantly generalizing previously studied models. These models use ideas from [Read More...]

Presenter: Abigail Raz, Cooper Union
Authors: Abigail Raz and Erin Meger
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: September 30, 2023; 10:10 am

Maximizing the number of odd cycles in a planar graph

How many copies of a fixed cycle, $C_k$, can a planar graph contain? This problem has been studied in the case of even cycles by Cox-Martin and Lv et al. In this talk, we extend their results to answer the question asymptotically for odd cycles with $k=5,7,9$ and give a bound which is tight up to a factor of $3/2$ for all larger odd cycles. Our bounds [Read More...]

Presenter: Emily Heath, Iowa State University
Authors: Ryan R. Martin, Chris Wells
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: September 30, 2023; 10:35 am

Rainbow Hamiltonian cycles in random graphs

We show that for every \gamma>0 if p>> \frac{\log{n}}{n^{1-gamma}} then a.a.s. any o(pn)-bounded edge-coloured $G(n,p)$ satisfies the following. If $H$ is an n-vertex subgraph of G(n,p) with minimum degree at least p/2+o(n) then G has a rainbow Hamiltonian cycle. Our method largely relies on various probabilistic tools and employs absorption [Read More...]

Presenter: Liana Yepremyan, Emory University
Authors: Julia Boettcher, Peter Allen
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: September 30, 2023; 11:00 am

Enumerating patterns in Social Networks in A Distribution-Free Model

Fox et al introduced the model of c-closed graphs, a distribution-free model motivated by motivated by one of the most universal signatures of social networks, triadic closure. Previous literature shows that the number of maximal cliques and maximal complete bipartite graphs in any c-closed graph on n vertices is always polynomial in n. In this work, we [Read More...]

Presenter: Fan Wei, Duke University
Authors: Gabbie Bourla, Fan Wei
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: October 1, 2023; 2:00 pm

The codiameter of hypergraphs

The codiameter of a graph is the largest integer $k$ such that for any pair of vertices $x$ and $y$, there exists an $x,y$-path of length at least k. Extremal problems on the codiameter of graphs, especially for the case k=n-1 (Hamiltonian-connected graphs), have been well studied. We consider an analogous problem for hypergraphs in which every pair of [Read More...]

Presenter: Ruth Luo, University of South Carolina
Authors: Alexandr Kostochka, Ruth Luo, Grace McCourt
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: October 1, 2023; 2:25 pm

Counting Graphic Sequences

A graphic sequence is a non-increasing sequence of natural numbers that can occur as the degree sequence of a graph. We show that the number of graphic sequences of length n grows like cn^{-3/4}4^n for some constant c. The foundation of our proof consists of a few reformulations, that turn our problem into a question about the lazy simple symmetric random [Read More...]

Presenter: Serte Donderwinkel, McGill University
Authors: Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, Alex Scott
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: October 1, 2023; 2:50 pm

Generalized Ramsey numbers in the non-integral regime

"A $(p,q)$-$\textit{coloring}$ of a graph $G$ is an edge-coloring of $G$ such that every $p$-clique receives at least $q$ colors. In 1975, Erdős and Shelah introduced the $\textit{generalized Ramsey number}$ $f(n,p,q)$ which is the minimum number of colors needed in a $(p,q)$-coloring of $K_n.$ In 1997, Erdős and Gyárfás showed that $f(n,p,q)$ is at [Read More...]

Presenter: Lina Li, Iowa State University
Authors: Patrick Bennett; Michelle Delcourt; Lina Li; Luke Postle
Symposium Year: 2023
Session: Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Presentation Time: October 1, 2023; 3:15 pm