Natural constructions (not depending on parameters) [closed]

Question

Consider graph clusterings as a prototypical example of (logical) constructions.

Let a clustering of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$.

I am looking for a way to define the notion of a "natural graph clustering". By a natural graph clustering I mean - informally - a clustering that can be uniformly defined for all graphs by a formula or an algorithm that doesn't depend on arbitrary parameters.

Intended examples of natural graph clusterings include

1. the connected components of a graph
2. the cliques of a graph
3. the maximal cliques of a graph
4. the orbits of the automorphism group of a graph

Intended counter-examples (while depending on parameters) include

1. cliques up to size $k$
2. quasi-cliques, i.e. a fraction $\theta$ of the edges can be missing

But what does it mean formally to "depend on a parameter"? E.g. counter-example (1) can easily be defined by a formula not containing any numeric parameter $k$ but instead an appropriate number of quantifiers.

(How) can the notion of "dependence on a parameter" be formalized?

The problem is: every number (or other distinguished set) occuring in a formula as a parameter can either be eliminated by an appropriate number of quantifiers or by a definite description.

An intuitive feeling remains that the counter-examples are less "natural" than the intended examples.

So what does distinguish the intended examples from the counter-examples?

Or is it a chimera, and such a distinction cannot be made?

[Appendix]

There are unclear cases for which I have no intuition whether they should count as examples or counter-examples:

1. connected induced subgraphs with more edges than vertices (a kind of quasi-clique)

---

^{I also tried to ask this question at MSE.}

Answer 1

I guess somehow we should rule out spurious ways to depend on parameter, such as

"a graph is $k$-cliqueish if either $k=1$ and the graph is connected, or $k\ge 2$ and the graph has a clique of size $k$".

Here is attempt (not constructive and not really canonical). Fix a first-order language $L$ containing some basic arithmetic so we can use parameters from $\mathbb N$.

Definition 1. For an $L$-definable function $f$ with domain $\mathbb N$, define the complexity $C(f)$ to be the shortest definition of $f$ in $L$.

Definition 2. For functions $f^*$ and $f$ with domain $\mathbb N$, we say that $f$ is an improvement of $f^*$ if $C(f)\le C(f^*)$, and for all but finitely many $n$, $f(n)=f^*(n)$.

Definition 3. A set $S$ depends on a parameter if there exists an injective $f$ with domain $\mathbb N$, such that for all improvements $g$ of $f$, there is an $n$ with $f(n)=g(n)=S$. In this case we say the value of the parameter can be $n$.

Theorem(?) The collection $S$ of graphs having a clique of size 5 does depend on a parameter (which can have the value 5), since a natural definition of "clique of size $k$" cannot be shortened and modified in such a way as to still be correct for almost all $k$, and at the same time remove $S$ from the range.