A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-a...A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not contain any defensive （offensive） k-alliance as a subset. A set Y C V is a defensive （offensive） k-alliance cover, if for all defensive （offensive） k-alliance S, S ∩ Y ≠ 0, i.e., Y contains at least one vertex from each defensive （offensive） k-alliance of F. In this paper we show several mathematical properties of defensive （offensive） k-alliance free sets and defensive （offensive） k-alliance cover sets, including tight bounds on their cardinality.展开更多
We study the strength of some combinatorial principles weaker than Ramsey theorem for pairs over RCA0. First, we prove that Rainbow Ramsey theorem for pairs does not imply Thin Set theorem for pairs. Furthermore, we g...We study the strength of some combinatorial principles weaker than Ramsey theorem for pairs over RCA0. First, we prove that Rainbow Ramsey theorem for pairs does not imply Thin Set theorem for pairs. Furthermore, we get some other related results on reverse mathematics using the same method. For instance, Rainbow Ramsey theorem for pairs is strictly weaker than ErdSs- Moser theorem under RCA0.展开更多
文摘A defensive （offensive） k-alliance in F = （V, E） is a set S C V such that every v in S （in the boundary of S） has at least k more neighbors in S than it has in V ／ S. A set X C_ V is defensive （offensive） k-alliance free, if for all defensive （offensive） k-alliance S, S／ X ≠ 0, i.e., X does not contain any defensive （offensive） k-alliance as a subset. A set Y C V is a defensive （offensive） k-alliance cover, if for all defensive （offensive） k-alliance S, S ∩ Y ≠ 0, i.e., Y contains at least one vertex from each defensive （offensive） k-alliance of F. In this paper we show several mathematical properties of defensive （offensive） k-alliance free sets and defensive （offensive） k-alliance cover sets, including tight bounds on their cardinality.
基金Acknowledgements The author thanks Prof. Wei Wang for his valuable insights and helpful comments. He also thanks Profs. Chitat Chong, Qi Feng, and Yue Yang for providing chances to participate in a series of logic programs held by MCM of CAS and IMS of NUS. This work was partially supported by the National Natural Science Foundation of China （Grant No. 11001281） and the Basic Research Foundation of Jilin University, China （No. 450060502080）.
文摘We study the strength of some combinatorial principles weaker than Ramsey theorem for pairs over RCA0. First, we prove that Rainbow Ramsey theorem for pairs does not imply Thin Set theorem for pairs. Furthermore, we get some other related results on reverse mathematics using the same method. For instance, Rainbow Ramsey theorem for pairs is strictly weaker than ErdSs- Moser theorem under RCA0.
