Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus (Q1416118)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus |
scientific article |
Statements
Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus (English)
0 references
14 December 2003
0 references
The paper is devoted to the following combinatorial problem: given a Boolean \(m \times n\) matrix with \(m > n\), find either an all-zero row, or two 1's in some column. Some modifications of the problem are discussed. The paper contains interesting historical and bibliographical remarks, examples, and two open problems.
0 references
combinatorics
0 references
matrix
0 references
