en>Rjwilmsi: Journal cites, added 2 DOIs, added 1 issue number using AWB (9888)

2014-01-26T08:33:18Z

Journal cites, added 2 DOIs, added 1 issue number using AWB (9888)

New page

[[File:Vamos matroid.svg|thumb|The [[Vámos matroid]], a paving matroid of rank four; the shaded parallelograms depict its five circuits of size four]]
In the mathematical theory of [[matroid]]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 <math>r</math> every circuit has size at most <math>r+1</math>, so it is equivalent to define paving matroids as the matroids in which the size of every circuit belongs to the set <math>\{r,r+1\}</math>.<ref name="w">{{harvtxt|Welsh|2010}}.</ref>

==Examples==
Every simple matroid of rank three is a paving matroid; for instance this is true of the [[Fano plane|Fano matroid]]. [[Combinatorial enumeration]] of the simple matroids on up to nine elements has shown that a large fraction of them are also paving matroids.<ref name="w"/> The [[Vámos matroid]] provides another example, of rank four.

[[Uniform matroid]]s of rank <math>r</math> have the property that every circuit is of length exactly <math>r+1</math> and hence are all paving matroids;<ref name=Ox26>{{harvnb|Oxley|1992|p=26}}</ref> the converse does not hold, for example, the [[cycle matroid]] of the [[complete graph]] <math>K_4</math> is paving but not uniform.<ref name=Ox27>{{harvnb|Oxley|1992|p=27}}</ref>

A [[Steiner system]] <math>S(t,k,v)</math> is a pair <math>(S,\mathcal{D})</math> where <math>S</math> is a [[finite set]] of size <math>v</math> and <math>\mathcal{D}</math> is a family of <math>k</math>-element subsets of <math>S</math> with the property that every <math>t</math>-element subset of <math>S</math> is also a subset of exactly one set in <math>\mathcal{D}</math>. The elements of <math>\mathcal{D}</math> form a <math>t</math>-partition of <math>S</math> and hence are the hyperplanes of a paving matroid on <math>S</math>.<ref name=Ox367>{{harvnb|Oxley|1992|p=367}}</ref>

==''d''-Partitions==
If a paving matroid has rank <math>d+1</math>, then its hyperplanes form a [[family of sets|set system]] known as a <math>d</math>-partition. A family of two or more sets <math>\mathcal{F}</math> forms a <math>d</math>-partition if every set in <math>\mathcal{F}</math> has size at least <math>d</math> and every <math>d</math>-element subset of <math>\cup\mathcal{F}</math> is a subset of exactly one set in <math>\mathcal{F}</math>. Conversely, if <math>\mathcal{F}</math> is a <math>d</math>-partition, then it can be used to define a paving matroid on <math>E = \cup\mathcal{F}</math> for which <math>\mathcal{F}</math> is the set of hyperplanes. In this matroid, a subset <math>I</math> of <math>E</math> is independent whenever either <math>|I|\le d</math> or <math>|I|=d+1</math> and <math>I</math> is not a subset of any set in <math>\mathcal{F}</math>.<ref name="w"/>

==History==
Paving matroids were initially studied by {{harvtxt|Hartmanis|1959}}, in their equivalent formulation in terms of <math>d</math>-partitions; Hartmanis called them generalized partition lattices. In their 1970 book ''Combinatorial Geometries'', Henry Crapo and [[Gian-Carlo Rota]] observed that these structures were matroidal; the name "paving matroid" was introduced by {{harvtxt|Welsh|1976}} following a suggestion of Rota.<ref name=Ox75>{{harvnb|Oxley|1992|p=75}}</ref>

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.{{sfnp|Geelen|Humphries|2006}}

==Notes==
{{reflist|colwidth=30em}}

==References==
*{{citation
| last1 = Geelen | first1 = Jim | author1-link = Jim Geelen
| last2 = Humphries | first2 = Peter J.
| doi = 10.1137/060655596
| issue = 4
| journal = SIAM Journal on Discrete Mathematics
| mr = 2272246
| pages = 1042–1045 (electronic)
| title = Rota's basis conjecture for paving matroids
| url = http://www.math.uwaterloo.ca/~jfgeelen/publications/paving.pdf
| volume = 20
| year = 2006}}.
*{{citation
| last = Hartmanis | first = Juris | author-link = Juris Hartmanis
| doi = 10.4153/CJM-1959-013-8
| journal = Canadian Journal of Mathematics
| mr = 0099931 | zbl=0089.37002
| pages = 97–106
| title = Lattice theory of generalized partitions
| volume = 11
| year = 1959}}.
*{{citation | zbl=0784.05002 | last=Oxley | first=James G. | authorlink = James Oxley | title=Matroid theory | series=Oxford Science Publications | location=Oxford | publisher=[[Oxford University Press]] | year=1992 | isbn=0-19-853563-5 }}
*{{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 = 2010 | origyear=1976}}.

[[Category:Matroid theory]]

Muscle architecture - Revision history

en>Rjwilmsi: Journal cites, added 2 DOIs, added 1 issue number using AWB (9888)