2
$\begingroup$

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:


Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are no edges between them and $G\setminus(U\cup W) $ has a Hamilton path.


Proof: We apply the following algorithm, mantaining a partition of $V(G)$ into subsets $U,W$ and a path $P$. Initialize $U=V(G)$, $W=\phi$, $P=\phi$.

At each stage of the algorithm do the following: If $|U|\leq|W|$, stop.

Otherwise, if $P$ is empty, move a vertex from $U$ to $P$. If $P$ is non-empty, let $v$ be it's endpoint. If $N(v)\cap U\neq \phi$, pick a vertex $u\in N(v)\cap U$ , and move it to $P$, otherwise ($N(v)\cap U=\phi$) move $v$ to $W$.

At any point of the algorithm there are no edges between $U$ and $W$, and the value $|U|-|W|$ decreases by exactly one on each step.


I'd like to have a similar result, but for directed graphs, something similar to:

"Naive Tentative Lemma": For every directed graph $D$, there exists two disjoint sets $U,W\subseteq V(D)$ of equal size, such that there are no edges between them and $D\setminus(U\cup W)$ has a Hamilton (directed) path.


My approach: Modifying the algorithm slightly, by on each step checking $N^{+}(v)\cap U$ instead of $N(v)\cap U$, we can get the following result:

Lemma 1:For every directed graph $D$, there exists two disjoint sets $U,W\subseteq V(D)$ of equal size, such that $(U,W)$ form a directed pair and $D\setminus(U\cup W)$ has a Hamilton (directed) path.

The fact that they now form a directed pair is an issue, and using the algorithm directly would yield a $P$ that is not a directed path, but $U$ and $W$ would indeed have no edges between them.

My idea would be to prove something along the lines of:

"Realistic Tentative Lemma:" For every directed graph $D$, there exists three disjoint sets $U,W,F\subseteq V(D)$, where $U$ and $W$ are of equal size, and $|F|\leq \gamma n$ for some small $\gamma$, such that there are no edges between $U$ and $W$ and $D∖(U\cup W \cup F)$ has a Hamilton (directed) path.

This can be hinted from the algorithm above, by checking $N^{+}(v)\cap U$ and $N^{-}(v)\cap U$ for each endpoint of the path $P$, doing the same as before if $N^{+}\cap U \neq \phi$, and checking $N^{-}(v)\cap U$ when $N^{+}(v)\cap U =\phi$, if the in-neighbourhood is also empty, we move $v$ to $W$, if it isn't we move $v$ to $F$.

I don't really know how i would go about bounding $|F|$, which i would like to be small, or if there's a more clever way to go about this, or maybe another algorithm that would net something similar to the "Naive Tentative Lemma" from the get-go.

Any help or reference is greatly appreciated!

$\endgroup$
1
$\begingroup$

Regarding your Lemma 1.1, see Lemma 4.4 in Ben-Eliezer, Ido; Krivelevich, Michael; Sudakov, Benny, The size Ramsey number of a directed path, J. Comb. Theory, Ser. B 102, No. 3, 743-755 (2012). ZBL1245.05041.

I don't think there can be any version of your Naive Tentative Lemma or even the Realistic Tentative Lemma because of a complete bipartite graph with all edges oriented from one side to the other.

Would you mind sharing what sort of conclusion you were hoping to draw from this lemma?

$\endgroup$

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.