Is it possible that a finite combinatorial problem may admit a closed form solution, and for it to be impossible in practice to prove the validity of this solution? I'm not sure if a rigorous definition can be given to the notion of a finite combinatorial problem, but I mean problems of the following nature:

Given a set finite set $X$, which may or may not have additional structure, enumerate the number of elements in $X$ which satisfy some constraint defined in terms of the primitives of set theory and the additional structure of $X$.

Since we are speaking of closed form solutions, we are really interested in families of finite combinatorial problems, parametrized by $\mathbb{N}$, which scale in some natural way with increasing $n\in \mathbb{N}$. I'm not sure if the notion of a closed form solution can be given a rigorous definition, but I mean something along the lines of the following definition from Graham, Knuth, and Patashnik's Concrete Mathematics:

An expression for a quantity $f\left(n\right)$ is in closed form if we can compute it using at most a fixed number of "well known" standard operations, independent of $n$.

I understand that this question is vague and open ended, so I would be happy with answers or partial answers to any of the following subquestions.

  1. Are there examples of finite combinatorial problems for which empirical evidence suggests there is a closed form solution, but for which significant effort has failed to produce any proofs of the validity of this solution?

  2. Is it possible to give a rigorous axiomatization that captures the notion of of a finite combinatorial problem that working combinatorialists work with, and then bring to bear ideas along the lines of Godel's Theorems and Turing's work on the Halting Problem to produce an existence proof for such families of combinatorial problems? Can any rigorous formulation be given to the notion of a family of finite combinatorial problems scaling naturally with $n\in\mathbb{N}$?

  3. Are there examples of finite combinatorial problems which display a kind of regularity for large $n$. That is, are there any known families of finite combinatorial problems that scale naturally with $n\in\mathbb{N}$, such that $f\left(n\right)$, the answer to the problem associated to $n$, behaves haphazardly for small $n$, but can then be given in terms of a closed form expression for sufficiently large $n$? Is there anything to suggest that difficult combinatorial problems that have been studied, but for which little is known, may display this kind of regularity?

  4. Finally, are there any results in mathematical logic, set theory, or proof theory of which I am unaware, that render my question trivial or foolish?

I would appreciate any help with this question that can be given. As someone with a decent background in combinatorics, but no deep knowledge of logic or set theory, I don't know where to begin with this.

Edit:(In response to a comment of Qiaochu Yuan) $n$ need not be the size of $X$. I hope this example should clarify what I'm trying to get at. Consider the problem of enumerating the permutations of the elements of a finite set $X$ of cardinality $n$. This problem may be cast as the following problem.

Enumerate the elements of $X^n$, $\left(x_0,\ldots ,x_{n-1}\right)$, for which $x_i = x_j$ if and only if $i = j$. The problem has solution $n!$, which may or may not be considered closed, depending on what you mean by "well known" in Knuth's definition. The answer to this problem is dependent only on the size of $X$, not on any interpretation of what the elements might be. In a sense, the problems of this manner could be said to scale naturally with $n$. Part of my question is to provide a rigorous definition of what I mean by scale naturally.

  • $\begingroup$ Is n here supposed to be the size of X? Aren't you disallowing any questions whose answer is a function f(n) which is larger than n? $\endgroup$ – Qiaochu Yuan Feb 25 '11 at 22:05
  • $\begingroup$ @Qiaochu: I have added a response to your comment to the body of the post. $\endgroup$ – Albert Steppi Feb 25 '11 at 22:44

There's some work on complexity of combinatorial counting of objects definable in Monadic Second Order Logic (MSOL).

For example, you can define "X is an independent set of G" using MSOL. Time to count number of independent sets is independent of size of the graph for family of graphs of bounded tree width. For independent sets it is independent for family of bounded clique width, and one of Makowksi's papers gives conditions beyond MSOL which allow tractability with bounded clique width.

See page 8 of Makowski/Godlin's Graph Polynomials: From Recursive Definitions to Subset Expansion Formulas for examples of properties definable using MSOL on a graph.

There's a number of papers from Makowski and co-authors on this line of work, for instance his student's Definability of Combinatorial Functions and their Linear Recurrence Relations.

  • $\begingroup$ This is exactly the sort of thing I am looking for. $\endgroup$ – Albert Steppi Feb 26 '11 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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