Create accountLogin

Recent searches

No recent searches

Search options

Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!

Administered by:

Server stats:

3K
active users

mathstodon.xyz: AboutStatusProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.3.7

Chris Purcell

Here's a sequence that doesn't appear to be in the oeis (unless I erred). Let aₙ be the size of the smallest graph with exactly n cycles. The first few terms are: 3,5,4,6...
a₅ is pretty hard to figure out by hand (I think the answer is 8) but it's easy to check that a₆=5 a₇=4.
A trivial upper bound on aₙ is 2n+1. I think there should be a not too difficult upper bound of O(√n).
Anyone know anything else?

Aug 26, 2020, 02:11 PM·Public·Web
0boosts·1favorite
Public
Chris Purcell

One idea I had: if you take a cycle and add a path between two of its vertices, you get a graph with three cycles. If you repeat, you either get six or seven depending on the choice of vertices. That means you can only achieve four or five cycles by gluing two graphs at a vertex, which I used to figure out a₄ and a₅.

Public
Colin the Mathmo

@ccppurcell Assuming simple and undirected I guess ... I could post this on the MathsProm list, known to be frequented by Neil Sloane.

How far have you got? Can you write an informal page sketching your thoughts?

Public
Chris Purcell

@ColinTheMathmo simple and undirected is correct. I got up to a₈ I think a₉ should be 8 but not sure. I will write a page tomorrow!

Public
Colin the Mathmo

@ccppurcell I've written a blog post. There might be more to add later, but I've realised there was more work underneath than there was worth talking about.

Here:

solipsys.co.uk/new/VerticesReq

www.solipsys.co.ukVertices Required For Cycles
Public
0xDE

@ccppurcell Replacing each edge of an n-gon by a triangle gives number of cycles 2n+n (two choices at each edge if you go all the way around, plus the triangles), with O(n) vertices and edges.

Now for any n build a graph whose biconnected components look like this, choosing greedily at each step the biggest polygon you can use. Result: exactly n cycles using O(log⁡n) vertices and edges.

Probably with care you can reduce vertices to O(log⁡n/log⁡log⁡n).

Public
Chris Purcell

@11011110 oh that's nice thanks! By "with care" you mean replace the greedy approach with something else? I don't have good intuition for O(log⁡n/log⁡log⁡n) unfortunately

Public
0xDE

@ccppurcell No, I meant use greedy but with graphs that have a wider range of numbers of cycles so that each greedy step can get much closer to the number of cycles you want.

Ω(log⁡n) edges and/or Ω(log⁡n/log⁡log⁡n) vertices are obvious lower bounds because every cycle is a set of edges and even complete graphs have only factorial-like numbers of cycles.

SearchLive feeds
About