Counting regions of the boxed threshold arrangement

MaRDI QIDQ4989370zbMATH OpenFDO

Authors Priyavrat Deshpande, Krishna Menon, Anurag Singh

Publication date 25 May 2021

Full work available at URL https://arxiv.org/abs/2101.12060, https://cs.uwaterloo.ca/journals/JIS/VOL24/Deshpande/desh5.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

finite field methodhyperplane arrangementthreshold graph

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Bernoulli and Euler numbers and polynomials (11B68) Relations with arrangements of hyperplanes (32S22) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: In this paper we consider the hyperplane arrangement in $mathbb{R}^n$ whose hyperplanes are $x_i+x_j=1mid1leqi<jleqncup{x}_i=0,1mid1leqileqn$. We call it the emph{boxed threshold arrangement} since we show that the bounded regions of this arrangement are contained in an $n$-cube and are in one-to-one correspondence with the labeled threshold graphs on $n$ vertices. The problem of counting regions of this arrangement was studied earlier by Joungmin Song. He determined the characteristic polynomial of this arrangement by relating its coefficients to the count of certain graphs. Here, we provide bijective arguments to determine the number of regions. In particular, we construct certain signed partitions of the set $-n,dots,nsetminus0$ and also construct colored threshold graphs on $n$ vertices and show that both these objects are in bijection with the regions of the boxed threshold arrangement. We independently count these objects and provide closed form formula for the number of regions.

Recommendations

• A combinatorial statistic for labeled threshold graphs
• Shi threshold arrangement
• scientific article; zbMATH DE number 6670059
• A simple bijection for the regions of the Shi arrangement of hyperplanes
• scientific article; zbMATH DE number 1182849

Cites work

• An introduction to hyperplane arrangements
• Characteristic polynomial of the hyperplane arrangements \(\mathcal{J}_n\) via finite field method
• Characteristic polynomials of subspace arrangements and finite fields
• Combinatorics of permutations
• Counting Labeled Threshold Graphs with Eulerian Numbers
• Enumeration of Graphs and the Characteristic Polynomial of the Hyperplane Arrangements $\mathcal{J}_n$
• Extended linial hyperplane arrangements for root systems and a conjecture of Postnikov and Stanley
• Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• On certain hyperplane arrangements and colored graphs

Cited in

(3)

• Shi threshold arrangement
• A combinatorial statistic for labeled threshold graphs
• \(q\)-Stirling numbers in type \(B\)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counting regions of the boxed threshold arrangement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989370)