Boolean designs and self-dual matroids

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

In this paper we consider a variety of questions in the context of Boolean designs. For example, Erdös asked: How many subsets of an n-set can be found so that pairwise their intersections are all even (odd)? E. Berlekamp [2] and the author both answered this question; the answer is approximately 2[ 1 2n]. Another question which can be formulated in terms of Boolean designs was asked by J. A. Bondy and D. J. A. Welsh [1]. For what values of d can one find a connected binary matroid of rank d which is identically self-dual? We prove that such matroids exist for all d except 2, 3, and 5. The paper ends with a discussion of more general modular designs and with constructions of some identically self-dual matroids representable over the field of three elements.

Original languageEnglish (US)
Pages (from-to)111-128
Number of pages18
JournalLinear Algebra and Its Applications
Volume10
Issue number2
DOIs
StatePublished - 1975

Fingerprint

Matroid
Binary Matroid
Modular Design
Pairwise
Odd
Intersection
Subset
Design
Context

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Numerical Analysis

Cite this

Boolean designs and self-dual matroids. / Graver, Jack E.

In: Linear Algebra and Its Applications, Vol. 10, No. 2, 1975, p. 111-128.

Research output: Contribution to journalArticle

@article{e203a049ce4b4daeb88df47cabe8ebea,
title = "Boolean designs and self-dual matroids",
abstract = "In this paper we consider a variety of questions in the context of Boolean designs. For example, Erd{\"o}s asked: How many subsets of an n-set can be found so that pairwise their intersections are all even (odd)? E. Berlekamp [2] and the author both answered this question; the answer is approximately 2[ 1 2n]. Another question which can be formulated in terms of Boolean designs was asked by J. A. Bondy and D. J. A. Welsh [1]. For what values of d can one find a connected binary matroid of rank d which is identically self-dual? We prove that such matroids exist for all d except 2, 3, and 5. The paper ends with a discussion of more general modular designs and with constructions of some identically self-dual matroids representable over the field of three elements.",
author = "Graver, {Jack E}",
year = "1975",
doi = "10.1016/0024-3795(75)90003-8",
language = "English (US)",
volume = "10",
pages = "111--128",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier",
number = "2",

}

TY - JOUR

T1 - Boolean designs and self-dual matroids

AU - Graver, Jack E

PY - 1975

Y1 - 1975

N2 - In this paper we consider a variety of questions in the context of Boolean designs. For example, Erdös asked: How many subsets of an n-set can be found so that pairwise their intersections are all even (odd)? E. Berlekamp [2] and the author both answered this question; the answer is approximately 2[ 1 2n]. Another question which can be formulated in terms of Boolean designs was asked by J. A. Bondy and D. J. A. Welsh [1]. For what values of d can one find a connected binary matroid of rank d which is identically self-dual? We prove that such matroids exist for all d except 2, 3, and 5. The paper ends with a discussion of more general modular designs and with constructions of some identically self-dual matroids representable over the field of three elements.

AB - In this paper we consider a variety of questions in the context of Boolean designs. For example, Erdös asked: How many subsets of an n-set can be found so that pairwise their intersections are all even (odd)? E. Berlekamp [2] and the author both answered this question; the answer is approximately 2[ 1 2n]. Another question which can be formulated in terms of Boolean designs was asked by J. A. Bondy and D. J. A. Welsh [1]. For what values of d can one find a connected binary matroid of rank d which is identically self-dual? We prove that such matroids exist for all d except 2, 3, and 5. The paper ends with a discussion of more general modular designs and with constructions of some identically self-dual matroids representable over the field of three elements.

UR - http://www.scopus.com/inward/record.url?scp=0016497311&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0016497311&partnerID=8YFLogxK

U2 - 10.1016/0024-3795(75)90003-8

DO - 10.1016/0024-3795(75)90003-8

M3 - Article

AN - SCOPUS:0016497311

VL - 10

SP - 111

EP - 128

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 2

ER -