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

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

中文关键词:  （0  1）-矩阵  跳跃数

英文关键词:（0  1）-matrices  jump number  stair number.

中文摘要:

      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.还得到了该猜想的另一个反例.

英文摘要:

      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 ∈Λ(2k - 2, k) if k ≥ 11, and find another counter-example to this conjecture .