Algorithms, Combinatorics and Optimization Seminar
— 4:00pm
Location:
In Person
-
Wean Hall 8220
Speaker:
XAVIER PÉREZ GIMÉNEZ
,
Associate Professor, Department of Mathematics, University of Nebraska-Lincoln
https://math.unl.edu/xperezgimenez2
Perfect matchings in the random bipartite geometric graph
We consider the standard random bipartite geometric graph process in which n red vertices and n blue vertices are placed at random on the unit d-dimensional cube and edges are added sequentially, between vertices of different colors, in increasing order of edge-length. A natural question is to ask whether the first edge in the process that results in the minimum degree being at least one coincides, with high probability, with the first edge that creates a perfect matching. While this was already known to be false when d=2, as the thresholds are not even of the same order, we are able to positively answer it for dimension d at least 3.
This is joint work with Abigail Raz.
Tea and cookies at 4pm in the Math Lounge, Wean 6220 (bring your own cup if possible)
Event Website:
https://aco.math.cmu.edu/abs-23-24/apr25.html