An optimal lower bound on the number of variables for graph identification
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 612-617
- https://doi.org/10.1109/sfcs.1989.63543
Abstract
It is shown that Omega (n) variables are needed for first-order logic with counting to identify graphs on n vertices. This settles a long-standing open problem. The lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that three variables suffice to identify all graphs of color class size 3, and two variables suffice to identify almost all graphs. The lower bound is optimal up to multiplication by a constant because n variables obviously suffice to identify graphs on n vertices.<>Keywords
This publication has 10 references indexed in Scilit:
- Describing Graphs: A First-Order Approach to Graph CanonizationPublished by Springer Nature ,1990
- Definability with bounded number of bound variablesInformation and Computation, 1989
- On uniformity within NC/sup 1/Published by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Recursive construction for 3-regular expandersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Expressibility as a Complexity Measure: Results and DirectionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- Upper and lower bounds for first order expressibilityJournal of Computer and System Sciences, 1982
- Number of quantifiers is better than number of tape cellsJournal of Computer and System Sciences, 1981
- An application of games to the completeness problem for formalized theoriesFundamenta Mathematicae, 1960