This one isn't my problem – it came from MathOverflow – but it's frustrating me that I haven't been able to solve it, so I hope by reposting it here I can get some more attention to it and maybe even a solution.

Here are some examples of graphs for which the number of cycles is large relative to the size of the largest doubled cycle minor:

A biconnected graph with no length-3 doubled cycle minor must be either a subdivision of $$K_4$$ or a series-parallel graph in which one of the two arguments to each series composition is a path. All such graphs have $$O(n^2)$$ cycles.

In outerplanar graphs, the length $$k$$ of a doubled cycle minor is the number of leaves of the dual tree. Each cycle can be formed by pruning some branches of the tree, and there are at most $$k$$ branches to prune, so there are $$O(n^k)$$ cycles in the outerplanar graphs with no doubled $$k$$-cycle minor. For instance, the outerplanar graph below has four leaves.

The complete bipartite graph $$K_{k,n}$$ (for $$k \le 2n$$) has maximum doubled cycle minor length $$k$$ and $$O(n^k)$$ cycles.

In complete graphs, the length of a doubled cycle minor is approximately $$2/3$$ the number of vertices. (Each edge contraction can double only two of the edges of a cycle.) The number of cycles is factorial in the number of vertices, so the exponent of the number of cycles (as a polynomial in $$n$$) is also linear in $$n$$.

Form a tree with height $$\log_2 k$$ and branching factor $$b$$ (possibly much larger than $$k$$). Connect each node to all its ancestors and connect the set the children of each node by a spanning tree. If we didn't include the spanning trees, the result would have low tree-depth, causing all of its cycles to have length at most $$k$$, from which it follows that there are $$O(n^k)$$ cycles and maximum doubled cycle length $$k$$. The spanning trees don't significantly increase the number of cycles (you can use at most one path per spanning tree in a cycle, and each cycle touches at most $$k$$ of these trees) and for the same reason doesn't significantly increase the length of the longest doubled cycle minor.

Somehow I have the feeling that the last example, based on tree-depth, is on the right track. For minor-closed graph families, having no large cycle minor is the same as each biconnected component having bounded tree-depth, so having no large doubled cycle minor should be the same as having some structure like tree-depth but a little more complicated. But I can't prove anything of the sort.

ETA 2014-04-10: Solved, negatively, by a planar bipartite permutation graph.

Comments:

None:
2014-04-05T20:16:01Z

May I ask with which program do you generate these beautiful graph figures?

11011110:
2014-04-05T20:34:42Z

Thanks — I drew them using Adobe Illustrator. The vertex placement was done by hand rather than automatically.