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


Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • September 24, 2012

Published In

Volume / Issue

  • 7456 LNCS /

Start / End Page

  • 282 - 290

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783642326202

Digital Object Identifier (DOI)

  • 10.1007/978-3-642-32621-9_21

Citation Source

  • Scopus