October 30, 2019, 12:15 PM - 1:15 PM
Location:
Mathematics Graduate Student Lounge -- 7th Floor
Rutgers University
Hill Center
Mathematics Department
110 Frelinghuysen Road
Piscataway, NJ 08854
Keith Frankston, Rutgers University
The Erdős Rényi random graph (denoted G(n,1/2)) is a random object on n vertices where each edge appears independently with probability 1/2. We call a graph rigid if it has no non-trivial automorphisms. A classical result in random graph theory states that the probability that G(n,1/2) is rigid goes to 1 (as n goes to infinity). In this talk we discuss what happens when we look, not at G(n,1/2), but its induced subgraphs. We will show that almost surely any induced subgraph of size (1+ε)n/2 is rigid by looking at a more general result.