8
$\begingroup$

I conjecture that if $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.

For more information, see the 1988 paper by Erdös et al., How to Make a Graph Bipartite.

Question 1: Is this conjecture true by your intuition?

Question 2: What is the complexity of counting the number of odd cycles in a graph? Is there any efficient algorithm to do that?

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ My intuition says you need more than that (consider the graph of 3 groups of $n/3$ vertices $V_1,V_2,V_3$ such that there are all edges $V_1 \to V_2 \to V_3 \to V_1$, haven't thought it through). A $n^2/9$ is a much more intuitive bound. But my intuition also says: "If Erdös said so, it has to be true :)". Counting simple cycles of length exactly $2k+1$ is #W[1]-hard (with respect to $k$), but there might be an easier way for finding all odd cycles. $\endgroup$ – R B Mar 9 '14 at 21:03
  • $\begingroup$ @RB This should already be an answer. $\endgroup$ – Yixin Cao Mar 9 '14 at 22:34
  • $\begingroup$ Actually, I completely ignored the triangle-free part :o. For such graphs, my intuition says it's true, and tight (consider $V_1\to V_2\to V_3\to V_4\to V_5\to V_1$ for equal partition $V_1,..,V_5$. $\endgroup$ – R B Mar 9 '14 at 22:40
  • 1
    $\begingroup$ Dear Rupei, there are two well-known conjectures by erdos where the graph proposed by RB (and perhaps that you also had in mind) are suppose to give the extreme value. One is on the maximum number of pentagons in a triangle free graphs with 5n vertices and the other is the same as your conjecture on the minimum number of edges required to turn a triangle-free graph into bipartite. I vaguely remember that some substantial progress was made on the first conjecture recently but maybe I mix up the two. $\endgroup$ – Gil Kalai Apr 16 '14 at 16:27
  • $\begingroup$ @GilKalai, thank you very much for your comments, dear Professor Kalai, I found the following paper which shows the results you mean: Simonovits, Miklós. "Paul Erdős’ influence on extremal graph theory." The Mathematics of Paul Erdös II. Springer Berlin Heidelberg, 1997. 148-192. $\endgroup$ – Rupei Xu May 15 '15 at 14:00
8
+50
$\begingroup$

My intuition says it's probably true, and here's a matching lower bound (i.e. a graph of which you have to delete at least $\frac{n^2}{25}$ edges for it to become bipertite:

$G=(V_1\cup V_2\cup V_3\cup V_4\cup V_5, (V_1\times V_2) \cup (V_2\times V_3) \cup (V_3\times V_4) \cup (V_4\times V_5) \cup (V_5\times V_1))$ , $|V_1| = |V_2| = |V_3| = |V_4| = |V_5|$.

This graph is certainly triangle free, but if $x<\frac{n^2}{25}$ edges are to be deleted there will still exist a $C_5=v_1\to v_2\to v_3\to v_4\to v_5 \to v_1$ for some vertices $v_1\in V_1, v_2\in V_2, v_3\in V_3, v_4\in V_4, v_5\in V_5$.

As for the second question, it is well known that counting simple cycles of length $2k+1$ are $\#W[1]-hard$, with respect to $k$, and can't be computed in time $n^{o(k)}$ unless ETH fails.

There is, however, a possibility to approximate the number of such cycles in $O^*(2^{O(k)})$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What does "* " mean in $O∗(2^{O(k)})$ ? It seems that we have some hope to solve it. Thanks. $\endgroup$ – Rupei Xu Mar 11 '14 at 8:44
  • 1
    $\begingroup$ @Saeed - as far as I know this is what $O^*(f(k))$ stands for, and this is used in many papers (e.g.) this way. I'm familiar with what you're referring to as $\widetilde O(f(n))$ which is a short writing for $O(f(n)polylog(f(n)))$. $\endgroup$ – R B Apr 12 '14 at 9:46
  • 1
    $\begingroup$ OK, I can see your linked paper but is not like the way you said, but e.g see this paper: lamsade.dauphine.fr/~boria/papers/SteinerTSP.pdf, uses O* in the way I mean, some multiplicant which is much smaller than the original power, e.g if we have algorithm n^3 logn we can write it O*(n^3), or O(2^n n), O(2^n log n), ... write it as O*(2^n), but in parametrized complexity I never seen (or I never noticed) that someone write O*(f(k)) which means O(f(k) poly(n)), I can suppoes it's O(f(k) poly(k)) but where is $n$ in O*(f(k)), May be I'm wrong, though. $\endgroup$ – Saeed Apr 12 '14 at 9:57
  • 1
    $\begingroup$ I guess there are some different notations used in parameterized complexity. Another example can be seen in [Stanford's parameterized algorithms lectures] (stanford.edu/~rrwill/scribe5.pdf). Actually, I haven't seen usage of the $O^*$ notation outside parameterized complexity, so thanks for bringing it to my attention :). $\endgroup$ – R B Apr 12 '14 at 10:14
  • 1
    $\begingroup$ Thanks for your reference, it's interesting to see one notation in different meanings. $\endgroup$ – Saeed Apr 12 '14 at 10:20
1
$\begingroup$

One approach to proving your conjecture would be to try to use the Szemerédi regularity lemma, similar to the way the triangle removal lemma is proved (see e.g. here). I don't know if you'll get the right constants from this approach, though.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ In Szemerédi regularity lemma, usually it assumes a large number of partitions, the exact value of the partition is not easy to get. I wonder maybe it doesn't work here. $\endgroup$ – Rupei Xu May 15 '15 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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