IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Split graphs: Combinatorial species and asymptotics

  • Sept. 17, 2021
  • 2:30 p.m.


A split graph is a graph whose vertices can be partitioned into a clique (complete graph) and a stable set (independent set). How many split graphs on n vertices are there? Approximately how many are there, as n goes to infinity? Collins and Trenk (2018) have worked on these questions; after briefly summarizing their results, I will show how I have generalized them in the setting of species theory, a powerful framework for counting combinatorial objects acted on by isomorphisms. This generalization leads to a result relating split graphs and bicolored graphs, allowing me to prove the conjecture of Cheng, Collins, and Trenk (2016) that almost all split graphs are "balanced".

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster