Speaker:

Pavel Dvorak, TIFR

## Time:

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

## Venue:

- A201

## Organisers:

The functionality of a graph defined by [Alecu et al.: Graph functionality, JCTB2021] is a parameter that generalizes graph degeneracy.

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.