Department of Mathematics Calendar

Back to Listing

The Department of Mathematics Calendar has moved to Webtools. Anyone may submit an event by clicking the "+" button (upper right). Note: the Sponsor field is required. Just type "n/a"

All events will be reviewed before acceptance. Please email Shelby Koehne if you have any questions about submitting an event.

Note: you may search past and future events by clicking on the magnifying glass icon on the main Calendar page.

For an archive of past events: https://math.illinois.edu/research/seminars-department-calendar

Graph Theory and Combinatorics Seminar: Two conjectures on the spread of graphs

Event Type
Seminar/Symposium
Sponsor
N/A
Virtual
wifi event
Date
Jan 25, 2022   1:00 pm  
Speaker
Michael Tait (Villanova University)
Contact
Sean English
E-Mail
senglish@illinois.edu
Views
8

Given a graph G let lambda_1 and lambda_n be the maximum and minimum eigenvalues of its adjacency matrix and define the spread of G to be lambda_1 - lambda_n. In this talk we discuss solutions to a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs.

   
The first, referred to as the spread conjecture, states that over all graphs on $n$ vertices the join of a clique of order floor(2n/3) and an independent set of order ceiling(n/3) is the unique graph with maximum spread. The second, referred to as the bipartite spread conjecture, says that for any fixed e <= n^2/4, if G has maximum spread over all n-vertex graphs with e edges, then G must be bipartite.
 

We show that the spread conjecture is true for all sufficiently large n, and we prove an asymptotic version of the bipartite spread conjecture. Furthermore, we exhibit an infinite family of counterexamples to the bipartite spread conjecture which shows that our asymptotic solution is tight up to a multiplicative factor in the error term. This is joint work with Jane Breen, Alex Riasanovsky, and John Urschel.

Please email Sean English (senglish@illinois.edu) for Zoom link.

link for robots only