Math @ Duke

Publications [#348687] of Benjamin Rossman
Papers Published
 Rossman, B, A tight upper bound on the number of variables for averagecase kclique on ordered graphs,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7456 LNCS
(September, 2012),
pp. 282290, ISBN 9783642326202 [doi]
(last updated on 2022/05/21)
Abstract: A firstorder sentence φ defines kclique in the averagecase if lim/n→∞ Pr/G=G(n,p) [G unknown sign φ ⇔ G contains a kclique] = 1 where G = G(n,p) is the ErdosRényi random graph with p (= p(n)) the exact threshold such that Pr[G(n,p) has a kclique] = 1/2. We are interested in the question: How many variables are required to define averagecase kclique in firstorder logic? Here we consider firstorder 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 SpringerVerlag.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

