digraph with fixed outdegree and no directed 1-, 2-, or 3-cycles

[Dion Gijswijt]

Sorry, I meant Max's conjecture!

Dion Gijswijt.


> Well, a(n) <= 3n+1.  Just arrange 3n+1 points on a circle,
> with each pointing at the next n points around the circle.
> So if your conjecture is correct, a(n) = 3n+1 (which is A016777).
>
> I suspect that this is the answer, but I have not been able to
> prove or disprove the conjecture.  (More precisely, I proved it
> twice and found three counter-examples, but all were flawed.)
>
> Franklin T. Adams-Watters
>
> -----Original Message-----
> From: Max Alekseyev <maxale at gmail.com>
>
> For given positive integer n, let a(n) be the minimum positive integer
> such that there exists a digraph on a(n) vertices with the outdegree
> of each vertex equal n and no directed 1- (i.e., self-loops), 2-, or
> 3-cycles.
>
> Does this sounds familiar to anybody? Is this sequence in OEIS?
>
> It seems that a(n)>3n but I have no proof yet.
>
> ________________________________________________________________________
> Check Out the new free AIM(R) Mail -- Unlimited storage and
> industry-leading spam and email virus protection.
>