Return to 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.}

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.}