Counting graphs whose vertex induced subgraphs are members of a fixed set - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:20:12Z http://mathoverflow.net/feeds/question/20135 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20135/counting-graphs-whose-vertex-induced-subgraphs-are-members-of-a-fixed-set Counting graphs whose vertex induced subgraphs are members of a fixed set Travis Service 2010-04-02T03:35:19Z 2010-04-02T13:13:52Z <p>Let $C$ be the class of graphs of girth $g$ or more. $C$ can alternatively be characterized as: $G \in C$ iff each of $G$'s vertex induced subgraphs on less than $g$ nodes is a forest.</p> <p>We can generalize this as follows. Let $A$ be a class of graphs. Define $C_A$ as: $G \in C_A(k)$ iff all of $G$'s vertex induced subgraphs on less than $k$ nodes are members of $A$.</p> <p>A natural question is then:</p> <p>Given a class of graphs $A$ and integer $k$ how many graphs on $n$ vertices are in $C_A(k)$? Or more generally, can one bound the number of graphs on $n$ vertices in $C_A(k)$ given $k$ and $A$?</p> <p>The particular situation I am interested in is where we allow $k$ to be a function of the number of vertices in the graph. That is let $C_A(f(n))$ (where $f(n) &lt; n$) be defined as: $G \in C_A(f(n))$ iff all of $G$'s vertex induced subgraphs on less than $f(n)$ vertices are members of $A$ (where $n$ is the number of vertices in $G$).</p> <p>My actual question is: Is there a class of graphs $A$ such that the number of graphs in $A$ on $n$ vertices is $2^{O(g(n))}$ but the number of graphs on $n$ vertices in $C_A(c \cdot g^{-1}(n))$ is $2^{\omega(g(n))}$, for some constant $c$? Stated another way: all vertex induced subgraphs on $n$ vertices of a graph on $g(n)$ vertices in $C_A(c \cdot g^{-1}(n))$ are in $A$.</p> <p>In particular I am interested in the situation where $g(n) = n\log{n}$ and $A$ is hereditary (every vertex induced subgraph of a graph in $A$ is also in $A$). This implies that all vertex induced subgraphs of size $n$ or less of a graph on $n\log{n}$ vertices in $C_A(g^{-1}(n))$ are in $A$.</p> <p>EDIT: My motivation for this question is that it is related to an open problem on implicit graph representation in: S. Kannan, M. Naor, S. Rudich, Implicit Representation of Graphs, SIAM Journal on Discrete Mathematics 5, 596-603, 1992</p>