Wednesday, March 31, 2021
3:00pm
to
3:50pm
|
|
Math Seminar Series
(Conferences / Seminars / Lectures)
Combinatorics and Graph Theory
Ira Gessel, Brandeis University, will be speaking.
The topic is "Counting graphs with neighborhood restrictions."
Contact Bruce E Sagan (bsagan@msu.edu) for more information.
A graph is called point-determining (or mating type) if no two vertices have the same neighborhood. An arbitrary graph can be reduced to a point-determining graph by contracting each set of vertices with the same neighborhood to a single vertex, and this decomposition enables us to give a simple exponential generating function for counting point-determining graphs, as accomplished by Ronald Read in 1989. In this talk we will discuss a closely related problem: counting graphs in which no two vertices have complementary neighborhoods. The decomposition approach does not work here. Instead we apply inclusion-exclusion, similarly to its use in rook theory, to obtain a simple exponential generating function for these graphs. We also discuss how this application of inclusion-exclusion is related to Möbius inversion, and how it can be applied to some related problems. more information...
|
(517) 353-0844
