Back to search

The Open University

Hypergraphic matroids

Abstract

dc:description.abstract

A method of defining a matroid on the edge-set of a k-uniform hypergraph (a k-hypergraph) is defined, which is a generalisation of that used for defining a matroid on the edge-set of a graph; the matroids so defined are called "hypergraphic matroids". Analogues are found in hypergraphs of the concepts of trees, forests, circuits, cutsets and components; we show that two generalisations are necessary of the concept of a vertex in a graph - a vertex, and a (k-l)-subset of vertices of a k-hypergraph; we call such a subset a node. The class of hypergraphic matroids is not closed under contraction, but may be enlarged to the class of generalised hypergraphic matroids, which is the closure of the class of hypergraphic matroids under the operation of taking minors. These matroids are defined in an analogous way to hypergraphic matroids, but a particular type of submodular function is necessary, instead of the cardinality function used for hyper graphs. We show that no finite set of forbidden minors exists to characterise either harpergraphic or generalised hypergraphic matroids. There is, however, a lattice characterisation of hypergraphic matroids. Transversal matroids are hypergraphic, and we give a simple method of obtaining a presentation. We also prove that hypergraphic matroids are representable over every characteristic, and that binary generalised hypergraphic matroids are graphic. The graph-theoretic notion of series-parallel extension is generalised, motivated by hypergraph considerations, to a new operation called generalised series-parallel extension. This operation has many properties similar to series-parallel extension. Generalised seriesparallel networks are defined, and characterised by a set of six forbidden minors. An extension of this result characterises ternary base-orderable matroids. We show that the matroid of a hypergraph can be used to derive weak and strong colourings of the nodes, and that, under obvious necessary conditions, all such colourings arise in this way. Connectedness and paths are investigated, but the results obtained for hypergraphs are less satisfactory than those for graphs, largely because the concepts of "node" and "vertex" do not coincide for general k-hypergraphs.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
The Open University
Year dc:date.issued
1978

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Main, Roger Anthony

Rights

Language dc:language
en

Chain of custody

source
Harvested from
The Open University
Base URL
oro.open.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Main, Roger Anthony. Hypergraphic matroids. doctoral thesis, The Open University, 1978.