isomorphic to G. For example: ``Is there an
edge from vertex 1 to vertex 2?'' is not a graph property, but ``Does
the graph have one edge?'' is. Some graph properties are symmetric,
such as ``Is the graph complete?'' Others exhibit symmetry in a
different sense than that of Definition 2.5.1, such as ``Does
the graph contain a vertex of degree 5?''
A non-trivial graph property is one that is false for some graph, and true for some graph. If adding an edge to a graph can not make a property fail the graph property is called monotone. Examples of well-known monotone graph properties are whether a graph is connected, acyclic, non-bipartite, complete, non-planar, or non-k-colorable. Nonmonotone graph properties include whether the graph is a tree and k-regularity.
Conjecture 3.1.1 is known to be true for graphs whose number of vertices is a prime power [14].
The conjecture makes monotone graph properties an appealing target for study in the quantum oracle model. We attained asymptotically tight lower bounds for evasive symmetric functions in Chapter 2. In non-trivial monotone graph properties we have a class of functions, conjectured to be evasive, that exhibit a kind of symmetry due to their invariance under relabeling of vertices. We hope that Ambainis' Theorem can provide us with asymptotically tight lower bounds for non-trivial monotone graph properties as they did for nonconstant symmetric functions.