Notes about math, research, and more.
Attempt to find algorithm
What we want
Algorithm which
- Provides k-regular graphs, \(k\geq 3\), with high girth
- Graphs embed into hypercubes
Papers
Linial and Simkin
Title: “A randomized construction of high girth regular graphs”
Mckay, Wormald, and Wysocka
“Short cycles in random regular graphs” Linial and Simkin say that this paper provides a great enumeration of \(k\)-regular graphs such that girth \(\geq 1/2 \log_{k{-1}}n\).
My construction?
- Given girth \(g\)
- Start with disjoint cycles of length \(g\)
- Hypercubes take \(C^g\) and make copies of it. Each cycle must land entirely inside a copy of \(C^g\).
- Must connect in a way similar to \(\mathbb{Z}2\)-homology covers
- When can two adjacent cycles connect?