2
$\begingroup$

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$?

$\endgroup$
5
  • $\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$ Jan 26, 2021 at 16:56
  • $\begingroup$ What does $\sim$ mean here? $\endgroup$
    – Wojowu
    Jan 26, 2021 at 17:09
  • $\begingroup$ Isomorphic. Just changed it to $\cong$. $\endgroup$ Jan 26, 2021 at 17:11
  • 1
    $\begingroup$ Why not to formulate it as $|E|-|V|=d-1$? $\endgroup$ 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$ Jan 26, 2021 at 20:45

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\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$ 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$ 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$ Jan 26, 2021 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.