Oleg Pikhurko ; Joel Spencer ; Oleg Verbitsky
-
Decomposable graphs and definitions with no quantifier alternation
dmtcs:3423 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3423
Decomposable graphs and definitions with no quantifier alternationConference paper
Authors: Oleg Pikhurko 1; Joel Spencer 2; Oleg Verbitsky 3
0000-0002-9524-1901##NULL##0000-0002-9524-1901
Oleg Pikhurko;Joel Spencer;Oleg Verbitsky
1 Department of Mathematical Sciences
2 Courant Institute of Mathematical Sciences [New York]
3 Institut fur Informatik
Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism in terms of the adjacency and the equality relations. Let D0(G) be a variant of D(G) where we do not allow quantifier alternations in Φ. Using large graphs decomposable in complement-connected components by a short sequence of serial and parallel decompositions, we show examples of G on n vertices with D0(G)≤2log∗n+O(1). On the other hand, we prove a lower bound D0(G)≥log∗n−log∗log∗n−O(1) for all G. Here log∗n is equal to the minimum number of iterations of the binary logarithm needed to bring n below 1.
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: descriptive complexity of graphs,first order logic,Ehrenfeucht game on graphs,graph decompositions,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Syeda Abida Ejaz;Mubashir Aziz;Mohamed Fawzy Ramadan;Ammara Fayyaz;Muhammad Sajjad Bilal, 2023, Pharmacophore-Based Virtual Screening and In-Silico Explorations of Biomolecules (Curcumin Derivatives) of Curcuma longa as Potential Lead Inhibitors of ERBB and VEGFR-2 for the Treatment of Colorectal Cancer, Molecules, 28, 10, pp. 4044, 10.3390/molecules28104044, https://doi.org/10.3390/molecules28104044.