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

Published

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