Let $\Gamma$ be a connected graph with $H^1(\Gamma) \cong \mathbb{Z}^d$. Can we give a lower bound (preferably of the form $\gg d$) on the maximal number of edge-disjoint cycles one can find in $\Gamma$?
-
$\begingroup$ I obtain the graph $\Gamma$ I care about by starting with a tree $T$, partitioning its vertices into $d$ equivalence classes - with adjacent vertices being non-equivalent - and take the quotient of the graph by the equivalence relation. I assume that gives me a fully general $\Gamma$, and so knowing that $\Gamma$ arises in this way doesn't help? $\endgroup$– H A HelfgottCommented Jan 26, 2021 at 16:56
-
$\begingroup$ What does $\sim$ mean here? $\endgroup$– WojowuCommented Jan 26, 2021 at 17:09
-
$\begingroup$ Isomorphic. Just changed it to $\cong$. $\endgroup$– H A HelfgottCommented Jan 26, 2021 at 17:11
-
1$\begingroup$ Why not to formulate it as $|E|-|V|=d-1$? $\endgroup$– Fedor PetrovCommented Jan 26, 2021 at 17:57
-
$\begingroup$ @FedorPetrov Calling it $H^1$ makes it clear why I said "holey", and also why it should have anything to do with cycles. $\endgroup$– H A HelfgottCommented Jan 26, 2021 at 20:45
2 Answers
For a graph $G$, let $\nu(G)$ be the maximum number of edge-disjoint cycles, and let $\tau(G)$ be the minimum size of a set of edges $X$ such that $G-X$ has no cycles. Note that for a connected graph $G$ with $H^1(G) \cong \mathbb{Z}^d$, we have $d = \tau(G) \geq \nu(G)$, so $\nu(G) \gg d$ is impossible (although I assume you were hoping for $\nu(G) \in \Omega(d)$). This is also impossible, but we can get close.
Theorem. There exists a function $f(k)=O(k \log k)$ such that for every graph $G$, $\tau(G) \leq f(\nu(G))$.
This is actually an exercise in Diestel's graph theory textbook. In other words, $\nu(\Gamma) \geq f^{-1}(d)$. As noted by Gjergji Zaimi in a comment to the other answer, this bound is actually best possible (up to a constant factor) due to a classic example of Erdős and Pósa. Indeed there is huge body of related work, which are all called "Erdős-Pósa theorems." See this survey paper of Raymond and Thilikos or this webpage for more information.
The paper
Harant, Jochen; Rautenbach, Dieter; Recht, Peter; Regen, Friedrich. Packing edge-disjoint cycles in graphs and the cyclomatic number. Discrete Math. 310 (2010), no. 9, 1456--1462
constructs graphs for which the difference between $d$ and the nmaximum number of edge-disjoint cycles is $k$ for any $k \in \mathbb{N}$. If I understand the question correctly this shows you can't have a bound desired without some restrictions on the graphs (I have not thought more about the graphs described in the comments).
Edit: I posted in a rush. This paper and it's references are relevant, but does not answer the question. See comments below.
-
$\begingroup$ Well, I am asking whether one can bound the number of edge-disjoint cycles from below by $d/1000$ (say), so the statement given doesn't quite answer my question. I will follow the reference. $\endgroup$ Commented Jan 26, 2021 at 17:18
-
1$\begingroup$ The relevant paper is the one by Erdos and Posa referenced there. It shows that the best lower bound for the OP is of the form $O(d/\log d)$. $\endgroup$ Commented Jan 26, 2021 at 17:29
-
$\begingroup$ Yes my apologizes. I was too hasty in my office before teaching :). I can leave it up if helpful otherwise delete. It seems @GjergjiZaimi has already found a better reference. $\endgroup$ Commented Jan 26, 2021 at 19:12