Hypergraphic matroids

Main, Roger Anthony (1978). Hypergraphic matroids. PhD thesis The Open University.

DOI: https://doi.org/10.21954/ou.ro.0000fc88

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.

Viewing alternatives

Look up in Google Scholar

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

CORE (COnnecting REpositories)

Recommendations