<foo> simply produces <foo>in the text).
<URL: http://somewhere.tld/ >,
and it will be automatically made into a link.
(Do not try any other way or it might count as an attempt to spam.)mailto: URI,
e.g. mailto:my.email@somewhere.tld,
if you do not have a genuine Web site).
jonas (2006-03-26T00:45:20Z)
I've thought on this and I belive that the same construction I described above works for n = 7 instead of n = 8 too, if the property is that a K_4 component exists. There's only one minor variation in the strategy, namely that if you get three paths of length 1 in the first stage, you mustn't choose the middle one.
One correction about the general case though: the upper bound on the complexity of the property I described is not n - O(sqrt(n)) as I wrote in the last comment but n^2 - O(n).
jonas (2006-03-20T19:12:25Z)
This is a nice problem.
I thought of this a bit, and I've found a non-trivial graph property with less than n(n - 1)/2 complexity. Here it is.
Let's take n = 8, and let's say that the property P is true iff one of the graph's connected components is a 5 point large complete graph.
Let me show why the complexity of this is 27 (one less than n(n - 1)/2). Firstly, we can assume that we ask an unordered pair of vertices only once. Then, our strategy hash three steps. Firstly, ask for the pairs {0, 1}, {1, 2}, …, {n - 2, n - 1}, {n - 1, 0}.
Select one of the longest continuous paths of edges we've found. It's easy to prove that if P is true then all vertices of such a path must be in the K_5 component. Then, select one of those vertices, let's say p, and ask for all the edges starting from p. If P is true, than the connected points are exactly the points of the K_5 component, except for the point p. If the number of neighbours isn't equal to 4, than P is false. Otherwise, we ask for every edge of which at least one of the endpoints is a neighbour of p. Clearly this is enough to determine whether p and its neighbours are all connected together but not with any other points.
Finally, we have asked only at most two of the three edges between the other three points, so that's at most 27 edge in total.
Similarly, it's easy to construct a non-maximally-complex graph property for any n that states that the graph has a large complete graph as a component. The size of the complete component is n - O(sqrt(n)); and the complexity will be a different n - O(sqrt(n)).
Les Halles (2006-03-15T11:25:48Z)
C'est la honte publique ta réponse ! Mais j'ai quand même essayé de corriger ma proposition. En essayant le truc du graphe en scorpion j'ai cru que c'était basé sur le principe des tiroirs et en voyant ton exemple de cliques et anticliques je me suis dit qu'il fallait peut être symétriser.
Mais tous les essais du genre prendre des couples (i, j) ayant une certaine propriété, par exemple 2n + 1 couples différents, interroger le graphe pour voir si c'est des arêtes ou des anti-arêtes, appliquer le principe des tiroirs (par exemple on a n + 1 arêtes ou anti-arêtes) avec une propriété quelconque des graphes (être un arbre, contenir un cycle). Bref, tout ça ne m'a conduit qu'à des propriétés étant vraies pour tout graphe.
Ruxor (2006-03-13T14:28:10Z)
« Le graphe est un arbre » ne peut pas se décider en moins que le nombre maximum de questions, il me semble : si on connaît l'existence ou non d'une arête entre chaque paire de sommets moins une, et s'il est possible que ce soit un arbre, cette dernière paire peut *toujours* faire la différence entre arbre et pas arbre. Donc ce n'est certainement pas linéaire. D'ailleurs, demande-toi, comment poserais-tu les questions pour détecter si un graphe est un arbre ?
Chatelet (2006-03-13T12:40:46Z)
Le graphe est un arbre ou le graphe est un couplage ou de manière plus générale toute propriété qui utilise d'une façon ou d'une autre le principe des tiroirs (appliqué au nombre de noeuds) devrait être linéaire non ?
Ruxor (2006-03-11T18:44:29Z)
Oui, tu as raison, 3n−6 a l'air plus que hautement suspect, ou, vraisemblablement, c'est juste le temps pour trouver la queue du scorpion si elle existe et pas pour vérifier ensuite. La complexité totale doit être 6n+O(1).
Nick (2006-03-11T18:35:58Z)
Si on me dit 1, 2 et 3 sont la queue d'un eventuel scorpion, la propriete reste a tester. Il me faut tester tous les voisins de 1, tous ceux de 2 et ceux de 3. Ca fait deja, n-1+n-2+n-3=3n-6 questions. J'ai pas bien compris la definition du scorpion, ou bien il faut au moins 3n-6 operations en connaissant la queue? Ca me parrait difficile d'arriver a decouvrir la propriete en ce nombre d'operations sans fixer la queue.