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 pointdetermining (or mating type) if no two vertices have the same neighborhood. An arbitrary graph can be reduced to a pointdetermining 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 pointdetermining 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 inclusionexclusion, similarly to its use in rook theory, to obtain a simple exponential generating function for these graphs. We also discuss how this application of inclusionexclusion is related to Möbius inversion, and how it can be applied to some related problems. more information...
