Counting Independent Sets in Graphs of Hyperplane Arrangements

Nicholas Guo; Guangyi Yue

doi:10.1016/j.disc.2019.111764

paper

Counting Independent Sets in Graphs of Hyperplane Arrangements

arXiv:1612.04034 · doi:10.1016/j.disc.2019.111764

Abstract

In this paper, we count the number of independent sets of a type of graph $G (A, q)$ associated to some hyperplane arrangement $A$ , which is a generalization of the construction of graphical arrangements. We show that when the parameters of $A$ satisfy certain conditions, the number of independent sets of the disjoint union $G (A, q_{1}) \cup \dots \cup G (A, q_{s})$ depends only on the coefficients of $A$ and the total number of vertices $\sum_{i} q_{i}$ when $q_{i}$ 's are powers of large enough prime numbers. In addition it is independent of the coefficients as long as $A$ is central and the coefficients are multiplicatively independent.

Accepted by Discrete Mathematics