Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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).
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}$.
