Home /  Workshop /  Schedules /  Decomposing regular graphs into stars

Decomposing regular graphs into stars

Connections Workshop: Extremal Combinatorics February 06, 2025 - February 07, 2025

February 07, 2025 (09:00 AM PST - 10:00 AM PST)
Speaker(s): Catherine Greenhill (UNSW Sydney)
Location: SLMath: Eisenbud Auditorium, Online/Virtual
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Video

Decomposing regular graphs into stars

Abstract

Zoom Link

A $k$-star decomposition of a graph is a partition of the edge set into disjoint $k$-stars. Using the small subgraph conditioning method (SSCM), in 2018 Delcourt and Postle proved that with high probability, a random 4-regular graph has a 3-star decomposition. I will describe work to generalise this result. We have proved, again using the SSCM, that if a certain equation has a unique solution then with high probability, a random $d$-regular graphs has a $k$-star decomposition. We also prove that this sufficient condition holds whenever $k\leq d/2 + \log(d)/6$. There are connections with earlier work on beta-orientations which can be used to prove existence of $k$-star decompositions when $k \leq d/2$, while non-existence results can be obtained using a connection with independent sets in random regular graphs.

Supplements No Notes/Supplements Uploaded
Video/Audio Files

Decomposing regular graphs into stars

Troubles with video?

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.