﻿ Equivalence between Linear Tangle and Maximal Single Ideal

Open Journal of Discrete Mathematics
Vol.09 No.01(2019), Article ID:89377,4 pages
10.4236/ojdm.2019.91002

Equivalence between Linear Tangle and Maximal Single Ideal

Takaaki Fujita1, Koichi Yamazaki2

1Graduate School of Science and Technology, Gunma University, Gunma, Japan

2Division of Electronics and Informatics, Gunma University, Gunma, Japan Copyright © 2019 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/   Received: July 22, 2018; Accepted: December 22, 2018; Published: December 25, 2018

ABSTRACT

The concept of linear tangle was introduced as an obstruction to mixed searching number. The concept of (maximal) single ideal has been introduced as an obstruction to linear-width. Moreover, it was already known that mixed search number is equivalent to linear-width. Hence, by combining those results, we obtain a proof of the equivalence between linear tangle and maximal single ideal. This short report gives an alternative proof of the equivalence.

Keywords:

Linear Tangle, Maximal Single Ideal, Submodular Function 1. Introduction

A graph searching game is a game where searchers (or cops) want to capture a fugitive (or robber) and the fugitive want to escape from the searchers, and they move through a graph for their purpose. Graph searching games have been well-studied    , since graph searching games have many practical and theoretical applications such as robot motion planning, network security, and artificial intelligence (see e.g.  ).

There are several variants of graph searching games such as edge search, node search, and mixed search (see e.g.  ) and there are several graph width-parameters such as path-width, tree-width, and branch-width. In the study of graph searching games, it is known that there are some strong connections between graph searching games and graph width parameters, in which the minimum number of searchers (i.e., search number) usually corresponds to the value of width. For example, mixed search number is essentially equivalent to linear-width1 (see   ).

The concept of linear tangle was introduced in  as an obstruction to the existence of mixed searching strategy: there is a linear tangle of order $k+1$ iff there is no mixed searching strategy with k searchers, where k is a prefixed integer. From the equivalence, as mentioned above, between mixed search number and linear-width, a linear tangle of order $k+1$ is an obstruction to being linear-width is at most k (see also  ).

The concept of (maximal) single ideal has been introduced in  as an obstruction to linear-width: there is a maximal single ideal of order $k+1$ iff the linear-width is more than k. Thus, a linear tangle of a large order and a maximal single ideal of a large order are both obstructions to small linear-width, which means that the concepts of linear tangle and maximal single ideal are the same. In this short report, we give an alternative proof of the equivalence between linear tangle and maximal single ideal.

2. Definitions and Notations

In this paper, we consider a pair $\left(E,f\right)$ rather than graphs, where E is an underlying set and f is a symmetric submodular function on E, and such a pair is called connectivity system (see cf.  ). All sets considered in this paper are finite. For an underlying set E and a subset X of E, we denote $E\X$ by $\overline{X}$ .

A function $f{:2}^{E}\to \text{Z}$ is symmetric submodular if f satisfies the following:

1) $f\left(X\right)=f\left(\overline{X}\right)$ for any $X\subseteq E$ ,

2) $f\left(X\right)+f\left(Y\right)\ge f\left(X\cup Y\right)+f\left(Y\cap X\right)$ for any $X,Y\subseteq E$ .

It is known that a symmetric submodular function f satisfies the following properties  : for each $X,Y\subseteq E$ ,

1) $f\left(X\right)\ge f\left(\varnothing \right)$ and

2) $f\left(X\right)+f\left(Y\right)\ge f\left(X\Y\right)+f\left(Y\X\right)$ .

A set X is k-efficient if $f\left(X\right)\le k$ . Throughout the paper, f means a symmetric submodular function, k a fixed positive integer, and we assume that $f\left(\left\{e\right\}\right)\le k$ for every $e\in E$ , hence we have $f\left(\varnothing \right)\le k$ .

Definition 1 (  ). A linear tangle of order $k+1$ 2 on a connectivity system $\left(E,f\right)$ is a family $L$ of k-efficient subsets of E, satisfying the following axioms:

(L1) $\varnothing \in L$ ,

(L2) For each k-efficient subset X of E, exactly one of $X$ or $\overline{X}$ in $L$ ,

(L3) If $X,Y\in L$ , $e\in E$ , and $f\left(\left\{e\right\}\right)\le k$ , then $X\cup Y\cup \left\{e\right\}\ne E$ holds.

Definition 2 (  ). A maximal single ideal of order $k+1$ on a connectivity system $\left(E,f\right)$ is a family $M$ of k-efficient subsets of E, satisfying the following axioms:

(S1) $E\notin M$ ,

(S2) For each k-efficient subset A of E, exactly one of $A$ or $\overline{A}$ in $M$ ,

(S3) If $A,B\subseteq E$ , $A\subset B$ , $B\in M$ , and $f\left(A\right)\le k$ , then $A\in M$ holds,

(S4) If $A\in M$ , $e\in E$ , $f\left(\left\{e\right\}\right)\le k$ , and $f\left(A\cup \left\{e\right\}\right)\le k$ , then $A\cup \left\{e\right\}\in M$ holds.

Since we assume that $f\left(\left\{e\right\}\right)\le k$ for every $e\in E$ , the axioms (L3) and (S4) can be restated, respectively, as follows:

(L3) If $X,Y\in L$ and $e\in E$ , then $X\cup Y\cup \left\{e\right\}\ne E$ holds.

(S4) If $A\in M$ , $e\in E$ , and $f\left(A\cup \left\{e\right\}\right)\le k$ , then $A\cup \left\{e\right\}\in M$ holds.

3. Result

Lemma 1. A linear tangle $L$ of order $k+1$ is a maximal single ideal of order $k+1$ .

Proof. From the axioms (L1) and (L2), it is obvious that $L$ satisfies the axioms (S1) and (S2).

We claim that $L$ satisfies the axioms (S3). Suppose to, the contrary, that there exist k-efficient subsets A and B such that $A\subseteq B$ , $B\in L$ , and $A\notin L$ . Then, we have $\overline{A}\in L$ by (L2), and for any $e\in E$ , $\overline{A}\cup \left\{e\right\}\cup B=E$ holds, but this contradicts the axiom (L3).

Finally, we show that $L$ satisfies the axioms (S4). Suppose to, the contrary, that there exists k-efficient subset $A\in L$ and an element $e\in E$ such that $f\left(A\cup \left\{e\right\}\right)\le k$ and $A\cup \left\{e\right\}\notin L$ hold. Then, we have $\overline{A\cup \left\{e\right\}}\in L$ , hence $A,\overline{A\cup \left\{e\right\}}\in L$ and $A\cup \overline{A\cup \left\{e\right\}}\cup \left\{e\right\}=E$ hold, however, this contradicts the axiom (L3).

Lemma 2. A maximal single ideal $M$ of order $k+1$ is a linear tangle of order $k+1$ .

Proof. From the axioms (S1) and (S2), it is obvious that $M$ satisfies the axioms (L1) and (L2).

We show that $M$ satisfies the axiom (L3). Suppose to, the contrary, that there exists a triple $\left(X,Y,\left\{e\right\}\right)$ such that $X,Y\in M$ , $e\in E$ , and $X\cup Y\cup \left\{e\right\}=E$ . We choose a triple minimizing $|X\cap Y|$ in such triples $\left(X,Y,\left\{e\right\}\right)$ . First, we claim that $X\cap Y=\varnothing$ holds. From the axiom (S3) and the submodularity, $2k\ge f\left(X\right)+f\left(Y\right)\ge f\left(X\Y\right)+f\left(Y\X\right)$ holds. Thus, at least one of $f\left(X\Y\right)$ or $f\left(Y\X\right)$ is at most k. Without loss of generality, we may assume that $f\left(X\Y\right)$ is at most k. Hence, by (S3) from $X\Y\subseteq X$ , we have $X\Y\in M$ . If $X\cap Y\ne \varnothing$ , then we have $|X\cap Y|>|\left(X\Y\right)\cap Y|$ , however, this contradicts the choice of the triple. Thus, we have shown that $X\cap Y=\varnothing$ .

Next, we claim that $e\notin X$ holds. Suppose if not, that is, if $e\in X$ , then we have $X\cup Y=E$ , which implies that $\overline{X}=Y\in M$ holds, however, this contradicts the axiom (S2). Similarly, we know that $e\notin Y$ holds.

Now, we know that the triple $\left(X,Y,\left\{e\right\}\right)$ consists of a partition of E. Hence, we have $f\left(X\cup \left\{e\right\}\right)=f\left(\overline{Y}\right)=f\left(Y\right)\le k$ , and from this, it follows that $X\cup \left\{e\right\}=\overline{Y}\in M$ holds by the axiom (S4). However, this contradicts the axiom (S2).

From lemmas 1 and 2, we have the following theorem.

Theorem 1. Under the assumption that $f\left(\left\{e\right\}\right)\le k$ for every $e\in E$ , $F$ is a linear tangle of order $k+1$ iff $F$ is a maximal single ideal of order $k+1$ .

Acknowledgements

This work was supported by JSPS KAKENHI Grant Number 15K00007.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Fujita, T. and Yamazaki, K. (2019) Equivalence between Linear Tangle and Maximal Single Ideal. Open Journal of Discrete Mathematics, 9, 7-10. https://doi.org/10.4236/ojdm.2019.91002

References

1. 1. Aigner, M. and Fromme, M. (1984) A Game of Cops and Robbers. Discrete Applied Mathematics, 8, 1-12. https://doi.org/10.1016/0166-218X(84)90073-8

2. 2. Bonato, A. (2011) The Game of Cops and Robbers on Graphs. Vo. 12, The Student Mathematical Library. https://doi.org/10.1090/stml/061

3. 3. Bonato, A. and Yang, B.T. (2013) Graph Searching and Related Problems. In: Pardalos, P., Du, D.Z. and Graham, R., Eds., Handbook of Combinatorial Optimization, Springer, Berlin, 1511-1558. https://doi.org/10.1007/978-1-4419-7997-1_76

4. 4. Angelopoulos, S., Fraignaud, P., Fomin, F., Nisse, N. and Thilikos, D.M. (2017) Report on GRASTA 2017, 6th Workshop on Graph Searching, Theory and Applications, Anogia, Crete, Greece, April 10-13, 2017. https://hal-lirmm.ccsd.cnrs.fr/lirmm-01645614

5. 5. Fomin, F.V. and Thilikos, D.M. (2008) An Annotated Bibliography on Guaranteed Graph Searching. Theoretical Computer Science, 399, 236-245. https://doi.org/10.1016/j.tcs.2008.02.040

6. 6. Thilikos, D.M. (2000) Algorithms and Obstructions for Linear-Width and Related Search Parameters. Discrete Applied Mathematics, 105, 239-271. https://doi.org/10.1016/S0166-218X(00)00175-X

7. 7. Bienstock, D. (1989) Graph Searching, Path-Width, Tree-Width and Related Problems (a Survey). In Reliability of Computer and Communication Networks, Vol. 5 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 33-50.

8. 8. Fomin, F.V. and Thilikos, D.M. (2003) On the Monotonicity of Games Generated by Symmetric Submodular Functions. Discrete Applied Mathematics, 131, 323-335. https://doi.org/10.1016/S0166-218X(02)00459-6

9. 9. Fujita, T. and Yamazaki, K. (2017) Linear-Width and Single Ideal. The 20th Anniversary of the Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo University of Science, 29th August-1st September 2017, 110-111. http://www.jcdcgg.u-tokai.ac.jp/JCDCG3_2017_abstracts.pdf

10. 10. Geelen, J., Gerards, B., Robertson, N. and Whittle, G. (2006) Obstructions to Branch-Decomposition of Matroids. Journal of Combinatorial Theory, Series B, 96, 560-570. https://doi.org/10.1016/j.jctb.2005.11.001

NOTES

1If a graph has no pendant vertices, the equivalence holds.

2In  , the order is k rather than k + 1.