Events Mini Calendar

Go to previous month Go to next month
  S M T W R F S
W9 28 1 2 3 4 5 6
W10 7 8 9 10 11 12 13
W11 14 15 16 17 18 19 20
W12 21 22 23 24 25 26 27
W13 28 29 30 31 1 2 3


Today is:
Fri, Sep 24, 2021


MSU Events Calendar

 
 Choose Calendar view:   Day   Week   Month     Search   Filter

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...


Location: Online via Zoom [map]
Price: free
Sponsor: Department of Mathematics
Contact: Department of Mathematics
phone pic (517) 353-0844