Description
Abstract: According to a classical result, the largest clique in $G(n,1/2)$ has asymptotically $2\log n$ vertices with high probability, where log is the base 2 logarithm. As a special instance of the Subgraph Query Problem initiated by Ferber et al., the following question arises: can we find such a large clique with high probability if we are only allowed to query a limited number of pairs in $G(n,1/2)$? In each query we can inquire whether a pair of vertices constitutes an edge. Other than the number of queries, there is no limitation on the complexity of the algorithm: we are allowed to carry out an arbitrarily large (finite) amount of computation. The problem is non-trivial if we have $n^\delta$ queries for some $\delta \in [1,2)$; if $\delta=2$, we can uncover the whole graph structure and find a largest clique of size $2\log n$ (w.h.p.).
Feige et al. showed that for any $\delta \in [1,2)$, the largest clique we can find by such an algorithm (w.h.p.) is at most $\alpha\log n$ for some $\alpha<2$ that depends on $\delta$. The best known upper bound was shown by Alweiss et al. recently; for instance, for $\delta=1$ their formula yields $\alpha\leq 1+1/\sqrt{2}$.
With Endre Csóka, we studied the $l$-adaptive variant of the problem during the Focused Workshop on Networks and Their Limits, held at the Erdős Center in July 2023. That is, there is a fixed number of rounds $l$, and in each round we have to tell in advance which set of pairs the algorithm would query (only taking into consideration the outcome of the previous rounds). With this additional limitation, we have proven stronger upper bounds for $\alpha$ than that of Alweiss et al. in the fully adaptive version of the clique problem. Moreover, we extended the results to the maximum size of subgraphs with prescribed minimum edge density that can be found by $n^\delta$ ($l$-adaptive or fully adaptive) edge queries in $G(n,1/2)$.
The proof hinges on finding the optimal solution of a combinatorial problem that involves the parameter $l$. We managed to do so for $l=2$, $l=3$, and $l=\infty$, and we proved non-trivial upper bounds for $l\geq 4$. These upper bounds for $l\geq 4$ are almost certainly not sharp, and could potentially be improved on. We pose this as an open problem in the talk.