Book contents
- Frontmatter
- Contents
- Preface
- W.T. Tutte, 1917–2002
- 1 Decompositions of complete graphs: embedding partial edge-colourings and the method of amalgamations
- 2 Combinatorial schemes for protecting digital content
- 3 Matroids and Coxeter groups
- 4 Defining sets in combinatorics: a survey
- 5 Finite projective planes with a large abelian group
- 6 Algorithmic aspects of graph homomorphisms
- 7 Counting lattice triangulations
- 8 Partition regular equations
- 9 Kostka–Foulkes polynomials and Macdonald spherical functions
4 - Defining sets in combinatorics: a survey
Published online by Cambridge University Press: 05 May 2013
- Frontmatter
- Contents
- Preface
- W.T. Tutte, 1917–2002
- 1 Decompositions of complete graphs: embedding partial edge-colourings and the method of amalgamations
- 2 Combinatorial schemes for protecting digital content
- 3 Matroids and Coxeter groups
- 4 Defining sets in combinatorics: a survey
- 5 Finite projective planes with a large abelian group
- 6 Algorithmic aspects of graph homomorphisms
- 7 Counting lattice triangulations
- 8 Partition regular equations
- 9 Kostka–Foulkes polynomials and Macdonald spherical functions
Summary
Abstract
In a given class of combinatorial structures there may be many distinct objects with the same parameters. Two questions arise naturally.
Given two such objects, where and how do they differ?
How much of an individual object is needed to identify it uniquely?
These questions are obviously related, the first leading to the concept of a trade, and the second to that of a defining set. This survey deals with denning sets in block designs, graphs and some related structures. The corresponding trades in each structure are also discussed briefly.
Introduction
We start with a simple example. A graph G = (V, E) consists of a finite set V of elements called vertices, and a set E of unordered pairs of vertices, called edges. The complete graph on v vertices, Kv, is a graph in which all pairs of distinct vertices constitute edges, so that any graph on v or fewer vertices may be considered as a subgraph of Kv.
If v = 2n, then a one-factor of Kv is a set of n unordered pairs which between them contain each element of V precisely once. A defining set of a one-factor is a subset of its edges which uniquely identifies it. More generally, a perfect matching in a graph G on 2n vertices is a set of n edges incident with each vertex of V.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2003 , pp. 115 - 174Publisher: Cambridge University PressPrint publication year: 2003
- 8
- Cited by