Tata Institute of Fundamental Research
Functionality of a Random Graph is Polylogarithmic
STCS Student Seminar
Speaker:
Pavel Dvorak
Organiser:
Eeshan Modak
Date:
Friday, 26 May 2023, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Pavel Dvorak |
| Organiser: | Eeshan Modak |
| Date: | Friday, 26 May 2023, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
Abstract:
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.
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.