关于Brualdi-Anstee猜想

摘要

著名的组合图论专家Brualdi和Anstee于1980年独立地提出了下述猜想：设R ＝（r1，r2，…，rm）、R′＝（r′1，r′2，…，r′m）、S ＝（s1，s2，…，sn）、S′＝（s′1，s′2，…，s′n）是非负整数向量，u（R，S）表示具有行和向量为R、列和向量为S的｛0，1｝-矩阵类，则存在矩阵A∈u（R，S），B∈u（R′，S′），使A＋B∈u（R＋R′，S＋S′）的充要条件是u（R，S）、u（R′，S′）和u（R＋R′， S＋S′）均非空．1986年，陈永川找到Brualdi-Anstee猜想的反例．对猜想的已知条件作补充，使得该猜想成立并证明之，并且由此得到了两个新定理．%Brualdi and Anstee,two famous experts of combinatorics and graph theory,raised a conjecture in 1980 as follows:Let R =(r1,r2,…,rm),R′=(r′1,r′2,…,r′m),S =(s1,s2,…,sn)and S′=(s′1,s′2,…,s′n)be nonnegative integral vector.Denote by u(R,S)the classes of (0,1 )matrix with row sum vector R and column sum vector S.There exist a matrix A∈u(R,S)and a matrix B∈u(R′,S′)such that A+B∈u(R+R′,S+S′).The necessary and sufficient condition for it is u(R,S)、u(R′,S′)and u(R+R′, S +S′)are not empty.Y.C.Chen found the counterexample in 1986.In this paper,to make the conjecture established and prove it, we make some supplement for the known conditions of the conjecture,then two new theorems are obtained according to it.