Importance of the $2^{\tau(G)}\leqslant A(n,g(G))$ conjecture

Question

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.

Answer 1

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.