Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is b...Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained.展开更多
In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
Elias,et al.(2016)conjectured that the Kazhdan-Lusztig polynomial of any matroid is logconcave.Inspired by a computer proof of Moll’s log-concavity conjecture given by Kauers and Paule,the authors use a computer alge...Elias,et al.(2016)conjectured that the Kazhdan-Lusztig polynomial of any matroid is logconcave.Inspired by a computer proof of Moll’s log-concavity conjecture given by Kauers and Paule,the authors use a computer algebra system to prove the conjecture for arbitrary uniform matroids.展开更多
An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “g...An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “global” version and a “pseudo-global” version. Some corresponding properties of combinatorial schemes are also obtained.展开更多
An excellent introduction to the topic of poset matroids is due to M.Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rankaxioms for poset matroids. In this paper, we stud...An excellent introduction to the topic of poset matroids is due to M.Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rankaxioms for poset matroids. In this paper, we study the special integral function f and obtain a newclass of poset matroids from the old ones, and then we generalize this result according to theproperties of f. Almost all of these results can be regarded as the application of global rankaxioms for poset matroids. The main results in our paper have, indeed, investigated the restrictionof the basis of the poset matroid, and we give them the corresponding geometric interpretation.展开更多
Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is t...Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.展开更多
Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55： 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if ...Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55： 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e＇ for any two edges e and e＇ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.展开更多
Delta-matroid theory is often thought of as a generalization of topological graph theory.It is well-known that an orientable embedded graph is bipartite if and only if its Petrie dual is orientable.In this paper,we fi...Delta-matroid theory is often thought of as a generalization of topological graph theory.It is well-known that an orientable embedded graph is bipartite if and only if its Petrie dual is orientable.In this paper,we first introduce the concepts of Eulerian and bipartite delta-matroids and then extend the result from embedded graphs to arbitrary binary delta-matroids.The dual of any bipartite embedded graph is Eulerian.We also extend the result from embedded graphs to the class of delta-matroids that arise as twists of binary matroids.Several related results are also obtained.展开更多
The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation...The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.展开更多
Ditroid is a directed version of matroid. In this paper we investigate transversal theory of ditroids. Directed versions of Rado-Hall and Edmonds-Fulkerson theorems are obtained. Our results provide partial answers to...Ditroid is a directed version of matroid. In this paper we investigate transversal theory of ditroids. Directed versions of Rado-Hall and Edmonds-Fulkerson theorems are obtained. Our results provide partial answers to two questions raised by L. Qi.展开更多
Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the lo...Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.展开更多
In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an appro...In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.展开更多
Some properties of closed fuzzy matroid and those of its hyperplanes are investigated. A fuzzy hyperplane property, which extends the analog of a crisp matroid from crisp set systems to fuzzy set systems, is proved.
The problem of k-llmited maximum base was specified into two special problems of k-limited maximum base; that is, let subset D of the problem of k-limited maximum base be an independent set and a circuit of the matroi...The problem of k-llmited maximum base was specified into two special problems of k-limited maximum base; that is, let subset D of the problem of k-limited maximum base be an independent set and a circuit of the matroid, respectively. It was proved that under this circumstance the collections of k-limited base satisfy base axioms. Then a new matroid was determined, and the problem of k-limited maximum base was transformed to the problem of maximum base of this new matroid. Aiming at the problem, two algorithm% which in essence are greedy algorithms based on former matroid, were presented for the two special problems of k- limited maximum base. They were proved to be reasonable and more efficient than the algorithm presented by Ma Zhongfan in view of the complexity of algorithm.展开更多
In this paper, some properties of the image of the geometric lattice of a graphic matroid under a strong map are discussed, and a negative answer to the related open question of Welsh’s book is given.
Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization,algorithm design and so on.On the other hand,quantum computing has attracted much att...Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization,algorithm design and so on.On the other hand,quantum computing has attracted much attention and has been shown to surpass classical computing on solving some computational problems.Surprisingly,crossover studies of the two fields seem to be missing in the literature.This paper initiates the study of quantum algorithms for matroid property problems.It is shown that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits(bases,flats,hyperplanes)of a matroid,and for the decision problem of deciding whether a matroid is uniform or Eulerian,by giving a uniform lower boundΩ■on the query complexity of all these problems.On the other hand,for the uniform matroid decision problem,an asymptotically optimal quantum algorithm is proposed which achieves the lower bound,and for the girth problem,an almost optimal quantum algorithm is given with query complexityO■.In addition,for the paving matroid decision problem,a lower boundΩ■on the query complexity is obtained,and an O■ quantum algorithm is presented.展开更多
文摘Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained.
文摘In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
基金supported by the National Natural Science Foundation of China under Grant Nos.11901431 and 12171362.
文摘Elias,et al.(2016)conjectured that the Kazhdan-Lusztig polynomial of any matroid is logconcave.Inspired by a computer proof of Moll’s log-concavity conjecture given by Kauers and Paule,the authors use a computer algebra system to prove the conjecture for arbitrary uniform matroids.
基金Supported by the National Natural Science Foundation of China (Granted No.103710438)Education Ministry of China (Granted No.02139)
文摘An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “global” version and a “pseudo-global” version. Some corresponding properties of combinatorial schemes are also obtained.
基金Supported partially by the National Natural Science Foundation of China(Grant No.10371048)
文摘An excellent introduction to the topic of poset matroids is due to M.Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rankaxioms for poset matroids. In this paper, we study the special integral function f and obtain a newclass of poset matroids from the old ones, and then we generalize this result according to theproperties of f. Almost all of these results can be regarded as the application of global rankaxioms for poset matroids. The main results in our paper have, indeed, investigated the restrictionof the basis of the poset matroid, and we give them the corresponding geometric interpretation.
基金Supported by National Natural Science Foundation of China (Grant No. 60673047) and RFDP 200804220001
文摘Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.
基金The authors would like to thank the referees for providing some very helpful suggestions for revising this paper. This work was supported by the National Natural Science Foundation of China （Grant No. 61070230）.
文摘Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55： 654-659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e＇ for any two edges e and e＇ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.
基金supported by the National Natural Science Foundation of China(Nos.12171402,12101600)by the Fundamental Research Funds for the Central Universities(No.2021QN1037)。
文摘Delta-matroid theory is often thought of as a generalization of topological graph theory.It is well-known that an orientable embedded graph is bipartite if and only if its Petrie dual is orientable.In this paper,we first introduce the concepts of Eulerian and bipartite delta-matroids and then extend the result from embedded graphs to arbitrary binary delta-matroids.The dual of any bipartite embedded graph is Eulerian.We also extend the result from embedded graphs to the class of delta-matroids that arise as twists of binary matroids.Several related results are also obtained.
基金Supported by the National Natural Science Foundation of China(31601209)the Natural Science Foundation of Hubei Province(2017CFB398)
文摘The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.
文摘Ditroid is a directed version of matroid. In this paper we investigate transversal theory of ditroids. Directed versions of Rado-Hall and Edmonds-Fulkerson theorems are obtained. Our results provide partial answers to two questions raised by L. Qi.
文摘Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.
基金Project (No. 10671177) supported by the National Natural Science Foundation of China
文摘In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.
文摘Some properties of closed fuzzy matroid and those of its hyperplanes are investigated. A fuzzy hyperplane property, which extends the analog of a crisp matroid from crisp set systems to fuzzy set systems, is proved.
文摘The problem of k-llmited maximum base was specified into two special problems of k-limited maximum base; that is, let subset D of the problem of k-limited maximum base be an independent set and a circuit of the matroid, respectively. It was proved that under this circumstance the collections of k-limited base satisfy base axioms. Then a new matroid was determined, and the problem of k-limited maximum base was transformed to the problem of maximum base of this new matroid. Aiming at the problem, two algorithm% which in essence are greedy algorithms based on former matroid, were presented for the two special problems of k- limited maximum base. They were proved to be reasonable and more efficient than the algorithm presented by Ma Zhongfan in view of the complexity of algorithm.
基金Foundation item:The NSF(99SL02)of Shaanxi Province and the SF(20609)of China for Postdoctoral Fellow.
文摘In this paper, some properties of the image of the geometric lattice of a graphic matroid under a strong map are discussed, and a negative answer to the related open question of Welsh’s book is given.
文摘Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
基金National Natural Science Foundation of China(Grant Nos.62272492,61772565)Guangdong Basic and Applied Basic Research Foundation(No.2020B1515020050).
文摘Matroid theory has been developed to be a mature branch of mathematics and has extensive applications in combinatorial optimization,algorithm design and so on.On the other hand,quantum computing has attracted much attention and has been shown to surpass classical computing on solving some computational problems.Surprisingly,crossover studies of the two fields seem to be missing in the literature.This paper initiates the study of quantum algorithms for matroid property problems.It is shown that quadratic quantum speedup is possible for the calculation problem of finding the girth or the number of circuits(bases,flats,hyperplanes)of a matroid,and for the decision problem of deciding whether a matroid is uniform or Eulerian,by giving a uniform lower boundΩ■on the query complexity of all these problems.On the other hand,for the uniform matroid decision problem,an asymptotically optimal quantum algorithm is proposed which achieves the lower bound,and for the girth problem,an almost optimal quantum algorithm is given with query complexityO■.In addition,for the paving matroid decision problem,a lower boundΩ■on the query complexity is obtained,and an O■ quantum algorithm is presented.
