Description
Combinatorics seminar.
Speaker: Deepanshu Kush.
Affiliation: IIT Bombay.
Date and Time: Tuesday 22August, 2:00 pm - 3:00 pm.
Venue: Ramanujan Hall, Department of Mathematics.
Title: Normalized Matching Property in Random & Pseudorandom Graphs.
Abstract: Normalized Matching Property (NMP) is a simple and natural
generalization of the famous Hall's marriage condition for bipartite
graphs, to the setting when the sizes of the two vertex classes are
distinct. It is a well-studied notion in the context of graded posets and
several well-known ones are known to have it (for instance the boolean
lattice or the poset of subspaces of a finite dimensional vector space).
However, in this talk, we will consider NMP with a 'random twist': if for
every possible edge in a bipartite graph, we toss a coin in order to
decide if we keep it or not, how biased must the coin be to expect to have
NMP in the graph with high probability? We shall arrive at a sharp
threshold for this event. Next, what can we say about explicit graphs that
are known to behave 'random-like'? One of the earliest notions of a
pseudorandom graph was given by Thomason in the 80s. We shall prove an
'almost' vertex decomposition theorem: every Thomason pseudorandom
bipartite graph admits - except for a negligible portion of its vertex set
- a partition of its vertex set into trees that have NMP and which arise
organically through the Euclidean GCD algorithm.