Speaker: |
Pavel Dvorak |

Organiser: |
Eeshan Modak |

Date: |
Friday, 26 May 2023, 16:00 to 17:00 |

Venue: |
A201 |

(Scan to add to calendar)

Informally, the functionality of a graph G is minimal k such that in any induced subgraph H of G there is a vertex v in H and a set S of k vertices that the adjacency of v and any vertex u in H is determined by adjacency of u and S.

I'll show that random graph G = G(n,p) has functionality asymptotically at least log n and at most log^3 n. The upper bound is a fresh new result, I'll be happy to discuss its correctness.

This is joint work with L. Folwarczný, M. Opler, P. Pudlák, R. Šámal, T. Vu.