3
$\begingroup$

During a course about finite dynamical systems the following conjecture was presented to us :

Let G be a directed graph of order n.
Let $\tau(G)$ be the minimum size of a subset of $V(G)$, $I$ such that $G \setminus I$ is acyclic (Feedback Vertex Set). Let $g(G)$ be the girth of $G$ (the minimum size of a cycle of $G$). If G is acyclic, let $g(G) = n+1$.
Let $A(n,d)$ be the maximum size of a subset $X \subseteq \{0,1\}^n$ such that the Hamming distance of two distinct elements of $X$ is always larger or equal than $d$.

Conjecture : for all graphs $G$ of order $n$, $2^{\tau(G)}\leqslant A(n,g(G))$.

From my understanding, this is just an attempt to find properties of codes and of some particular graphs describing $A(n,d)$ (e.g. hypercubes of dimention $n$ for $A(n,1)$ or subgraphs of these hypercubes for $A(n,x)$). Is that true ?

Does $A(n,g(G))$ describe something useful in particular (in this case $G$ seems to describe the length of the words while it described the words themselves in the case of hypercubes) ?

Are there other consequences/implications ? Does the fact that G should be directed matter ?

Thank you in advance.

$\endgroup$
6
  • $\begingroup$ "subset $I$" of what? $V(G)$ or $E(G)$ "If $G$ is acyclic, let $g(G)=n+1$" where $n$ is what? $\endgroup$
    – bof
    Feb 26, 2018 at 17:39
  • $\begingroup$ @bof: while you are right that this is not defined, it is clear from context that $I\subseteq V(G)$ and that $n=\lvert V(G)\rvert$. at potato: your mentioning 'codes' is indeed relevant, since e.g. according to [C. Godsil, Algebraic Combinatorics, CRC Press, 1993, ISBN 9780412041310; p. 205], the function $A(n,d)$ is the maximum cardinality of a code of minimum distance $d$ inside the $n$-dimensional hypercube. $\endgroup$ Feb 26, 2018 at 18:48
  • $\begingroup$ @bof: It should be fixed now (I just transcribed one-to-one the paper we got). PeterHeinig: thanks ! $\endgroup$
    – potato
    Feb 26, 2018 at 21:43
  • $\begingroup$ @PeterHeinig : does it make more sense now ? $\endgroup$
    – potato
    Feb 26, 2018 at 22:19
  • $\begingroup$ @potato: it makes a little more sense; personally, I still don't understand what "graphs describing $A(n,d)$" is supposed to mean. Also, each of the three questions in the OP seems rather vague to me: 'is this an attempt?', 'are there consequences?', 'does G being directed matter?' I do not mean to be flippant, but strictly speaking the answer is three times 'obviously yes'. That being said, let me add that the most relevant publications I know (though still only trangentially so; in particular they are about undirected graphs) are: [D. A. Pike, Decycling hypercubes, ... $\endgroup$ Feb 27, 2018 at 6:17

1 Answer 1

1
$\begingroup$

Permit me to make a relevant (though inconclusive) observation regarding your question "Does the fact that G should be directed matter?", an observation which lends some intuitive credibility to 'your' conjecture. I take that question to mean

Is enough known about minimum feedback sets to refute the conjecture in the OP for undirected graphs?

In other words, can we disproof the conjecture

Conjecture 0. For every undirected finite simple graph, $2^{\tau(G)}\leq A(n,g(G))$.

An obvious attempt to refute Conjecture 0 is to make use of a theorem of D. A. Pike in

David A. Pike, Decycling hypercubes. Graphs Comb. 19, No.4, 547-550 (2003).

wherein a proof is given that

Theorem 1 If $n\in\omega$ is such that the $n$-dimensional hypercube $Q_n$ contains a minimum feedback vertex set which moreover is an independent set, then $\tau(Q_n) = 2^{n-1} - A(n,\tau(G_n))$.

If Conjecture 0 is true, then for any $n$ as in Theorem 1, and specializing to $G=Q_n$, it follows that (using that $g(Q_n)=4$),

$2^{2^{n-1}}\quad\leq\quad A(n,4)\cdot 2^{A(n,4)}$ ${\hspace{163pt}}$ (consequence)

and deciding whether this is true or false is a matter of pure coding theory. It seems to me that this is true, so that 'your' conjecture cannot be refuted along the lines I am sketching: by the Gilbert-Varshamov bound we have

$A(n,4) \geq \frac{2^n}{1 + n + \binom{n}{2} + \binom{n}{3}}$

and this is comfortably large enough so that for all sufficiently large $n$, the necessary condition (consequence) is satisfied.

$\endgroup$

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.