BEGIN:VCALENDAR
VERSION:2.0
METHOD:PUBLISH
PRODID:-//Virginia Tech//VT Calendar//EN
BEGIN:VEVENT
DTSTAMP:20210331T200000Z
UID:1616767751211@events.msu.edu
CATEGORIES:Conferences / Seminars / Lectures
DTSTART:20210331T200000Z
DTEND:20210331T205000Z
SUMMARY:Math Seminar Series
DESCRIPTION:
Combinatorics and Graph Theory\n
\n
Ira Gessel,
Brandeis University, will be speaking.\n
\n
The
topic is "Counting graphs with neighborhood
restrictions."\n
\n
Contact Bruce E Sagan (bsagan@msu.edu)
for more information.\n
\n
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.\n\n
Price: free\n
Sponsor: Department of Mathematics\n
Sponsor's Homepage: https://www.math.msu.edu/\n
Contact name: Department of Mathematics\n
Contact phone: (517) 353-0844\n
for more info visit the web at:\n
https://www.math.msu.edu/Seminars/CalendarView.aspx?month-of=September2016\n
LOCATION:Online via Zoom
END:VEVENT
END:VCALENDAR