A combinatorial statistic for labeled threshold graphs

Abstract

Consider the collection of hyperplanes in ${\mathbb{R}}^n$ whose defining equations are given by $\{x_i+x_j=0\mid 1\le i<j\le n\}$. This arrangement is called the threshold arrangement since its regions are in bijection with labeled threshold graphs on $n$ vertices. Zaslavsky's theorem implies that the number of regions of this arrangement is the sum of coefficients of the characteristic polynomial of the arrangement. In the present article we give a combinatorial meaning to these coefficients as the number of labeled threshold graphs with a certain property, thus answering a question posed by Stanley.

Minor changes, final version