|
ever from you, as from a burning torch,
flying around are patches of the fire,
going up in flames, do you set yourself free,
or do you just abandon all of your desires ?
will only flurry remain? soot, smoke and tar?
or will down the ashes, there will be diamond
shimmering in darkness as the morning star?
Here is the original "Popiol i diament" of
Cyprian Norwid, from his
collection " Behind Closed Courtains".
Another, more literal translation
is here.
Free, sometimes as free as above, translations from slavic languagesare are incidentally
my hobby, particularly when it comes to songs of
Buwat Okujava
but I am also fascinated by the difficulties with the automated
translations.
Below are classroom Graffiti's conjectures about cata-condensed benzenoids
run Little Red Riding Hood style. All needed definitions can be found in
Pony Express and in particular all conjectures here
with exception of the last one, are about benzenoids. Concerning the last
one, see Ashes and Diamonds II, conj. 1035.
Red Burton style amounts to learning a subject by working on conjectures
of Graffiti, though unlike in the Texas style, the students are welcome to
read texbooks or freely discuss the problems with instructors.
The Little Red Riding Hood style requires in addition providing the "simplest"
counterexample to each round of conjectures after the round
terminates (provided that it is the case). The details are in [F].
Hex graph of every benzenoid can be
defined by a subset of a N by N hex board. The simplicity of benzenoids is
determined first by the size the smallest hex board needed to place the benzenoid
on it, and then lexicographically by listing elements of the defining subset.
Hexagons of the hexboard are numbered by consecutive integers proceeding from left
to right and from the bottom up. Thus benzene is represented by
the code (1,{0}), with the first element of the pair being N, and the second -
the set of indices of hexagons.
Napthalene is represented by (2,{0,1}) and penanthrene by (2,{0,1,3}).
The next simplest benzenoid corresponding to 2 by 2 hex board is not
cata-condensed (the hex graph, by definition, must be a tree), so the next eligible
example is anthracene - (3,{0,1,3}).
The goal of the course is not only to discuss conjectures of Graffiti, but
also to discuss the so-called intelligent programs, and "AI debate", though limited
primarily to claims concerning conjecture-making programs. Each time an opportunity
will arise as it was the case with the very first round (in class), I will use conjectures
to
illustrate some of these issues. Apart from this, as it was the case with all previous
versions
of "Written on the Wall", this file is used as a list of memos to myself and as
an illustrations
of the performance of Graffiti. In particular the class participants will be aware of
most of the problems and difficulties which will come up in the process.
The version started with 38 invariants derived from G and H(G) - the hex graph
of G. All invariants are very simple with exception of the spectral measure.
The starting example was of course benzene and after a few rounds with
fairly easy counterexamples the program made these three conjectures:
Upper Bounds for h - the number of hexagons of benzenoid G
1.1 h ≤ -1 + MID of G,
where MID ( minimum independent dominating
set) is
defined as the number of vertices of a minimum independent set I, such every vertex of G
is either in I or is adjacent to an element of I.
MID is computed by an aproximation algorithm which
starting with an empty set I, expands it by a vertex of maximum degree of the graph
induced by G \ N(I), where N(X) is the set of vertices which are either in X or are adjecent
to an element of X. This allows for various interpretations of
conjectures involving this concept and if needed we will discuss it further.
1.2 h ≤ half of the sum of reciprocal of the degree sequence of G.
1.3 h ≤ twice the independence number of H(G).
The problem is to find a simplest counterexample to either of the two conjectures
or to prove that both of them true. If it is the case, one have to prove or
disprove that for every cata-condensed benzenoid we have equality either in 1.1, 1.2 or
1.3
This is a natural interpretation of the end-of-the-round conjectures of Dalmatian version
and it may be easier to understand why, after the following
definition:. A system of inequalities L ≤ Ri is a
quasi-equality if all inequalities of the system are true and if for each x (in
the domain of L ) there is k such that Rk(x) is
well defined and L(x) = Rk(x).
The definition basically amounts to saying that L is the minimum of Ri's.
Dalmatian version attempts to make conjectures until the system of inequalities becomes a
quasi-equality (over the domain being the set of
objects in the database of the program,) and the natural interpretation of this conjecture
is of course, that the quasi-equality is valid for the set of all objects under
consideration, [F], which in our case is the class of all cata-condensed benzenoids.
As an example, let us consider the bound "independence number of H(G)", from the
very first conjecture of the current run (with benzene as the only example.)
Accoording to our rules the interpretation of the end-of-the-round, the conjecture in
question is not
(i) h ≤ the independence number of H(G).
but,
(ii) h = the independence number of H(G).
Before we ran this version, we discussed a few other rounds in one of which Graffiti
correctly conjectured that for cata-condensed benzenoids
h = 1 + v3/2
,
where v3 is the number of vertices of degree 3 of G.
Monna
conjectured that independence of cata-condensed benzenoids is 2h + 1 . Ryan
independentely
found the first of these two formulae and posted the simple solutions to the kba
mailing list.
After adding yesterday (9. 10. 03) to the database of Graffiti a counterexample to conjecture
1.2, the program responded with the round:
2.1 h ≤ 4 * (MID of H)
2.2 h ≤ - 1 + MID of G.
2.3 h ≤ twice the sum of reciprocals of of the spectral measure of H(G).
2.4 h ≤ twice the independence number of H(G).
Conjectures that were already proved before are
displayed in bold characters and conjectures which are repetitions of conjectures from
previous rounds are shown in italics.
Greg and Ryan seem to have similar proofs of 2.2 going by induction on deletion of an
endpoint of H(G) (if you could write longer proofs in html form, it would be preferable
to posting them to the list).
Here is a simpler argument for 2.2: let N(D) be
D + {y in G: y is adjacent to an element of D}
Since
the maximum degree of G is 3, |N(D)| - the number of elements of N(D) - has at most 4|D|
elements.
Hence 2.2. follows because cata-condensed benzenoid with h hexagons have 4h + 2 vertices.
Conjecture 2.4 is true because H(G) is a tree and for bipartite graphs the independence
number is
at least half of the number vertices. Note that going strictly by rules one had to prove
at
the very least,
that there are no counterexamples to 1.3 (which is the same as 2.2), simpler than the
simplest counterexample to 1.2.
Ideally a proof of an inquality should include characterization of all cases of
equality.
We still have not done it for
2.2 and 2.4
Soon after the class Dillon and Ryan noticed that 2.1 is also true and that this can be
shown by the same argument as 2.2. We can use this argument because the maximum degree of
trees of
cata-condensed benzenoids is 3, (otherwise H(G) would contain triangles.)
In the same posting to kba list, Ryan made conjecture that
h ≤ - 1 + MID of G + h3,
where h3 is the number of vertices of degree 3 of the hex graph of G.
The argument for 2.2 can be generalized as follows: If X is a MID of an n-vertex
graph G with maximum degree d and if X contains at most m vertices of degree d
in the graph induced by X then
(i) n ≤ d*m + (d-1) (|X|- m),
Every vertex of degree 3 of hex-tree contributes 1 to the count of L of endpoints
(leaves) of this tree, i.e., L = h3 + 2.
Combining this with the above formula we get
(ii) h ≤ MID - 1 - 1/4 * h3
which is a partial corroboration of Ryan's conjecture. The question is whether 1/4th
can be replaced by a better constant c. The constant c can not however be greater than
1/2 as one can see from the example of a tree with degree sequence (3,3,1,1,1,1); in
particular this tree is a counterexample to original Ryan's conjecture.
Discussing these problems in class today (9.15.03) Dillon noticed that not every tree
of maximum degree 3 is a hex-tree of a benzenoid. The question is which trees are
of this form.
Ryan provided detailed proof of (ii) along with discussion of related
problems and a new conjecture which would imply that constant 1/4 in (ii) could be replaced
by
1/2. Let D be a minimum independent dominating set of G, and let V3 be the number
of vertices of degree 3 in H(G). Let us call a vertex of G over-dominated if it has
two or more neighbors in D.
Conjecture: G has a MID D with the number of over-dominated vertices greater or
equal to V3.
Nice aspect of Ryan's conjecture is that (as his previous conjecture) it is quite bold,
apart from being well motivated. Hopefully bold enough to materialize in another
counterexample which will further illuminate the situation. The point is that conjectures
get proven or refuted, theorems - generalized or simplified, and only
examples are forever.
Concerning the constant in (ii), I would think that it can be replaced by 1/2, because
probably a weaker statement than Ryan's conjecture (though involving the same idea)
should be enough to prove it.
After including (hardly minimal, which could be a torture) counterexample to
2.3 and after two more rounds Graffiti finished with a round of correct
conjectures. The first of these two rounds consisted of 6 conjectures,
four out of which were correct, and the results of the second round were similar.
Note that the ratio of correct conjectures was higher than on the average in the previous
(eighties and nineties) versions of Graffiti, some of which were dozens or even
hundreds of
examples. This is quite
counter-intuitive, but in spite of reporting similar observations from the beginning
of work on Graffiti some individuals propose as research projects to
use larger databases of
examples to increase the ratio of correct conjectures. As a wise man Huang Po said:
"a wise man believes what he sees, not what he knows".
One of the final (bingo) conjectures was
(iii) h ≤ 1 + 1/2 *(the number of vertices of maximum degree).
After that bingo was easy, since benzene was the only example for which we do not
have equality in (iii). An old procedure of Graffiti makes conjectures of the form I = c,
where I is an invariant and c is constant, but it should also make conjectures of
the form T = f, where T is a term and f a function with relatively few (wrt to the number
of objects) values. In general, one should have also conjectures of this form where
f has restricted range as for example integers or rationals.
I is a n invariant
If instead of the number of vertices of maximum degree we had invariant
g3 = the number of vertices of degree 3, the program probably would make
this conjecture
h = 1 + 1/2 * g3,
but, it is difficult to be sure, because, conjectures depend on ordering of
invariants and some other factors.
The formula (iii) came up as one of the first conjecture when I was preparing
"Ashes and Diamonds" for its present classroom use and it proved to be
exceptionally useful in debugging of this version. Most of the problems originated
from improper encoding of examples. Apart from speeding up arbitrary computer programs,
Graffiti-like programs can be also used as debuggers and even as correctors (of certain
programs). This possibility was marginally mentioned in my perennial [A], but lately more
and more, I consider this possibility quite practical. In general, conjectures of
Graffiti can be used to detect errors in data ( a considerable problem at least
in the genome project.)
Typing coding sequences of counterxamples it is easy to make a mistake and
detecting errors in data because of resulting conjectures was happening all the
time, when I started to use coding sequences in previous educational versions
of Graffiti. Nevertheless, it was not the first time when I presented a documented
evidence of the possibilty of using Graffiti as a debugger.
Discussing the stability patterns on DIMACS meeting in '98, I made on their basis
a conjecture of my own, namely
that one of the 78 atom, IPR fullerenes which Graffiti was using as an example of stable
molecule appears to be less stable than the other four IPR fullerenes with the same number
of atoms. I presented my conjecture publicly, on purpose, to subject Graffiti to a blind test. As it
turned out later, two out of the ten "stable" examples used by Graffiti were never produced
in bulk and one of these two examples turned out to be "singled out" by the program as
possibly less stable.
Let d be the number of vertices in MID
3.3.1 d ≤ 2 * |H(G)|
3.3.2 d ≤ number of vertices of maximum degree
3.3.3 d ≤ maximum of spectral measure of G
3.3.4 d ≤ mean eccentricity of G.
The mute database had 3 bounds at this point, |G|, the independence of G, and the diameter
of G. The last conjecture may be considered as a hint for 3.3.4. The examples at this point
were benzene, phenantrene and triphenilene. 9. 22. 03.
As I promised I asked Doug about the status of the problem what benzenoids
with h hexagons minimize their matching number.
From: Doug Klein
Yes this is open, and I think that it is hard. Actually it likely
becomes harder if one takes the related problem "among all benzenoids with n
sites find those which minimize their matching number" or also "among all
benzenoids with h hexagons find those which have u=0". Actually I think
that when making comparisons for different values of m at constant u, it is
a delicate matter in making stability comparisons. Really I think that u
(more so than m) is the arbiter of "stability".
Doug
From kleind@tamug.tamu.edu Tue Sep 23 19:50:52 2003
Date: Tue, 23 Sep 2003 14:48:54 -0500
You asked about determining which h-ring benzenoids have minimum
matching number m. A relevant article which I have stumbled across since I
last e-mailed you is: C. R. Si & L.-Z Shang, "When a Polyhex is Kekulean", MatCh 49 (2003)
117-126. Here Kekulean means u=0, and they allow a little beyond benzenoids, and they
provide necessary & sufficient conditions. But I am not sure that the
conditions are suitably "simple", since their condition involves the
examination of every bipartitioning via a certain type of edge-cutting of
the polyhex.
It also occurs to me that in Harary et al, J. Math. Chem. 6 (1993)
295 there is a straight-forward but perhaps not especially elegant algorithm
to determine whether any selected edge e is in any possible perfect matching
of a finite graph G. If this is done for every edge e leading into any
selected vertex, then the answer being no for every such edge is necessary &
sufficient for G to have no Kekule structure (i.e., to have u>0).
Doug
After Ryan's findings and conjectures I added to the program the annihilation number
which is defined in
Ashes and Diamonds II.
The conjectures below are for arbitrary benzenoids.
4.1 the annihilation number of G = independence number of G.
4.2 the annihilation number of G = half of the number of edges of G.
4.3.1 the annihilation number of G ≤ half the number of edges of G
4.3.2 the annihilation number of G ≤ 1 + 2(freq of vertices of maximum degree) of
G.
Next Ryan proved in the class 4.4.1 and 4.4.2 below. 10. 1. '03. Much later (when someone
asked about it,) he sent an outline of his argument to be included here:
5.25. '05. " Both of these conjectures are true and follow from two facts. First,
the annihilation number of benzenoids, and indeed all graphs with only two different degrees,
is the floor of the minimum of (e/d) and (n-e/D); where e is number of edges, n is number of
vertices, d is minimum degree, and D is maximum degree. Since benzenoids have minimum degree
two and the annihilation number is at most e/d, conjecture 4.4.1 is true. Second, you can use the
fact that the number of degree two vertices is at most six less than the number of degree
three vertices, together with the fact that the annihilation number is at most n-e/D, to prove
conjecture 4.4.2." 5.25. '05.
4.4.1 the annihilation number of G ≤ half the number of edges of G
4.4.2 the annihilation number of G ≤ 1 + 2(freq of vertices of maximum degree)
of
G.
4.4.3the annihilation number of G ≤ 1 + the independence number of G.
4.5.1 the annihilation number of G ≤ half the number of edges of G
4.5.2 the annihilation number of G ≤ 1 + 2(freq of vertices of maximum degree)
of
G.
4.5.3the annihilation number of G ≤ MID of H(G) + diameter of G.
Perhaps more instructive than 4.5.3 are two of the five conjectures from the
mute database:
m4.5.1 the annihilation number of G ≤ the number of vertices minimum degree of G
m4.5.2 the annihilation number of G ≤ 2(MID of G)
10.7.03
6.1 the independence number of benzenoid G = cover number of G.
The simplest counterexample is (2,{0,1,2}). Let e(v) be the number of vertices at
even distance from v.
6.2. the independence number of benzenoid G = maximum of e(G).
A counterexample to this conjecture is an hourglass - two copies of a triangulene with base
3 (6h) with top hexagon being amalagamated ( so there are 11 hexagons alltogother)
I do not know whether it is the simplest counterexample
to this
conjecture.
6.3.1 the independence number of benzenoid G ≤ -1 + the depth
of the degree sequence of G.
The depth of the degree sequence is n - its residue.
6.3.2 the independence number of benzenoid G ≤ 1 + maximum of e(G).
The second conjecture is false - counterexamples include larger hourglasses.
For the first conjecture to appear on this list (at least at this stage) I had to remove
from the list of invariants the annihilation number. Graffiti made this conjecture in
a run with database of about 100 benzenoids (most of which were used in Pony
Express.) I think that 6.3.1 is similar to some of Ryan's results
about annihilation number.
12. 12. '03
The next and the last conjecture to celebrate the end of the semester is
is based on one example - adamantane - the simplest diamondoid:
the independence number of every diamondoid is equal to the chromatic
number of its complement.
References
[A] Program Accelerators
[F] S. Fajtlowicz, Toward Fully Automated Fragments of Graph Theory,
Graph Theory Notes of NY Academy of Sciences, XLII, 2002.
|