In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
theory of
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s, a paving matroid is a matroid in which every circuit has size at least as large as the matroid's rank. In a matroid of rank
every circuit has size at most
, so it is equivalent to define paving matroids as the matroids in which the size of every circuit belongs to the set
.
[.] It has been conjectured that
almost all matroids are paving matroids.
Examples
Every simple matroid of rank three is a paving matroid; for instance this is true of the
Fano matroid. The
Vámos matroid
In mathematics, the Vámos matroid or Vámos cube is a matroid over a set of eight elements that cannot be represented as a matrix over any field. It is named after English mathematician Peter Vámos, who first described it in an unpublished ma ...
provides another example, of rank four.
Uniform matroid
In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...
s of rank
have the property that every circuit is of length exactly
and hence are all paving matroids;
the converse does not hold, for example, the
cycle matroid
In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...
of the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
is paving but not uniform.
A
Steiner system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...
is a pair
where
is a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. T ...
of size
and
is a family of
-element subsets of
with the property that every
-element subset of
is also a subset of exactly one set in
. The elements of
form a
-partition of
and hence are the hyperplanes of a paving matroid on
.
''d''-Partitions
If a paving matroid has rank
, then its hyperplanes form a
set system
In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set f ...
known as a
-partition. A family of two or more sets
forms a
-partition if every set in
has size at least
and every
-element subset of
is a subset of exactly one set in
. Conversely, if
is a
-partition, then it can be used to define a paving matroid on
for which
is the set of hyperplanes. In this matroid, a subset
of
is independent whenever either
or
and
is not a subset of any set in
.
Combinatorial enumeration
Combinatorial enumeration
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infini ...
of the simple matroids on up to nine elements has shown that a large fraction of them are also paving matroids.
On this basis, it has been conjectured that
almost all matroids are paving matroids. More precisely, according to this conjecture, the limit, as ''n'' goes to infinity, of the ratio between the number of paving matroids and the number of all matroids should equal one. If so, the same statement can be made for the sparse paving matroids, matroids that are both paving and dual to a paving matroid. Although this remains open, a similar statement on the asymptotic ratio of the logarithms of the numbers of matroids and sparse paving matroids has been proven.
History
Paving matroids were initially studied by , in their equivalent formulation in terms of
-partitions; Hartmanis called them generalized partition lattices. In their 1970 book ''Combinatorial Geometries'',
Henry Crapo and
Gian-Carlo Rota
Gian-Carlo Rota (April 27, 1932 – April 18, 1999) was an Italian-American mathematician and philosopher. He spent most of his career at the Massachusetts Institute of Technology, where he worked in combinatorics, functional analysis, proba ...
observed that these structures were matroidal; the name "paving matroid" was introduced by following a suggestion of Rota.
The simpler structure of paving matroids, compared to arbitrary matroids, has allowed some facts about them to be proven that remain elusive in the more general case. An example is
Rota's basis conjecture, the statement that a set of ''n'' disjoint bases in a rank-''n'' matroid can be arranged into an ''n'' × ''n'' matrix so that the rows of the matrix are the given bases and the columns are also bases. It has been proven true for paving matroids, but remains open for most other matroids.
Notes
References
*.
*.
*.
*
*.
*{{citation
, last = Welsh , first = D. J. A. , authorlink = Dominic Welsh
, contribution = 2.3. Paving Matroids
, isbn = 9780486474397
, pages = 40–41, 44
, publisher = Courier Dover Publications
, title = Matroid Theory
, year = 1976. Reprinted 2010.
Matroid theory