2023/10/10 by Csóka, Endre, Pongrácz, András
#05C80 #05C85 #68Q87 #68W20 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.06826
We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Recall that the largest clique in G ∼ G(n,1/2) has size roughly 2log2 n. Let α⋆(δ,ℓ) be the supremum over α such that there exists an algorithm that makes nδ queries in total to the adjacency matrix of G, in a constant ℓ number of rounds, and outputs a clique of size αlog2 n with high probability. We give improved upper bounds on α⋆(δ,ℓ) for every δ∈ [1,2) and ℓ ≥ 3. We also study analogous questions for finding subgraphs with density at least η for a given η, and prove corresponding impossibility results.