Almost Complete Characterization of Functionality of Random Graphs

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.