Two Bijections On NBC Subsets

In 1912,the chromatic polynomial was first introduced by Birkhoff for planar graphs.In 1932,Whitney extended the chromatic polynomial to graphs in general and obtained a combinatorial interpretation for its coefficients by introducing broken circuits,so called Whitney’s broken circuit theorem.In 1973,Stanley obtained that the number of acyclic orientations of a graph equals the number of no broken circuit subsets of its edge set.In 1980,Stanley’s theorem was extended by Las Vergnas to oriented matroids,that is,the number of acyclic orientations of an oriented matroid equals the number of all no broken circuit subsets of its underlying matroid.It’s well known that the characteristic polynomial of hyperplane arrangements extends the chromatic polynomial of graphs.In 1975,Zaslavsky’s formula stated that the number of all regions of a real hyperplane arrangement is exactly equal to the sum of the signless coefficients of its characteristic polynomial.In 1992,Orlik-Terao extended Whitney’s broken circuit theorem to hyperplane arrangements in general,i.e.,the sum of the signless coefficients of its characteristic polynomial equals the number of its no broken circuit subsets with nonempty intersection.In 1986,Blass and Sagan’s algorithm established a bijection from acyclic orientations of a graph to no broken circuit subsets of its edge set.In this thesis we will establish two such bijections for oriented matroids and hyperplane arrangements respectively.Below are the main results.1.Applying the deletion-contraction operation,we establish a bijection from the acyclic reorientations of an oriented matroid to all no broken circuit subsets of its underlying matroid.2.Applying the correspondence between linear hyperplane arrangements and matroids,we obtain a bijection between the regions of a linear hyperplane arrangement and its no broken circuit subsets.This bijection is further extended to affine hyperplane arrangements via the coning operation.