Return to Question

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^\star$).

An arc $(u,v)$ in $G$ is called a shortcut if there exists a directed path from $u$ to $v$ in $G$ different from $(u,v)$.

In our research, we came up with the following conjecture:

Conjecture. Let $G$ be a DAG without shortcuts such that the indegree and outdegree of every vertex is each $\leq 2$. Then there exists a matching in $G^\star$ of size at least $\frac{1}{4}e(G)$.

Small examples seem to support this conjecture, although a general proof appears quite elusive. The condition about shortcut absence is essential (there exists a counterexample with a shortcut). The lower bound $\frac{1}{5}e(G)$ here is almost trivial (and holds even with shortcuts), and with some effort we were able to prove the bound $\frac{2}{9}e(G)$.

Any help in proving or disproving the conjecture will be appreciated.

P.S. Apparently it is crucial that $G^\star$ results from a DAG. E.g., a similar statement for a generic undirected graph of degree at most $4$ and no cycles of length $3$ (which follows from the absence of shortcuts $G$) does not hold.

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^\star$).

An arc $(u,v)$ in $G$ is called a shortcut if there exists a directed path from $u$ to $v$ in $G$ different from $(u,v)$.

In our research, we came up with the following conjecture:

Conjecture. Let $G$ be a DAG without shortcuts such that the indegree and outdegree of every vertex is each $\leq 2$. Then there exists a matching in $G^\star$ of size at least $\frac{1}{4}e(G)$.

Small examples seem to support this conjecture, although a general proof appears quite elusive. The lower bound $\frac{1}{5}e(G)$ here is almost trivial (and holds even with shortcuts), and with some effort we were able to prove the bound $\frac{2}{9}e(G)$.

Any help in proving or disproving the conjecture will be appreciated.

P.S. Apparently it is crucial that $G^\star$ results from a DAG. E.g., a similar statement for a generic undirected graph of degree at most $4$ and no cycles of length $3$ (which follows from the absence of shortcuts $G$) does not hold.

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^\star$).

An arc $(u,v)$ in $G$ is called a shortcut if there exists a directed path from $u$ to $v$ in $G$ different from $(u,v)$.

In our research, we came up with the following conjecture:

Conjecture. Let $G$ be a DAG without shortcuts such that the indegree and outdegree of every vertex is each $\leq 2$. Then there exists a matching in $G^\star$ of size at least $\frac{1}{4}e(G)$.

Small examples seem to support this conjecture, although a general proof appears quite elusive. The lower bound $\frac{1}{6}e(G)$ here is almost trivial, and with some effort we were able to prove the bound $\frac{2}{9}e(G)$.

Any help in proving or disproving the conjecture will be appreciated.

P.S. Apparently it is crucial that $G^\star$ results from a DAG. E.g., a similar statement for a generic undirected graph of degree at most $4$ and no cycles of length $3$ (which follows from the absence of shortcuts $G$) does not hold.

For a directed acyclic graph (DAG) $G$, denote by $G^\star$ the undirected graph obtained from $G$ by ignoring direction of its arcs. Let $e(G)=e(G^\star)$ be the number of arcs in $G$ (or edges in $G^\star$).

An arc $(u,v)$ in $G$ is called a shortcut if there exists a directed path from $u$ to $v$ in $G$ different from $(u,v)$.

In our research, we came up with the following conjecture:

Conjecture. Let $G$ be a DAG without shortcuts such that the indegree and outdegree of every vertex is each $\leq 2$. Then there exists a matching in $G^\star$ of size at least $\frac{1}{4}e(G)$.

Small examples seem to support this conjecture, although a general proof appears quite elusive. The condition about shortcut absence is essential (there exists a counterexample with a shortcut). The lower bound $\frac{1}{5}e(G)$ here is almost trivial (and holds even with shortcuts), and with some effort we were able to prove the bound $\frac{2}{9}e(G)$.

Any help in proving or disproving the conjecture will be appreciated.

P.S. Apparently it is crucial that $G^\star$ results from a DAG. E.g., a similar statement for a generic undirected graph of degree at most $4$ and no cycles of length $3$ (which follows from the absence of shortcuts $G$) does not hold.