### Abstract

A 0-1 matrix is called l-block-free if it nowhere has a pair of rows ancl a pair of columns such that the four entries thus singled out are all 1,s. What is the maximum number of 1's a 4-block-free matrix can have? We investigate a knapsack-type relaxation of a 0-1 prograrnming formulatiotr of the problcm, accotrnt for its solution properties ancl acldress issues as to t,he realizobility in terms of 0-1 matrices of the solutions found. We note frtrt,hermore that a conclusivc answer, valicl fclr all square rrratrices, would also settle the cla.ssical anrl gelrerally unanswered question as to ttle existence of a so-called finite projectiue plane of a given order. Along the way, some surprisingly simple proofs of earlier results arc provided. Also a nerv characlerization of a finite projective plane is given.

Original language | English |
---|---|

Pages (from-to) | 115-131 |

Number of pages | 17 |

Journal | Pure Mathematics and Applications |

Volume | 10 |

Issue number | 2 |

Publication status | Published - 31 Jan 1999 |

Externally published | Yes |

### Keywords

- 4-block-free matrices
- knapsack-type relaxations
- maximum cardinality bipartile matching problem
- MCBMP
- greedy algorithm

## Fingerprint Dive into the research topics of 'Maximum 4-block-free matrices and knapsack-type relaxations'. Together they form a unique fingerprint.

## Cite this

Illés, T., & Krarup, J. (1999). Maximum 4-block-free matrices and knapsack-type relaxations.

*Pure Mathematics and Applications*,*10*(2), 115-131.