Date: Friday, April 05, 2013
Location: 3941 BBB/CSE (10:30 AM to 11:30 AM)
Title: An Optimal Lower Bound on the Number of Variables for Graph Identification
Abstract: In this paper we show that Omega(n) variables are needed for first-order logic with counting to identify graphs on n vertices. The k-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 because n variables obviously suffice to identify graphs on n vertices.
Speaker: Aaron Snook
Institution: U-M
Event Organizer: martinjs
| 
