Combinatorial structure

A combinatorial structure is a discrete mathematical object specified by underlying elements and rules organizing them. A graph equips a set of vertices with edges; a permutation orders labels; a set partition groups them into nonempty subsets. Counting requires an explicit equality convention. Two labelled combinatorial structures may differ only by their labels, whereas an unlabelled combinatorial structure identifies objects related by an appropriate isomorphism. Thus there are three labelled two-element subsets of a three-element set, but only one abstract two-element set up to bijection.

An unlabelled combinatorial structure is a combinatorial structure considered up to an appropriate isomorphism, so the names assigned to underlying elements do not distinguish objects. For graphs, this means a bijection of vertices preserving adjacency. A different drawing or vertex numbering can therefore represent the same unlabelled graph.

On three labelled vertices there are $2^{\left(\genfrac{}{}{0ex}{}{3}{2}\right)}=8$ simple graphs, but only four unlabelled types: the empty graph, one edge with an isolated vertex, the two-edge path, and the triangle. Simply dividing eight by $3!$ cannot work because these types have different numbers of automorphisms.

More generally, relabelling gives a group action of the symmetric group on labelled structures. Unlabelled structures are its orbits, and the orbit-stabilizer theorem explains how automorphisms affect orbit size. Burnside's lemma counts the orbits by averaging fixed-point counts.

A combinatorial structure whose elements carry distinct labels from a prescribed finite set. For example, a rooted tree can have labelled vertices; assigning labels is part of the structure counted by an exponential generating function.

An independence system consists of a finite set $E$ and a nonempty family $\mathcal{I}$ of subsets such that $I\in \mathcal{I}$ and $J\subseteq I$ imply $J\in \mathcal{I}$. This is the hereditary condition: deleting chosen elements keeps a selection admissible. In particular, the empty set belongs to $\mathcal{I}$. An independence system becomes a matroid when it also satisfies the matroid independence axioms for exchange. The hereditary nonmatroid greedy obstruction shows why deletion alone does not justify a greedy algorithm.

The ground set is the set of labelled elements available for selection. An independence system specifies which subsets of this ground set are admissible; in a linear matroid the labels index vectors, whereas in a graphic matroid they index edges.

On the ground set $E=\{x,y,z\}$, permit exactlyThis lists every admissible subset; the excluded subsets are $\{x,y\}$, $\{x,z\}$, and $\{x,y,z\}$. It is an independence system: deleting elements from $\{y,z\}$ produces its listed singletons or the empty set, and deleting from a singleton produces the empty set. But $I=\{x\}$ and $J=\{y,z\}$ violate exchange: neither $y$ nor $z$ can be added to $I$. Thus it is not a matroid.

The descending-weight greedy algorithm admits $x$ first, then rejects both $y$ and $z$, returning $\{x\}$ with weight $10$. Exchanging the tied order of $y,z$ changes nothing. The admissible pair $\{y,z\}$ weighs $12$, exceeding every singleton and the empty set, so it is the true optimum. Both $\{x\}$ and $\{y,z\}$ are maximal elements under inclusion of subsets, but only the pair has maximum cardinality. This identifies exactly where the matroid greedy algorithm loses its guarantee: heredity preserves admissibility under deletions, while exchange prevents a locally maximal selection from being too small.