-2
$\begingroup$

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.

$\endgroup$
10
  • 3
    $\begingroup$ I'm not sure this is an appropriate question for MO, but even if it is you only waited 24 hours to get an answer on math.SE. You should wait at least a couple of weeks. $\endgroup$ Feb 18, 2014 at 20:38
  • 2
    $\begingroup$ @Andy: You are demanding a lot of patience. Experience taught me that when you don't get an answer at MSE - or even a comment - after a couple of hours, you will only get one by sheer accident. $\endgroup$ Feb 18, 2014 at 22:40
  • $\begingroup$ @Andy: And please give me a slight hint: Is my question inappropriate because it is trivial or because it is nonsensical? (I cannot guess from the close votes, but maybe I would learn something from this information.) $\endgroup$ Feb 18, 2014 at 22:46
  • 6
    $\begingroup$ @Hans: I have not voted to close, but your question feels a bit "stone soup-y" to me. You are pitching out a very soft idea and asking whether and how it can be mathematically formalized. Like almost every very soft idea: certainly, yes it can be mathematically formalized, in several different ways. Whether or which of these formalizations will be preferable to you is hard to know in advance, so your are essentially asking for people to create some mathematics until you say you like it. This site is designed for more focused questions than that. $\endgroup$ Feb 18, 2014 at 22:51
  • $\begingroup$ I think that Pete's comment describes the issues with this question perfectly. And I'm sorry if you feel like we demand patience here, but that is the generally agreed upon policy. If you don't get a good answer on math.se, you should think about how to improve your question to get one rather than just copying it here. $\endgroup$ Feb 18, 2014 at 22:51

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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