Abstrakt
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 the adjacency of u to S. I will present (almost) matching lower and upper bounds for the functionality of random graphs G(n,p) for all possible values of p. For a large range of p, the bounds differ in a constant factor. For values of p that are near to 0 or 1, the bounds differ in log n factor.
This is joint work with L. Folwarczný, M. Opler, P. Pudlák, R. Šámal, T. Vu.