A tight upper bound on the number of variables for average-case k-clique on ordered graphs

A first-order sentence φ defines k-clique in the average-case if lim/n→∞ Pr/G=G(n,p) [G unknown sign φ ⇔ G contains a k-clique] = 1 where G = G(n,p) is the Erdos-Rényi random graph with p (= p(n)) the exact threshold such that Pr[G(n,p) has a k-clique] = 1/2. We are interested in the question: How many variables are required to define average-case k-clique in first-order logic? Here we consider first-order logic in vocabularies which, in addition to the adjacency relation of G, may include fixed "background" relations on the vertex set {1,...,n} (for example, linear order). Some previous results on this question: - With no background relations, k/2 variables are necessary and k/2+ O(1) variables are sufficient (Ch. 6 of [7]). - With arbitrary background relations, k/4 variables are necessary [6]. - With arithmetic background relations (<, +, x), k/4+O(1) variables are sufficient (Amano [1]). In this paper, we tie up a loose end (matching the lower bound of [6] and improving the upper bound of [1]) by showing that k/4+O(1) variables are sufficient with only a linear order in the background. © 2012 Springer-Verlag.

Duke Scholars

Author Benjamin Rossman Computer Science