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.
