The Maximum Jump Number of (0, 1)-Matrices of Order 2k - 2 with Fixed Row and Column Sum k  

具有固定行列和k的阶为2k-2的(0,1)-矩阵的最大跳跃数(英文)

作　　者：游林[1] 王天明[2] 

机构地区：[1]海南师范大学组合与信息科学实验室,海南海口571158 [2]大连理工大学应用数学系,辽宁大连116024

出　　处：《Journal of Mathematical Research and Exposition》2005年第2期244-254,共11页数学研究与评论（英文版）

基　　金：Hainan Natural Science Foundation of Hainan (10002)

摘　　要：In 1992, Brualdi and Jung first introduced the maximum jump number M(n, k), that is, the maximum number of the jumps of all (0, 1)-matrices of order n with k 1's in each row and column, and then gave a table about the values of M(n, k) when 1 ≤ k ≤ n ≤ 10. They also put forward several conjectures, including the conjecture M(2k - 2, k) = 3k - 4 + [k-2/2]. In this paper, we prove that b(A) ≥ 4 for every A ∈ A(2k - 2, k) if k ≥ 11, and find another counter-example to this conjecture .1992年Brualdi与Jung首次引出了最大跳跃数M(n,k),即每行每列均含k个1的阶为n的(0,1)-矩阵的跳跃数的极大数,给出了满足条件1≤k ≤n ≤10的(0,1)-矩阵的最大跳跃数M(n,k)的一个表,并提出了几个猜想,其中包括猜想M(2k-2,k)=3k-4+[k-2/2].本文证明了当k≥11时,对每个A∈∧(2k-2,k)有b(A)≥4.还得到了该猜想的另一个反例.

关 键 词：(0  1)-matrices jump number stair number. 

分 类 号：O151.21[理学—数学]