<p>I don't know what's already known but the obvious bounds are that it is at most $\binom{n}{n/2}$ (<a href="https://en.wikipedia.org/wiki/Sperner%27s_theorem">Sperner's theorem</a>) 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.</p>

<p>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}$.</p>

CC BY-SA 3.0
2016-05-17T08:42:05.513Z
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.
stardust
CC BY-SA 3.0
2016-05-17T17:34:05.280Z
Add the edges only in one direction.
David Eppstein
CC BY-SA 3.0
2016-05-16T20:51:41.193Z
2016-05-16T22:10:46.357Z
2016-05-16T22:10:46.357Z
David Eppstein
<p>Is the maximum number of induced circuits in a simple directed graph known? </p>

<hr>

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

<p>$3^{n/3} + \frac{n}{3}$ </p>

<p>*tested up to n=51 (for each n multiple of 3).</p>

<graph-theory><graph-algorithms><co.combinatorics>
The maximum number of induced cycles in a simple directed graph
stardust
# The maximum number of induced cycles in a simple directed graph

(Asked by: username_0 on 2016-05-16)

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).

**Tags:** graph-theory, graph-algorithms, co.combinatorics

---

## 1 answers

### Answer by username_1 on 2016-05-16. Score: 10 | Accepted answer

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](https://en.wikipedia.org/wiki/Sperner%27s_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}$.

> **Comments:**
> **username_0**: 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.  
> **username_1**: Add the edges only in one direction.  

---

