# Search Research Symposium Abstracts

Page 1 of 1

## 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

Page 1 of 1