2015/06/02 by Joshua Brody, Brody, Joshua, Mario Sánchez García +1 · 3 citations
Computer Science · Economics, Econometrics and Finance · #05C80 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.2 #FOS: Computer and information sciences #Game Theory and Voting Systems #Sports Analytics and Performance
paper · pdf · doi:10.48550/arxiv.1506.01083
openalex publication_date 2015/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs "dependent random graphs". Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. We also obtain bounds for the chromatic number. Surprisingly, many of the standard properties of random graphs also hold in this relaxed setting. We show that with high probability, a dependent random graph will contain a clique of size ((1-o(1))log n)/(log(1/p)), and the chromatic number will be at most (n log(1/1-p))/(log n). As an application and second main result, we give a new communication protocol for the k-player Multiparty Pointer Jumping (MPJk) problem in the number-on-the-forehead (NOF) model. Multiparty Pointer Jumping is one of the canonical NOF communication problems, yet even for three players, its communication complexity is not well understood. Our protocol for MPJ3 costs O((nloglog n)/(log n)) communication, improving on a bound of Brody and Chakrabarti [BC08]. We extend our protocol to the non-Boolean pointer jumping problem \widehatMPJk, achieving an upper bound which is o(n) for any k >= 4 players. This is the first o(n) bound for \widehatMPJk and improves on a bound of Damm, Jukna, and Sgall [DJS98] which has stood for almost twenty years.