Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is an attempt to refine my previous question into something precise enough to admit a resolution.

Let $P\;$ be a graph property, let $T_n\left(P\;\right)$ be the set of isomorphism classes of graphs on $n$ vertices which satisfy $P\;$, and let $f\left(n\right) = \left|T_n\left(P\; \right)\right|$, the number of elements in $T_n\left(P\;\right)$. Is it possible for $f\left(n\right)$ to satisfy a simple recurrence $f\left(n\right)=\mathcal{R}\left(f\left(1\right),f\left(2\right),\ldots,f\left(n-1\right)\right)$, yet for it be an intractable problem to determine this recurrence given a formulation of $P\;$?

This problem as stated is trivial. Let $X$ be some collection of graphs for which $g\left(n\right)$, the number of graphs in $X$ with $n$ vertices, satisfies some simple recurrence. Then let $P\;$ be given as $x\in X$. In this case $P\;$ tells us nothing of how to find this recurrence. Is there some property in logic or set theory that identifies such examples? It seems that there should be some way to consider a large class of formulations of graph properties for which this question is not trivial, but at the moment I am too ignorant to formalize this notion.

Edit: (In response to Qiaochu's comment) I suspect that it doesn't matter too much what class of recurrences we consider. For now lets just consider linear recurrences with integer coefficients, $f\left(n\right)= \sum_{i=n-k}^{n-1}\alpha_{n-i} f\left(i\right)$, where $k$ is some constant. Then the problem I am interested in is whether or not there exists an algorithm which given a formula $\mathcal{F}$ describing a graph property $P\;$, outputs a proof that $f\left(n\right)=\left|T_n\left(P\right)\right|$ satisfies a linear recurrence with integer coefficients and produces the recurrence in all cases in which $f\left(n\right)$ satisfies such a recurrence, or otherwise runs forever. Of course, we must consider some restricted class of such formulas $\mathcal{F}$, but as I stated above I am unsure at the moment how to define such a class.

Edit: I have come to believe that much of the above is irrelevant, and that my line of reasoning has been confused. This is because everything seems to hang upon the class of graph properties (actually formula describing graph properties) we consider, and I have left this completely open. It now seems apparent that we should consider finitely encoded formula describing graph properties which:

  1. Provide all of the information which is needed to check if a given graph possesses the property.

  2. Describe something which is intrinsic to graphs.

I believe that the latter condition can be formalized in some way, but I am not sure of this. If a formula describing a graph property does not satisfy the first condition, then I do not see how it could be possible to enumerate the graphs which have $n$ vertices and possess the property, given only the formula. Allowing graph properties which do not satisfy the second condition allows us to encode a wide class of difficult mathematical problems into our framework. For example, we could let our property be described by

$X$ is a graph for which the number of edges equals the $kth$ digit in the decimal expansion for the Euler-Mascheroni constant $\lambda$, where $k$ is the number of vertices of $X$.

If $\lambda$ is rational, then one could say that $f\left(n\right)$, which for each $n\in \mathbb{N}$, returns the number of such graphs with $n$ vertices, has a simple closed form solution. It is however not known whether or not $\lambda$ is rational, and this could conceivably be an undecidable proposition.

I cannot be sure, but I suspect that if we limit the graph properties under consideration in this way, then this question is no longer terribly interesting. Perhaps someone may have something interesting to say on this topic, but I don't think I'm going to think about this any longer.

share|improve this question
What is a simple recurrence? What is a tractable problem? (Is this meant in the computability sense or in the complexity sense, e.g. polynomial time?) What does it mean to determine the recurrence? –  Qiaochu Yuan Feb 26 '11 at 16:08
add comment

1 Answer

up vote 2 down vote accepted

A somewhat similar situation is where the graph minor theorem puts you in. If you take any minor-closed family of graphs, you know that it has a finite list of forbidden minors, but presumably it's hard to find "in general" (I don't know if anyone tried to make that precise, but it's conceivable that in some setting it's not computable). Given the list of forbidden minors, you have an $O(n^3)$ algorithm for testing membership in the family. Whether that gives you an efficient enumeration algorithm, I'm not sure; but the resulting situation is that there is an $O(n^3)$ algorithm, but it might be hard to find.

share|improve this answer
This seems to get at the heart of what I've been asking about. A quick search for the graph minor theorem turned up a lot of seemingly relevant material. –  Albert Steppi Feb 26 '11 at 19:08
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.