« search calendars« Graduate Combinatorics Seminar

« Automorphisms of Induced Subgraphs of G(n,1/2)

Automorphisms of Induced Subgraphs of G(n,1/2)

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.