4
$\begingroup$

Is the maximum number of induced circuits in a simple directed graph known?


I tried the family of graphs suggested by David and the number of induced cycles is seems to be exactly

$3^{n/3} + \frac{n}{3}$

*tested up to n=51 (for each n multiple of 3).

$\endgroup$
10
$\begingroup$

I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (Sperner's theorem) and at least $3^{n/3}$ (for $n$ a multiple of three that is at least 9: form a cycle of three-vertex sets and add all edges between vertices in consecutive triples). These bounds hold both for the directed and undirected cases.

The $3^{n/3}$ bound turns out to be the right one, to within a polynomial factor at least, for both the directed and undirected cases. To see this, choose a starting vertex in one of $n$ ways (or a starting edge in the undirected case), and then greedily choose the remaining vertices of the cycle one by one. At each step where you have $k$ choices (the remaining neighbors of the most recently chosen vertex), each choice eliminates all those $k$ vertices from the remaining subproblem, because they can no longer be part of any induced cycle extending what you've already chosen. So, if you define $C(i)$ to be the maximum number of extensions that you could still make, given that you have $i$ remaining vertices, then this number obeys the recurrence $C(i)\le\max_{k\le i} kC(i-k)$. The maximum value of $k$ in this recurrence is given for $k=3$, giving $C(i)\le 3^{i/3}$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. Just one thing still confuses me "add all edges between vertices in consecutive triples" : wouldn't this just end up making very short (2-node induced cycles) in directed graphs? Then the maximum number of induced cycles would just be (n/3) + 9*((n/3)-1)? That is (n/3) 3-cycles and 9 2-cycles between vertices of each consecutive triplets. I am sure I have missed something. $\endgroup$ – stardust May 17 '16 at 8:42
  • $\begingroup$ Add the edges only in one direction. $\endgroup$ – David Eppstein May 17 '16 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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