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.展开更多
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.展开更多
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.
A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization proble...A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.展开更多
Let R=K[x1,…,xn]be the polynomial ring in n variables over a field K and I be a matroidal ideal of R.We show that I is sequentially Cohen-Macaulay if and only if the Alexander dual Iy has linear quotients.As a conseq...Let R=K[x1,…,xn]be the polynomial ring in n variables over a field K and I be a matroidal ideal of R.We show that I is sequentially Cohen-Macaulay if and only if the Alexander dual Iy has linear quotients.As a consequence,I is sequentially Cohen-Macaulay if and only if I is shellable.展开更多
文摘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.
文摘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.
文摘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.
基金supported by the Natural Science Foundation of Shandong Province of China(Nos.ZR2020MA029,ZR2021MA100)the National Natural Science Foundation of China(No.12001335).
文摘A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.
文摘Let R=K[x1,…,xn]be the polynomial ring in n variables over a field K and I be a matroidal ideal of R.We show that I is sequentially Cohen-Macaulay if and only if the Alexander dual Iy has linear quotients.As a consequence,I is sequentially Cohen-Macaulay if and only if I is shellable.
