graphs, codes and such

2011-10-23T23:34:00.000-07:00

2011-08-09T12:59:00.000-07:00

A slightly simpler proof of Kostochka's lemma. It avoids the need for one extra lemma.

For a collection of maximum cliques Q in a graph G, let X_Q be the
intersection graph of Q.

Lemma. If Q is a collection of maximum cliques in a graph G with
\omega(G) > 2/3 (\Delta(G) + 1) such that X_Q is connected, then \cap
Q \neq \emptyset.

Proof. Suppose not and choose a counterexample Q := {Q_1, ..., Q_r}
minimizing r.

Let A be a noncutvertex in X_Q and B a neighbor of A. Put Z := Q -
{A}. Then X_Z is connected and hence by minimality of r, \cap Z \neq
\emptyset. In particular, |\cup Z| \leq \Delta(G) + 1.

Hence |\cup Q| \leq |\cup Z| + |A - B| \leq 2(\Delta(G) + 1) -
\omega(G) < 2\omega(G). This contradicts Hajnal's lemma.

2011-07-19T21:30:00.000-07:00

Conjecture 14 from my recent paper is false by some pretty easy examples.

However, i still think Conjecture 13 (which Conjecture 14 implies) is true.

2011-04-27T10:06:00.000-07:00


static void Main()
{
  Func<int, int> w = t => (t + (t >> 31)) ^ (t >> 31);
  Func<int, int> r = t => -(-t >> 31);
  Func<bool> z = () => { Thread.Sleep(20); 
                         return true; };
  Func<string, bool> a = s => { Console.Write(s); 
                                return true; };
  Func<int, int, bool> b = null;
  b = (n, k) => k <= n && (Console.ForegroundColor = 
                (ConsoleColor)(r(k & (n - k)) + 1)) 
                != null && a("8") && b(n, k + 1);
  Func<int, bool> c = null;
  c = n => a("".PadLeft(40 - w(n) / 2, ' ')) && 
           (b(w(n), 0) || true) && z() && a("\n") && 
           (w(n) < 75 || n < 0) && c(n + 1);
  Func<bool> d = null;
  c(0);
  d = () => (c(-75) || true) && d(); 
  d();
}

2011-03-14T18:30:00.000-07:00

See more at Interesting Graphs.

2010-12-30T09:32:00.001-08:00

The only 7-mule containing a K_7 minus an edge.

2010-12-06T09:02:00.000-08:00

i proved this recently. It would be interesting to explicitly construct a sequence of graphs showing that t_0 does not exist instead of relying on P \neq NP.

2010-12-03T11:23:00.000-08:00

Church numerals in C#.


public static class Lambda
{
    public delegate Turtle Turtle(Turtle turtle);

    static Lambda()
    {
        ID = x => x;

        T = y => n => y;
        F = y => n => n;
        and = p => q => p(q)(F);
        or = p => q => p(T)(q);
        not = p => y => n => p(n)(y);
        xor = p => q => p(not(q))(q);

        zero = s => z => z;
        one = s => z => s(z);
        succ = n => s => z => s(n(s)(z));
        iszero = n => n(x => F)(T);

        add = m => n => m(succ)(n);
        mul = m => n => m(z => add(n)(z))(zero);
        pow = b => exp => exp(mul(b))(one);

        pred = n => s => z => n(u => v => v(u(s)))(T(z))(one);
        sub = m => n => n(pred)(m);

        min = m => n => sub(m)(sub(m)(n));
        max = m => n => add(n)(sub(m)(n));
        leq = m => n => iszero(sub(m)(n));
        lt = m => n => not(leq(n)(m));
        eq = m => n => and(leq(m)(n))(leq(n)(m));

        make_pair = x => y => f => f(x)(y);
        make_triple = x => y => z => f => f(x)(y)(z);

        div = m => n => ID(bb => build => m(build)(bb)
              (cur => go => sofar => sofar))
              (make_triple(m)(T)(zero))
              (t => t(cur => go => sofar => and(go)
              (leq(n)(cur))
              (make_triple(sub(cur)(n))(T)(succ(sofar)))
              (make_triple(cur)(F)(sofar))));
        mod = m => n => ID(bb => build => m(build)(bb)
             (cur => go => cur))(make_pair(m)(T))
             (p => p(cur => go => and(go)
             (leq(n)(cur))
             (make_pair(sub(cur)(n))(T))
             (make_pair(cur)(F))));
    }

    public static readonly Turtle ID;
    public static readonly Turtle T;
    public static readonly Turtle F;
    public static readonly Turtle and;
    public static readonly Turtle or;
    public static readonly Turtle not;
    public static readonly Turtle xor;
    public static readonly Turtle zero;
    public static readonly Turtle one;
    public static readonly Turtle succ;
    public static readonly Turtle iszero;
    public static readonly Turtle add;
    public static readonly Turtle mul;
    public static readonly Turtle pow;
    public static readonly Turtle factorial;
    public static readonly Turtle div;
    public static readonly Turtle mod;
    public static readonly Turtle pred;
    public static readonly Turtle sub;
    public static readonly Turtle min;
    public static readonly Turtle max;
    public static readonly Turtle leq;
    public static readonly Turtle lt;
    public static readonly Turtle eq;
    public static readonly Turtle make_pair;
    public static readonly Turtle make_triple;

    public static int ToInt(this Turtle turtle)
    {
        if (turtle.IsZero())
            return 0;

        return 1 + pred(turtle).ToInt();
    }

    public static Turtle ToTurtle(this int i)
    {
        if (i == 0)
            return zero;

        return succ((i - 1).ToTurtle());
    }

    public static bool IsZero(this Turtle turtle)
    {
        return iszero(turtle)(Lambda.T)(Lambda.F) == Lambda.T;
    }

    public static bool ToBool(this Turtle turtle)
    {
        return !turtle.IsZero();
    }
}

2010-12-02T18:38:00.000-08:00

Are you currently the type of God that would claim that True sits to the left of False?
Are you currently the type of God that would claim that False sits to the left of Random?
Are you currently the type of God that would claim that True sits to the left of Random?

2010-12-02T17:49:00.000-08:00

Are you currently a truth-teller if and only if True sits to the left of False?
Are you currently a truth-teller if and only if False sits to the left of Random?
Are you currently a truth-teller if and only if True sits to the left of Random?

2010-03-10T17:17:00.000-08:00

Here is a much simpler proof of a lemma of Kostochka that i translated from Russian and used.

Lemma. Let G be a graph with omega > 2/3 (Delta + 1). If Q is a collection of maximum cliques in G such that X_Q is connected, then \cap Q \neq \emptyset.

Proof. Assume not and let Q = {Q_1, ..., Q_r} be a bad collection of maximum cliques with r minimal. Then r \geq 3 and X_Q is complete since it is connected and transitive. Put Z = Q - {Q_1}. Then X_Z is connected and hence by minimality \cup Z contains a universal vertex. In particular |\cup Z| \leq Delta + 1. Thus

|\cup Q| \leq |Q_1 - Q_2| + |\cup Z| \leq 2(Delta + 1) - omega < 2omega.

But then Hajnal gives a contradiction.

2009-11-09T09:13:00.000-08:00

The harder hardest logic puzzle where Random can randomly say 'ja', 'da' or remain silent cannot be solved in two questions. This is not too difficult to prove.

Let the gods be arranged ABC. When the gods are in arrangement W and a question P is posed to god A we write P_W(A) for the response (an element of {y,n,s} -- (y)es, (n)o, (s)ilent).

Claim. It is not possible to solve the version of the hardest logic puzzle ever where Random randomly remains silent, answers `yes' or answers `no' in two questions.

Proof. Assume (to reach a contradiction) that it is possible, then there is a procedure for solving it in two questions. Let Q be the first question that is asked in this procedure and without loss of generality assume it is addressed to god A. There are 4 possible arrangements of T, F and R such that A \neq R and only 3 possible responses. Hence there must be two different arrangements U and V with A \neq R such that Q_U(A) = Q_V(A). Let X = RTF, Y = RFT. Then we can choose Random's responses so that Q_U(A) = Q_V(A) = Q_X(A) = Q_Y(A) = D. But then after asking Q and receiving response D all we know is that the arrangement is one of U, V, X, Y. Thus the second question must distinguish 4 possibilities with one question which is impossible.

2008-03-28T16:03:00.000-07:00

2008-01-18T20:19:00.000-08:00

i haven't existed since i last existed here.

rlavwfv

2007-10-20T20:02:00.000-07:00

Working on using the following theorem to prove the full Borodin-Kostochka conjecture.

Theorem: If G contains a doubly critical edge and satisfies chi >= Delta >= 6, then G contains a K_Delta.

So, the Borodin-Kostochka conjecture (and more) holds for graphs containing a doubly critical edge. This allows one to try to find a doubly critical edge instead of trying to find a big clique. This works to give a new proof of Brooks' theorem, but it gets intricate for the Borodin-Kostochka condition; however, there is a lot of room to play and it looks very promising (this all uses a decomposition theorem of Lovasz -- actually a modification of it by Catlin).

nqsiq

dxbpgril

2007-08-31T20:09:00.001-07:00

One can only flourish among people who share the identical ideas and the identical will; i have no one -- that is my sickness.

whafedp

2007-08-27T19:00:00.000-07:00

Infinitely many primes.

Here is a game.

I've picked a number between 0 and N and your goal is to find out what the number is by asking me yes/no questions.

(1) There are N+1 possible numbers i could have picked, so any plan that you devise will require you to ask at least lg(N + 1) questions in the worst case.
(2) There is a plan that you can follow that will require at most ceiling(lg(N + 1)) questions -- a binary search will do.

Assume (to reach a contradiction) that there are finitely many primes p_1, ..., p_M.

(3) N = p_1^k_1 * ... * p_M^k_M for some choice of non-negative integers k_1, ..., k_M.

(4) Since the smallest prime is 2, we have k_i <= lg(N) for all i. Consider the following plan.

Use (2) to determine k_1 in at most ceiling(lg(k_1)) <= ceiling(lg(lg(N))) questions.
Use (2) to determine k_2 in at most ceiling(lg(k_2)) <= ceiling(lg(lg(N))) questions
. . . .

We have determined k_1, ..., k_M in at most M * ceiling(lg(lg(N))) questions. But this determines N completely! So we have determined N in at most M * ceiling(lg(lg(N))) <= M * (1 + lg(lg(N))) = M * (lg(2) + lg(lg(N))) = M * (lg(2 * lg(N))) = lg((2 * lg(N))^M) questions.

(5) You can win the game in at most lg((2 * lg(N))^M) questions for any N. By (5) and (1), for all N we have lg((2 * lg(N))^M) >= lg(N + 1), killing the lg's gives

(2 * lg(N))^M >= N + 1

This holds for all N, so in particular for N >= 2^(2^(2^(2^M - 1) / M) / 2). This gives

(2 * lg(2^(2^(2^(2^M - 1) / M) / 2)))^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
(2 * 2^(2^(2^M - 1) / M) / 2)^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
(2^(2^(2^M - 1) / M))^M >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
2^(2^(2^M - 1)) >= 2^(2^(2^(2^M - 1) / M) / 2) + 1
2^(2^(2^M - 1)) > 2^(2^(2^(2^M - 1) / M) / 2)
2^(2^M - 1) > 2^(2^(2^M - 1) / M) / 2
2^((2^M - 1) + 1) > 2^(2^(2^M - 1) / M)
2^(2^M) > 2^(2^(2^M - 1) / M)
2^M > 2^(2^M - 1) / M

M > 2^(2^M - M - 1)

Which is false for all positive integers. This contradiction completes the proof.

solkkj

uaugw

boiagmz

2007-08-04T17:58:00.000-07:00

.NET and Nintendo on iMac. As i told Cerny, everything can be simulated.

hjukhova

2007-08-04T17:35:00.000-07:00

Here is the magic squares searcher running on my iMac under vmware.

2007-07-23T19:38:00.000-07:00

Made a new version of the magic squares searcher. It can be found here

http://landon314.brinkster.net/MagicSearcher.msi

and here

http://landon314.brinkster.net/MagicSearcher.zip

This version has an improved interface with more options and a much faster search for squares in the hourglass configuration.

2007-07-20T19:10:00.000-07:00

Help find a 3x3 magic square of squares. Here is a winforms interface to the C++ magic squares code. The MagicLibrary assembly can be easily used in other applications to search for a magic square of squares. The source is included.

http://landon314.brinkster.net/MagicSearcher.zip

It currently only runs on Windows. i wanted to make OSX and Linux versions, but Mono does not support mixed mode assemblies! (MagicLibrary is a C++/CLI wrapper of unmanaged search code that i wrote a while back that uses Victor Shoup's NTL).

The search so far is documented in the following.

http://landon314.brinkster.net/magicSearch.pdf

2007-07-08T18:54:00.001-07:00

Tell me this:

why does it happen that at the very, yes, at the very moments
when I am most capable of feeling every refinement of all that
is "sublime and beautiful," it would, as though of design, happen
to me not only to feel but to do such ugly things, such that ...
Well, in short, actions that all, perhaps, commit; but which,
as though purposely, occurred to me at the very time when I
was most conscious that they ought not to be committed. The
more conscious I was of goodness and of all that was "sublime
and beautiful," the more deeply I sank into my mire and the more
ready I was to sink in it altogether.

The following morning, I lay acutely conscious that the previous
day I had committed a loathsome action again, that what was
done could never be undone, and secretly, inwardly gnawing,
gnashing at myself for it, tearing and consuming myself till at
last the bitterness turned into a sort of shameful accursed sweetness.

2007-07-06T19:28:00.000-07:00

The Man gathers them,
they who would not have their face touch the void,
they who would relinquish the status of unique being.
To what end?
The machine,
the faceless monster,
scalable unchecked ego at the push of a button.

2007-06-29T19:35:00.001-07:00

It's all about the title.

2007-05-07T21:29:00.001-07:00

Dizziness or fainting may occur upon standing.

2007-04-25T20:07:00.000-07:00

Give me any tool and i will build ridiculously complicated castles.

2007-04-08T10:38:00.001-07:00

Formalism. Formalism!
Give us our Formalism,
for our minds are weak,
and our vision poor.

2007-04-02T17:42:00.000-07:00

Theorem: No purported proof of this statement is understandable.

Proof: Assume (to reach a contradiction) that the statement is false. Then there is a purported proof R of the statement that is understandable. Since R is understandable, R is sound. Thus R is a proof of the statement and hence the statement is true. This contradicts our assumption that the statement was false.

Thus, either the proof just given was unsound or you didn't understand it (or both).

The proof was surely sound. Hence you didn't understand it. Moron!

2007-04-01T11:58:00.000-07:00

Nobody can prove this statement.

2007-02-24T13:59:00.001-08:00

Claim: Every natural number can be expressed using only the words: 'the', 'least', 'natural', 'number', 'which', 'cannot', 'be', 'expressed', 'using', 'only', 'words'.

Proof: Assume (to reach a contradiction) that this is not the case. Then there is a least natural number which cannot be expressed thusly. Consider the expression "The least natural number which cannot be expressed using only the words: 'the', 'least', 'natural', 'number', 'which', 'cannot', 'be', 'expressed', 'using', 'only', 'words'." We have expressed said number thusly. Contradiction.

Claim: Every natural number can be expressed using only precisely two copies of each word amongst: 'the', 'least', 'natural', 'number', 'which', 'cannot', 'be', 'expressed', 'using', 'only', 'precisely', 'two', 'copies', 'of, 'each', 'word', 'amongst'.

Proof: Assume (to reach a contradiction) that this is not the case. Then there is a least natural number which cannot be expressed thusly. Consider the expression "The least natural number which cannot be expressed using only precisely two copies of each word amongst: 'the', 'least', 'natural', 'number', 'which', 'cannot', 'be', 'expressed', 'using', 'only', 'precisely', 'two', 'copies', 'of, 'each', 'word', 'amongst'." We have expressed said number thusly. Contradiction.

In particular, there are at most 34! natural numbers.

2007-01-28T12:44:00.000-08:00

Now with tabs and saving. Also, added a sample tool plug-in written in VB (it contracts edges).

2007-01-25T18:44:00.000-08:00

2007-01-16T18:02:00.000-08:00

Some sort of ridiculous stomach and head pain for the the two days (not sure if they are related).

Some sort of ridiculous ulcer or insect or quarter in there.

2007-01-07T21:21:00.000-08:00

What does a singleton friendly frame property look like?

2006-12-31T17:59:00.000-08:00

just made those ribs with jen (that is:

).

the following define a semi-group with unsolvable word problem.

2006-12-26T12:49:00.000-08:00

1) the only way we have to value one idea over another is through predictive ability
2) there are infintely many ways that could be 'the way it is' that all give the same answers for all data we can ever collect(infintely many models which describe all the data).
3) since the only way we can come to value one model over another is through one making better predictions than another, there is no way we can choose between this infinitude of 'perfect' models
4) we cannot know 'the way it is'
5) we feel compelled to answer questions of the form 'does X exist?'
6) since we cannot know 'the way it is', we cannot answer these questions in the strong sense, all we can do is give an answer from within the currently best model we have.
7) hence, under this interpretation of 'exists', the existence of something is man-dependent.

In objection to (1), we could claim some sort of preference for 'simplicity' of the model. This may be a good practical
consideration(a mathematically simpler model is easier to work with and milk predictions from), but we are not justified
in making the leap from 'simpler models are preferable for practical reasons' to 'simpler models describe the way it is'.

A thought experiment:

Assume mankind has reached a point in history where it has 'perfect' models of the universe (where 'perfect' means something like 'makes the most accurate possible predictions'). Say we have 'perfect models' M1, M2, M3, ...

The 'particles' in M1 are infinitely divisible (that is, M1 is a 'continuous model').
The 'particles' in M2 are not (that is, M2 is a 'discrete model').

Jones asks Smith, "is the universe continuous?"

Smith believes M1, so he says "yes!"
Jones believes M2, so he says "no way!"

who is correct? there is no argument, it seems to be a matter of faith.//

We aren't there yet. Could we ever know that we were there? How could we ever know that we weren't missing some piece of
data? Perhaps 'the way it is' changes in some complicated fashion every 100,000 years or so, making our models obsolete.
We really can't know that we are done taking data. So we won't ever need to have faith in one model over another. We can
always be in the state of 'I don't know which one is better, but I am actively collecting data in hopes of finding out, or
at least refuting one of them'.

2006-12-23T14:50:00.000-08:00

Can now export to TeX.

2006-12-23T09:44:00.000-08:00

Sick again, what's the deal? Added undo/redo to playground last night.

2006-12-19T16:27:00.000-08:00

Sick at home today. In the Graph Playground, made the tools in the toolbox into plugins. The plugin code files are located and then compiled at runtime. Used anonymous method magic to make it slick.

2006-12-13T01:56:00.000-08:00

Labels and property grid.

2006-12-10T00:21:00.000-08:00

Working on that.

2006-11-20T22:05:00.000-08:00

Little Paolo and Miriam are neighbors. Today was a half day at school, so they've gone down to the river behind their houses to skip rocks and catch tadpoles. Both have confused ideas running through their heads from Mrs. Appleton's discussion of natural selection in their 6th grade class this week. You see, Mrs. Appleton doesn't really understand it completely herself, so her presentation of the material tends to be a bit off. No matter, it gets the kids thinking about things they would never learn at home - both are having a religious upbringing(although not in the same religion). When Miriam catches her first tadpole, she holds it in her hand with a perplexed look on her face - you can tell she is really thinking hard. She brings it over to Paolo.

Miriam: Paolo, do you think this tadpole came to be how it is because of natural selection over a long period of time?
Paolo: Well, Mrs. Appleton says that everything came to be that way. But, at Sunday school we learned that the tadpole was just designed the way it is and put here.
Miriam: We learned that too. Could Mrs. Appleton be wrong? She is the teacher. She knows everything. How could she be wrong? How do we tell which is correct?

Remembering his lessons at Sunday school, Paolo devises a plan to convince Miriam. He suggests she should put the tadpole back in the water so that it doesn't die and while she is doing that takes off his watch and places it in the rocks. As she comes back, he points,

Paolo: Look at that!
Miriam: What is it? Looks like a watch.
Paolo: Lets forget that it is a watch for a second and just imagine we found it here and picked it up just like the tadpole.
Miriam: Ok...
Paolo: Lets open it up. Look at all these gears and other gadgets in here. Isn't it complicated?
Miriam: I don't know how it works, whoever made it must have been smart.
Paolo: Why do you think someone made it? It came about by natural selection over a long period of time.
Miriam: What? No way. That is way to complicated to have come about like that. Someone definately made it.
Paolo: And the tadpole? What if we could look inside it? How does it get energy to swim around, what mechanisms drive it?
Miriam: I don't know. It seems less complicated that the watch, but still pretty complicated.
Paolo: Well then, how about your eyes. Do you know how those work?
Miriam: Yeah! We learned about that in class, there are some sort of cones or something. It was very complicated I remember.
Paolo: Right, do you think your eyes came about by natural selection?
Miriam: Oh I see. Just like the watch. No they didn't, they are way too complicated, so someone must have made them.
Paolo: Exactly, so I don't buy into this natural selection business.
Miriam: Me either, lets skip some rocks.

They skip rocks for awhile, Miriam is much better at it(its all in those supple wrists). She is thinking about the implications of their conversation and concludes that the God she learns about in Sunday school must be the one who made everything - just as she had been taught, Mrs. Appleton is wrong.

Miriam: Paolo, so God made everything then, right?
Paolo: Well, I'd say that something made everything. What is God? I know we go to different churches, so your God is different than mine.
Miriam: Mine is the real one.
Paolo: How do you know that?
Miriam: It must be, what Mrs. Appleton was saying in opposition to my beliefs was wrong. Therefore my beliefs were right.
Paolo: But I can use the same argument. What Mrs. Appleton was saying in opposition to my beliefs was wrong. Therefore my beliefs were right. So, both our beliefs are right?
Miriam: Oh, hmm... I guess that just because her's were wrong doesn't mean mine were right. Nevermind.
Paolo: Right. We have to give some sort of positive argument for why our beliefs are correct, not just knock down others beliefs.

Now Paolo is concocting another plan to convince Miriam. He will do it just as his father convinced him.

Paolo: Miriam, do you think a being can be outside of time?
Miriam: What do you mean?
Paolo: Like, can there be someone who is sitting over there on those rocks thinking, but time is not passing for him?
Miriam: How could he be thinking if time was not passing for him? The question doesn't make any sense.
Paolo: Exactly, so you'd agree then that you can't have a being outside of time?
Miriam: Sure, I would have never thought otherwise.
Paolo: Ok, so we agree that someone made everything in the world, right?
Miriam: Yes, it is too complicated to not have been made.
Paolo: Good. So as He was making the world, time was passing, right?
Miriam: Why is it a He?
Paolo: Well, we don't know it is or isn't. Might not have any sex at all. But we just need some way to refer to it, so is 'He' ok?
Miriam: Ok, yeah. And yeah, time was passing of course.

Paolo: Why do you think He made the world?
Miriam: Hmm... I guess it's like a dollhouse. For entertainment?
Paolo: That's the only thing I can come up with too. Except, I'm not entertained by a dollhouse. The dolls don't have a mind of their own.
Miriam: I'm kinda getting bored of my dollhouse. The dolls never surprise me, since I invent all their situations. It would be fun if they had a mind of their own.
Paolo: Do you think we have a mind of our own?
Miriam: Of course.
Paolo: Why of course? Could we not just be dolls and He is moving us around?
Miriam: I find that hard to believe. Anyway, as you were saying before, He would get bored pretty quick if we didn't have minds of our own.
Paolo: He sure would. So we must have minds of our own.
Miriam: Yeah, so what? I already thought that.
Paolo: I'm just trying to get us a common base of assumptions to work from. Do you think everything that happens in the world was determined when He made it?
Miriam: Of course, He is God, He knows everything.
Paolo: But wait, just a minute ago you told me that of course we have minds of our own. If everything is already determined, then how do we have minds of our own? If at the beginning, He already knew the choices we would make at any given time in the future, and he set it all up to happen that way, then how do we have minds of our own?
Miriam: Uh, well. Ok. Those both can't be true. I feel sure that I have a mind of my own, so things can't be pre-determined.
Paolo: And since He set up the world, the outcome of the original setup must have been uncertain. He couldn't have known exactly what would happen in the future. Also, as time gets further and further away from the beginning, He would be less and less able to predict what would happen.
Miriam: Ok, I can agree with all that.

Paolo: So, since time was passing when He made the world, uncertainty was creeping in while he was in the process of making it.
Miriam: Ok, so if he had made it really really slowly, then he would have a hard time setting it up like he wanted.
Paolo: Exactly, you are all over this. And just like the watchmaker, He would strive to make His creation as close to his vision of it as possible.
Miriam: So He had to make it fast. Really fast. As fast as possible.
Paolo: How could He do it fast? The world is big and He can only move so fast since He is not outside of time.
Miriam: He wouldn't need to move fast if He was everywhere at once.
Paolo: That's true, but He wouldn't be able to place His creations if He was taking up all the space.
Miriam: Well, He doesn't have to be a big blob taking up all the space, He could just have parts that stretched out to everywhere.
Paolo: Ok, like a bunch of arms or something?
Miriam: Yah. So we need Him to have tons of arms.
Paolo: How many arms?
Miriam: As many as possible?
Paolo: Is there a limit? What if they just kept getting thinner and thinner. Then He could have some thick arms and then arms that get thinner and thinner forever.
Miriam: Can they really get thinner and thinner forever? That seems like magic. Isn't there like a smallest distance?
Paolo: Well, if there wasn't a smallest distance then I could keep moving forward forever but never move an inch. That doesn't fit my intuition of the world at all. My dad told me that in mathematics they invent these things called the 'real numbers' as a useful abstraction to model the world. He says this whole no smallest distance idea comes from people taking this model as literal truth - they forget that it was a mere model.
Miriam: I agree, there must be a smallest distance.
Paolo: Right then, so there is a minimal thickness to His arms. If we wanted Him to have as many as possible, the we should have them all be this minimal thickness.
Miriam: So He has loads of thin arms. They would need to be long too, so that He could work on distant places in the world.
Paolo: How many arms does your God have?
Miriam: Well, Jesus is God. So two I guess. That can't be right. But Mrs. Appleton isn't right either...
Paolo: My God has tons of thin arms. Our church is right across the street from yours.
Miriam: Really? Why do people believe in my God?
Paolo: History I guess, people have been believing in your God for a very long time. It is entrenched.
Miriam: But, He only has two arms! It's obviously not correct. What is your God called?
Paolo: The Flying Spaghetti Monster.

2006-11-16T11:53:00.000-08:00

Bounce for me.

2006-11-11T10:53:00.000-08:00

Finished writing up solutions to the hardest logic puzzle ever:

A simple solution to the hardest logic puzzle ever (with Brian)

Still working on a formal system to make the proofs symbolic (i.e trivial). Just need restricted indexicals (ranging over True/False/Random) and a couple new truth values (Explode and Indifferent) to deal with the self-reference.

2006-10-08T19:14:00.000-07:00

Formalism. Formalism!
Give us our Formalism,
for our minds are weak,
and our vision poor.

2006-10-01T19:16:00.000-07:00

Yesterday i proved that the a counterexample to Reed's conjecture has two connected complement. The proof is written in my notebook, will TeX it when i get a chance.

This followed immediately from the following improvement of the graph associations theorem.

If I_1, ..., I_m are disjoint independent sets in G, then at least one of the following holds

1) \chi(G) \leq \frac{1}{2} (\omega(G) + \Delta(G) + 2)
2) \chi(G) \leq \frac{1}{2}(\omega(G) + n - \sum_{j=1}^m |I_j| + 2m - 2)

So, in other words, the graph associations bound can be improved by 1/2 for counterexamples to Reed's conjecture.

2006-10-01T17:16:00.000-07:00

Gods: { A, B, C} = { Mr. True, Mr. False, Mr. Random }

Given a question Q, let E(Q) be the question
"If I asked you Q, would you say ja?"

Lemma 1: If we ask Mr. True or Mr. False E(Q), a
response of ja means the true answer to Q is yes
and a response of da means the true answer to Q is
no.

Proof: Both a double positive and a
double negative make a positive.

Lemma 2: If we have determined that a particular
God is not Mr. Random and have two questions
remaining, we can determine the identities of all the
Gods.

Proof: Without loss of generality, assume that A is
not Mr. Random. Ask A the following two questions:

(1) E("Is A Mr. True?"),
(2) E("Is B Mr. Random?").

By Lemma 1, A's response to (1) will determine A's
identity and then A's response to (2) will determine
the identity of both B and C.

Using these Lemmas, we can make quick work
of the puzzle.

Ask B the question E("Is A Mr. Random?"). If B says ja,
then either B is Mr. Random or A is Mr. Random (by Lemma 1).
Hence C is not Mr. Random. If B says da, then either B is
Mr. Random or A is not Mr. Random (by Lemma 1).
Hence A is not Mr. Random. Whence B's response to our
first question determines that a particular God is not
Mr. Random. Now Lemma 2 finishes the job.

2006-09-19T22:16:00.000-07:00

Got the magic squares building on the imac. Linking NTL with GMP (a bug in Apple's linker implementation made a little patch to GMP necessary [the patch just tricks the linker and thus isn't ideal]) gave a good speedup. Running now.

Going to San Francisco tomorrow for the rest of the week. Andrew Bird show on friday night.

2006-07-29T21:17:00.000-07:00

i spend most of my time thinking in the corner. i don't like to captitalize 'i' or the first letter of my name -- a form of self deprecation. i studied math in grad school and then left towards the end purely for spite.

2006-07-29T21:10:00.000-07:00

2006-07-23T10:54:00.000-07:00

Was able to show that the complement of a counterexample to Reed's conjecture has minimal degree at least 6. The proof suggests a general method.

Also, improved the bound on the maximal degree of a counterexample from

<= n - sqrt( n + 7 ), to

<= n - sqrt( n + 10 ).

2006-07-22T08:57:00.000-07:00

#include "stdafx.h"
#include "Square.h"
#include "GaussianInteger.h"
#include "time.h"

using namespace std;
using namespace NTL;

int MIN_PRIME;
int MAX_PRIME;
int MAX_POWER;
int MAX_FACTORS;
int MIN_NUMBER_OF_SQUARES;

int* prime;
int* primesOneModFour;
int spot;
int primesOneModFourCount;

GaussianInteger*** sumOfSquaresRepresentationTable = 0;

fstream outFile;

int _tmain(int argc, _TCHAR* argv[]) // MAX_PRIME MAX_POWER MAX_FACTORS MIN_NUMBER_OF_SQUARES
{
MIN_PRIME = 0;
MAX_PRIME = 100000;
MAX_POWER = 2*1 + 1;
MAX_FACTORS = 5;
MIN_NUMBER_OF_SQUARES = 6;
readArguments( argc, argv );

prime = new int[MAX_PRIME];
primesOneModFour = new int[MAX_PRIME];

srand( (unsigned) time(NULL) );
mt_init();

ostringstream stringStream;
stringStream << "log" << MIN_PRIME << "-" << MAX_PRIME << "-" << MAX_POWER << "-" << MAX_FACTORS << "-" << MIN_NUMBER_OF_SQUARES << ".txt";
outFile.open( stringStream.str().c_str(), fstream::in | fstream::out | fstream::ate );

int i;
int j;

bool bPreviousWorkSucked = true;
Factor* factorList = new Factor[MAX_FACTORS];
factorList[0].power = 2 * ( MAX_POWER / 2 );
for(i = 1; i < MAX_FACTORS; i++ )
factorList[i].power = 2 * ( MAX_POWER / 2 );

outFile.seekg( 0, fstream::end );
int length = outFile.tellg();
if( length > 0 )
{
cout << "Some work has already been done on this range, processing log file...\n";
outFile << "\nSome work has already been done on this range, processing log file...\n";

outFile.seekg( -2000, fstream::end );
string line[100];
int count = 0;
while( getline( outFile, line[count] ) )
{
// cout << "line(" << count << "): " << line[count] << "\n";
if( line[count].find( ":" ) != string::npos )
count++;
}

if( count >= 1 )
{

string temp = line[count - 1];
int index;
int start = 0;
for( i = 0; i < MAX_FACTORS; i++ )
{
index = temp.find( "^", start );
if( index == string::npos )
break;
stringstream tempStringStream;
tempStringStream << temp.substr( start, index - start );
tempStringStream >> factorList[i].prime;
// cout << "\nstreamed this in: " << factorList[i].prime << " from this: " << tempStringStream.str() << "\n";
start = index + 1;

start = temp.find( ".", start ) + 1;
if( index == string::npos )
break;
}
if( i == MAX_FACTORS )
bPreviousWorkSucked = false;
}
}

outFile.clear();
outFile.close();

outFile.open( stringStream.str().c_str(), fstream::out | fstream::app );

cout << "Generating all primes less than " << MAX_PRIME << ".\n";
outFile << "Generating all primes less than " << MAX_PRIME << ".\n";
generatePrimes();
cout << "Precomputing sum of squares decompositions for prime powers up to exponent " << MAX_POWER - 1 << ".\n";
outFile << "Precomputing sum of squares decompositions for prime powers up to exponent " << MAX_POWER - 1 << ".\n";
setupSumOfSquaresTable();

if( !bPreviousWorkSucked )
{
for( i = 0; i < MAX_FACTORS; i++ )
{
for( j = 0; j < primesOneModFourCount; j++ )
if( factorList[i].prime == primesOneModFour[j] )
{
factorList[i].prime = j;
break;
}
if( j == primesOneModFourCount )
{
cout << "\nfailed to find prime: " << factorList[i].prime << "\n";
bPreviousWorkSucked = true;
break;
}
}
}

if( bPreviousWorkSucked )
{
factorList[0].prime = 0;
for(i = 1; i < MAX_FACTORS; i++ )
factorList[i].prime = factorList[i - 1].prime + 1;
}

int numberOfFactors = MAX_FACTORS;
ZZ M;
ZZ tempA;
ZZ tempB;
bool done = false;
bool carrying;
GaussianInteger* decompositionList = 0;
bool foundSomething = false;
while( !done )
{
if( !done )
{
for( i = 0; i < numberOfFactors - 1; i++ )
{
cout << primesOneModFour[factorList[i].prime] << "^" << factorList[i].power << ".";
outFile << primesOneModFour[factorList[i].prime] << "^" << factorList[i].power << ".";
}
cout << primesOneModFour[factorList[i].prime] << "^" << factorList[i].power << ":\n";
outFile << primesOneModFour[factorList[i].prime] << "^" << factorList[i].power << ":\n";

cout << "Computing all sum of squares decompositions... ";
outFile << "Computing all sum of squares decompositions... ";

int numberOfDecompositions = getAllDecompositions( factorList, numberOfFactors, decompositionList );

if( spot != numberOfDecompositions )
{
cout << "I mispredicted the number of sum of squares decompositions!\n";
outFile << "I mispredicted the number of sum of squares decompositions!\n";
break;
}

cout << "found " << numberOfDecompositions << " decompositions.\n";
outFile << "found " << numberOfDecompositions << " decompositions.\n";

ZZ middle;
middle = numericallValueOfFactorList( factorList, numberOfFactors );
M = 3 * middle;

cout << "Building all possible magic squares...\n";
outFile << "Building all possible magic squares...\n";
ZZ square[9]; // 0 1 2
// 3 4 5
// 6 7 8
square[4] = middle;

for( i = 0; i < numberOfDecompositions; i++ )
{
for(j = i + 1; j < numberOfDecompositions; j++ )
{
// skew
square[6] = decompositionList[i].a;
square[2] = decompositionList[i].b;
square[7] = decompositionList[j].a;
square[1] = decompositionList[j].b;
square[0] = M - ( square[1] + square[2] );
square[8] = M - ( square[0] + square[4] );
square[5] = M - ( square[8] + square[2] );
square[3] = M - ( square[5] + square[4] );
if( isMagic( square ) )
{
int nSquares = numberOfSquares( square );
if( nSquares >= MIN_NUMBER_OF_SQUARES )
{
foundSomething = true;
cout << "found something (" << nSquares << "):\n";
outFile << "found something (" << nSquares << "):\n";
printSquare( square );
}
}

square[6] = decompositionList[i].a;
square[2] = decompositionList[i].b;
square[7] = decompositionList[j].b;
square[1] = decompositionList[j].a;
square[0] = M - ( square[1] + square[2] );
square[8] = M - ( square[0] + square[4] );
square[5] = M - ( square[8] + square[2] );
square[3] = M - ( square[5] + square[4] );
if( isMagic( square ) )
{
int nSquares = numberOfSquares( square );
if( nSquares >= MIN_NUMBER_OF_SQUARES )
{
foundSomething = true;
cout << "found something[b] (" << nSquares << "):\n";
outFile << "found something[b] (" << nSquares << "):\n";
printSquare( square );
}
}

square[6] = decompositionList[j].a;
square[2] = decompositionList[j].b;
square[7] = decompositionList[i].a;
square[1] = decompositionList[i].b;
square[0] = M - ( square[1] + square[2] );
square[8] = M - ( square[0] + square[4] );
square[5] = M - ( square[8] + square[2] );
square[3] = M - ( square[5] + square[4] );
if( isMagic( square ) )
{
int nSquares = numberOfSquares( square );
if( nSquares >= MIN_NUMBER_OF_SQUARES )
{
foundSomething = true;
cout << "found something[c] (" << nSquares << "):\n";
outFile << "found something[c] (" << nSquares << "):\n";
printSquare( square );
}
}

square[6] = decompositionList[j].a;
square[2] = decompositionList[j].b;
square[7] = decompositionList[i].b;
square[1] = decompositionList[i].a;
square[0] = M - ( square[1] + square[2] );
square[8] = M - ( square[0] + square[4] );
square[5] = M - ( square[8] + square[2] );
square[3] = M - ( square[5] + square[4] );
if( isMagic( square ) )
{
int nSquares = numberOfSquares( square );
if( nSquares >= MIN_NUMBER_OF_SQUARES )
{
foundSomething = true;
cout << "found something[d] (" << nSquares << "):\n";
outFile << "found something[d] (" << nSquares << "):\n";
printSquare( square );
}
}

// 0 1 2
// 3 4 5
// 6 7 8

// plus
square[3] = decompositionList[i].a;
square[5] = decompositionList[i].b;
square[7] = decompositionList[j].a;
square[1] = decompositionList[j].b;
square[0] = ( square[7] + square[5] ) / 2;
square[2] = ( square[3] + square[7] ) / 2;
square[6] = ( square[1] + square[5] ) / 2;
square[8] = ( square[3] + square[1] ) / 2;
if( isMagic( square ) )
{
int nSquares = numberOfSquares( square );
if( nSquares >= MIN_NUMBER_OF_SQUARES )
{
foundSomething = true;
cout << "found something[e] (" << nSquares << "):\n";
outFile << "found something[e] (" << nSquares << "):\n";
printSquare( square );
}
}

// X
square[0] = decompositionList[i].a;
square[8] = decompositionList[i].b;
square[6] = decompositionList[j].a;
square[2] = decompositionList[j].b;
square[1] = M - ( square[0] + square[2] );
square[3] = M - ( square[0] + square[6] );
square[5] = M - ( square[2] + square[8] );
square[7] = M - ( square[6] + square[8] );
if( isMagic( square ) )
{
int nSquares = numberOfSquares( square );
if( nSquares >= MIN_NUMBER_OF_SQUARES )
{
foundSomething = true;
cout << "found something[f] (" << nSquares << "):\n";
outFile << "found something[f] (" << nSquares << "):\n";
printSquare( square );
}
}
}
}
cout << "\n";
outFile << endl;
outFile.flush();
}

// Acquire the next central square to try.
j = 1;
do
{
carrying = false;
factorList[MAX_FACTORS - j].prime++;
if( factorList[MAX_FACTORS - j].prime >= primesOneModFourCount - j )
{
j++;
if( j <= MAX_FACTORS )
carrying = true;
else
done = true;
}
}
while( carrying );

if( !done )
{
for( i = MAX_FACTORS - j + 1; i < MAX_FACTORS; i++ )
{
factorList[i].prime = factorList[i - 1].prime + 1;
}
}
}
if( foundSomething )
{
cout << "A viable magic square with the requisite number of squares was found.\n";
outFile << "A viable magic square with the requisite number of squares was found.\n";
}
outFile.close();
if( decompositionList )
delete []decompositionList, decompositionList = 0;
if( factorList )
delete []factorList, factorList = 0;
if( prime )
delete []prime, prime = 0;
if( primesOneModFour )
delete []primesOneModFour, primesOneModFour = 0;
return 0;
}

void readArguments(int argc, _TCHAR* argv[])
{
if( argc >= 2 )
{
wistringstream tempStream( argv[1] );
tempStream >> MIN_PRIME;
if( argc >= 3 )
{
wistringstream tempStream( argv[2] );
tempStream >> MAX_PRIME;
if( argc >= 4 )
{
wistringstream tempStream( argv[3] );
tempStream >> MAX_POWER;
MAX_POWER = 2 * (MAX_POWER / 2) + 1;
if( argc >= 5 )
{
wistringstream tempStream( argv[4] );
tempStream >> MAX_FACTORS;
if( argc >= 6 )
{
wistringstream tempStream( argv[5] );
tempStream >> MIN_NUMBER_OF_SQUARES;
}
}
}
}
}
}

bool isMagic( ZZ* square )
{
// 0 1 2
// 3 4 5
// 6 7 8
int i;
int j;
for( i = 0; i < 9; i++ )
for( j = i + 1; j < 9; j++ )
if( square[i] == square[j] )
return false;

ZZ M = 3 * square[4];
return ( square[0] + square[1] + square[2] == M ) &&
( square[3] + square[4] + square[5] == M ) &&
( square[6] + square[7] + square[8] == M ) &&
( square[0] + square[3] + square[6] == M ) &&
( square[1] + square[4] + square[7] == M ) &&
( square[2] + square[5] + square[8] == M ) &&
( square[0] + square[4] + square[8] == M ) &&
( square[6] + square[4] + square[2] == M );

}

void printSquare( ZZ* square )
{
int i;
ZZ root;
bool isSquare;
cout << "\n";
outFile << "\n";
for( i = 0; i < 9; i++ )
{
isSquare = false;
if( square[i] >= 0 )
{
root = SqrRoot( square[i] );
if( root * root == square[i] )
isSquare = true;
}
if( isSquare )
{
cout << root << "^2 ";
outFile << root << "^2 ";
}
else
{
cout << square[i] << " ";
outFile << square[i] << " ";
}
if( ( i + 1 ) % 3 == 0 )
{
cout << "\n";
outFile << "\n";
}
}
cout << "\n";
outFile << "\n";
}

int numberOfSquares( ZZ* square )
{
int numberOfSquaresFound = 0;
int i;
ZZ root;
for( i = 0; i < 9; i++ )
{
if( square[i] >= 0 )
{
root = SqrRoot( square[i] );
if( root * root == square[i] )
numberOfSquaresFound++;
}
}
return numberOfSquaresFound;
}

void decomposePrime(const ZZ& p, ZZ& a, ZZ& b)
{
ZZ left;
ZZ right;
ZZ temp;

if ( p % 8 == 5 )
right = 2;
else
{
right = to_ZZ( 3 ) % p;
while ( Jacobi( right, p ) == 1 )
{
temp = nextPrime( to_int( right ) );
if( temp == -1 )
{
cout << "\nRAN OUT OF PRIMES!\n";
return;
}
right = temp % p;
}
}

right = PowerMod( right, ( p - 1 ) / 4, p );

if ( right < p / 2 )
right = p - right;
left = p;

while ( right * right > p )
{
temp = left;
left = right;
right = temp % right;
}
a = SqrRoot( p - right * right );
b = right;
}

ZZ nextPrime( int currentPrime )
{
int i;
for( i = currentPrime + 1; i < MAX_PRIME; i++ )
{
if ( prime[i] )
return to_ZZ( i );
}
return to_ZZ( -1 );
}

void generatePrimes()
{
int i, j;

prime[0] = 0;
prime[1] = 0;
for( i = 2; i < MAX_PRIME; i++ )
prime[i] = 1;
j = 0;
while( j * j <= MAX_PRIME )
{
while( prime[j] == 0 && j * j <= MAX_PRIME )
j++;
for( i = j + 1; i < MAX_PRIME; i++ )
{
if ( i % j == 0 )
prime[i] = 0;
}
j++;
}

primesOneModFourCount = 0;

for( i = 1; i < MAX_PRIME; i += 4 )
{
if( prime[i] && i >= MIN_PRIME)
{
primesOneModFour[primesOneModFourCount] = i;
primesOneModFourCount++;
}
}

}

int getAllDecompositions( Factor* factorList, int numberOfFactors, GaussianInteger*& decompositionList )
{
int i;
int numberOfDecompositions = 1;

for( i = 0; i < numberOfFactors; i++ )
numberOfDecompositions *= factorList[i].power + 1;

numberOfDecompositions /= 2;

if( decompositionList )
delete []decompositionList, decompositionList = 0;
decompositionList = new GaussianInteger[numberOfDecompositions];

GaussianInteger x( 1, 0 );
spot = 0;
recurse( factorList, numberOfFactors, decompositionList, x, 0 );

return numberOfDecompositions;
}

void recurse( Factor* factorList, int numberOfFactors, GaussianInteger* decompositionList,
const GaussianInteger& x, int currentFactor )
{
int i;
if( currentFactor == numberOfFactors ) // no factors left
{
GaussianInteger r( 1, 1 );
GaussianInteger ostensiblyNewDecompostion = x * r;

ostensiblyNewDecompostion.a = ostensiblyNewDecompostion.a * ostensiblyNewDecompostion.a;
ostensiblyNewDecompostion.b = ostensiblyNewDecompostion.b * ostensiblyNewDecompostion.b;

// make sure it really is a new and viable decomposition
if( ostensiblyNewDecompostion.a == ostensiblyNewDecompostion.b )
return;
for( i = 0; i < spot; i++ )
{
if( ostensiblyNewDecompostion.a == decompositionList[i].a && ostensiblyNewDecompostion.b == decompositionList[i].b ||
ostensiblyNewDecompostion.b == decompositionList[i].a && ostensiblyNewDecompostion.a == decompositionList[i].b )
return;
}

decompositionList[spot] = ostensiblyNewDecompostion;
spot++;
}
else
{
GaussianInteger y;
GaussianInteger z;
for( i = 0; i <= factorList[currentFactor].power; i++)
{
y = x * sumOfSquaresRepresentationTable[factorList[currentFactor].prime][factorList[currentFactor].power][i];
recurse( factorList, numberOfFactors, decompositionList, y, currentFactor + 1 );
}
}
}

void setupSumOfSquaresTable()
{
int i;
int j;
int k;
sumOfSquaresRepresentationTable = new GaussianInteger**[primesOneModFourCount];
for( i = 0; i < primesOneModFourCount; i++ )
{
sumOfSquaresRepresentationTable[i] = new GaussianInteger*[MAX_POWER];
for( j = 0; j < MAX_POWER; j++ )
sumOfSquaresRepresentationTable[i][j] = new GaussianInteger[j + 1];
}

GaussianInteger x;
GaussianInteger y;
for( i = 0; i < primesOneModFourCount; i++ )
{
decomposePrime( to_ZZ( primesOneModFour[i] ), x.a, x.b );
y = x.conjugate();
for( j = 1; j < MAX_POWER; j++ )
for( k = 0; k <= j; k++ )
sumOfSquaresRepresentationTable[i][j][k] = x.toThe( k ) * y.toThe( j - k );
}
}

void killSumOfSquaresTable()
{
int i;
int j;
for( i = 0; i < primesOneModFourCount; i++ )
{
for( j = 0; j < MAX_POWER; j++ )
{
if( sumOfSquaresRepresentationTable[i][j] )
delete []sumOfSquaresRepresentationTable[i][j],sumOfSquaresRepresentationTable[i][j] = 0;
}
if( sumOfSquaresRepresentationTable[i] )
delete sumOfSquaresRepresentationTable[i], sumOfSquaresRepresentationTable[i] = 0;
}
if( sumOfSquaresRepresentationTable )
delete sumOfSquaresRepresentationTable, sumOfSquaresRepresentationTable = 0;
}

2006-07-17T22:17:00.000-07:00

If the independence number is less than or equal to 3 or greater than 4 and the complement isn't 2-connected, then we are good. So, the independence number must be 4, in addition there is a vertex which is in all order 4 independent sets. There is more, but it is hard to put into words -- need pictures.

2006-07-16T20:23:00.000-07:00

Trying very hard to prove that a graph with chi > 1/2 ( omega + Delta + 2 ) has 2-connected complement. Able to show this for graphs with chi > 1/2 ( omega + Delta + 3 ); only 1/2 off. Have severely restricted possible counterexamples -- after removing a vertex disconnecting the complement, there are two components which must have the same minimal degree, the graph has independence number at most 4, the complements of each of the two components in the complement have the property that the induced subgraph on all vertices of maximal degree has triangle free complement. etc.

2006-07-15T21:47:00.000-07:00

The first plant had to eat the earth for the first animal to be able to eat the plant. This is the way the universe works. Therefore, the universe working another way is not necessary. As the path of least resistance is the way it works for the least resistance: as more resistance, time after time, after time, eventually is total resistance: as what method is offered to increase the ease of passage other than removing the resistance: damage done to the momentum for ever more: as some thing cannot be created from nothing: as more momentum needs a reason for the increase in closed(perpetual motion) system the universe logically must be: and the way it works is the animal: first animal had to eat the vegetable: as the first vegetable must have eaten the mineral: as the first mineral must have eaten the ethereal(structureless space material of feeling[no doubt - ambivalently nominal]). As the earth orbits the sun, the mineral of earth orbits the sun, it impacts the ether and absorbs it. As it absorbs it, the mineral of earth dissolves into the ether(expansion of dense gas into less dense gas). Are we of the closed working system of no guarantee: as here we are today from all yesterdays, with no guarantee of ever being here again for the future, for real. So worst case scenario is the logical artful ploy to discover who we are, where we are and the parameters of continued success of this, so far, everlasting life. Recycled is a logical conclusion in the perpetual motion obviously occuring. We all, everything, dissolve into ether as we leave the center area of the universe and pack up into relatively dense ether shaped like the outside part of a ball until the outward momentum ceases and the inward increases so the ether meets off center and creates spin and fusion at the new center of the universe; fusing into cores which grew under pressure giving off the particles which didn't fit as light and coming off center when too heavy for compression force to hold them on center and having their own inward compression force growing under it: "gravity" to carry on making smaller cores and so on: eternal momentum in a vegetarian strict universe.

2006-07-11T17:54:00.000-07:00

Finished new search range for a 3x3 magic square with at least 7 square entries.
Log so far.

2006-07-10T21:18:00.000-07:00

Tell me this:

why does it happen that at the very, yes, at the very moments when I am
most capable of feeling every refinement of all that is "sublime and
beautiful," it would, as though of design, happen to me not only to feel
but to do such ugly things, such that ... Well, in short, actions that all,
perhaps, commit; but which, as though purposely, occurred to me at the very
time when I was most conscious that they ought not to be committed. The more
conscious I was of goodness and of all that was "sublime and beautiful," the
more deeply I sank into my mire and the more ready I was to sink in it altogether.

The following morning, I lay acutely conscious that the previous day I had
committed a loathsome action again, that what was done could never be undone,
and secretly, inwardly gnawing, gnashing at myself for it, tearing and consuming
myself till at last the bitterness turned into a sort of shameful accursed sweetness.

2006-07-10T20:05:00.000-07:00

Just got back from gym. Spinning ==> tired now.

red wins: 182, blue wins: 146

starting to even out. no draws yet.

Thinking about a slew of other such games. Trying to find a simple one that is drawn if and only if r(5,5) > 43. More generally, games

{ G_(n, k) } such that G_(n, k) is drawn iff r(k, k) > n.

Current candidate: Same as before, but you lose your next turn if you increase your clique number (excluding making your first edge!).

The idea here is to force the players to avoid "boring" clique building races.

Trying this one now: 2003 Au Bon Climat, Pinot Noir, Santa Rita Hills.

2006-07-10T12:51:00.000-07:00

Home for lunch. No example showing r(5,5) > 43 found yet. More later.

2006-07-09T19:28:00.000-07:00

Ok.

2006-07-09T19:05:00.000-07:00

A female.

2006-07-09T19:00:00.000-07:00

This crazy german professor sent me his graph theory knowledge-based system on floppy disks. He repeatedly warned me to make a backup, "because it can corrupt the hard drive". Whatever, free published paper.

2006-07-09T18:59:00.000-07:00

Dargans?

2006-07-09T18:32:00.000-07:00

Today.
Shower:

How many people do you need at a party to guarantee the existence of either k mutual stangers or k mutual friends?

Know:
k = 3 : 6.
k = 4 : 18.
k = 5 : 43 - 49.

Can we find an example of an arrangement of 43 people having no 5-stanger clique nor a 5-friend clique? The space of possibilities is large (say 2^( 43 choose 2 ), without reducing for symmetry). A brute force approach is uninteresting and unlikely to be successful. Need some better way to navigate.

Of course, I don't think about this in terms of friends/stangers, but rather in terms of a red/blue edge coloring of K_43. Since an example would be a delicate balancing act between red and blue, it stands to my reason that the number of red edges and blue edges would be close.

Game:

Two players : Red and Blue.
Red starts.
Players alternate coloring an uncolored edge of K_43 their color.
Red wins if a Red K_5 appears.
Blue wins if a Blue K-5 appears.
Game is drawn if there are no more moves to play and neither player has won.

A draw in this game would give the desired example.

If both players played perfectly, then it seems likely a draw could occur (assuming there are examples with [nearly] equal numbers of red/blue edges). Accepting that, it also seems reasonable that better players would be more likely to draw.

The goal then is to make good players. This game has quite a large branching factor (~ 43 choose 2), so brute force search is out of the question. Perhaps a 2-ply search. Select some parameters for the evaluation functon. Self play, evaluation function tuned by temporal difference learning. Will that explore the space well?

Only one way to find out. The code for the 2 ply search and everything else except the selection of evaluation parameters and learning has been implemented. Currently running with a randomized evaluation function with win detection -- Red is dominating.