2013/07/16 by Junichiro Fukuyama, Fukuyama, Junichiro
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.1 #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.1307.4308
arXiv admin note: substantial text overlap with arXiv:1305.3218
openalex publication_date 2013/07/16 · arxiv created 2013/09/08 · arxiv updated 2013/09/10 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In 1985, Razborov discovered a proof that the monotone circuit complexity of the clique problem is super-polynomial. Alon and Boppana improved the result into exponential lower bound exp(Ω(n / log n)1/3)) of a monotone circuit C to compute cliques of size (1/4) (n / log n)2/3, where n is the number of vertices in a graph. Both proofs are based on the method of approximations and Erdos and Rado's sunflower lemma. There has been an interest in further generalization of the proof scheme. In this paper, we present a new approach to show the exponential monotone complexity. Unlike the standard method, it dynamically constructs a counter example: Assuming a monotone circuit C of sub-exponential size to compute k-cliques c, an algorithm finds an edge set t containing no c in the disjunctive normal form constructed at the root of C. We call such t a shift. The proof shows that t is disjoint from an edge set z whose removal leaves no k-cliques. We explore the set theoretical nature of computation by Boolean circuits. We develop a theory by finding topological properties of the Hamming space 2[n] where [n]=1, 2, ..., n. A structural theorem is presented, which is closely related to the sunflower lemma and claims a stronger statement in most cases. The theory lays the foundation of the above shift method. It also shows the existence of a sunflower with small core in a family of sets, which is not an obvious consequence of the sunflower lemma. Lastly, we point out that the new methodology has potential to apply to a general circuit computing cliques due to the dynamic selection of t and z, and to improve the Alon-Boppana bound exp(Ω(n / log n)1/3)).