An optimal lower bound on the number of variables for graph identification |
| |
Authors: | Jin-Yi Cai Martin Fürer Neil Immerman |
| |
Institution: | (1) Computer Science Dept., Princeton University, 08540 Princeton, NJ;(2) Computer Science Dept., University of Massachusetts, 01003 Amherst, MA;(3) Computer Science Dept., Pennsylvania State University, 16802 University Park, PA |
| |
Abstract: | In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308. |
| |
Keywords: | 03 B 10 05 C 60 05 C 85 |
本文献已被 SpringerLink 等数据库收录! |
|