DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2025.48

On the Roots of Independence Polynomial: Quantifying the Gap

Authors: Om Prakash and Vikram Sharma

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract

The independence polynomial of a graph G is the generating polynomial corresponding to its independent sets of different sizes. More formally, if a_k(G) denotes the number of independent sets of G of size k then I(G,z) := ∑_k (-1)^k a_k(G) z^k. The study of evaluating I(G,z) has several deep connections to problems in combinatorics, complexity theory and statistical physics. Consequently, the roots of the independence polynomial have been studied in detail. In particular, many works have provided regions in the complex plane that are devoid of any roots of the polynomial. One of the first such results showed a lower bound on the absolute value of the smallest root β(G) of the polynomial. Furthermore, when G is connected, Goldwurm and Santini established that β(G) is a simple real root of I(G,z) smaller than one. An alternative proof was given by Csikvári. Both proofs do not provide a gap from β(G) to the smallest absolute value amongst all the other roots of I(G,z). In this paper, we quantify this gap.

Cite as

Om Prakash and Vikram Sharma. On the Roots of Independence Polynomial: Quantifying the Gap. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{prakash_et_al:LIPIcs.FSTTCS.2025.48,
  author =	{Prakash, Om and Sharma, Vikram},
  title =	{{On the Roots of Independence Polynomial: Quantifying the Gap}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.48},
  URN =		{urn:nbn:de:0030-drops-251281},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.48},
  annote =	{Keywords: Independence Polynomial, Root separation, Zero-free regions}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2018.45

Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model

Authors: Swaroop N. Prabhakar and Vikram Sharma

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract

In this paper, we focus on lower bounds for data structures supporting orthogonal range querying on m points in n-dimensions in the semigroup model. Such a data structure usually maintains a family of "canonical subsets" of the given set of points and on a range query, it outputs a disjoint union of the appropriate subsets. Fredman showed that in order to prove lower bounds in the semigroup model, it suffices to prove a lower bound on a certain combinatorial tradeoff between two parameters: (a) the total sizes of the canonical subsets, and (b) the total number of canonical subsets required to cover all query ranges. In particular, he showed that the arithmetic mean of these two parameters is Omega(m log^n m). We strengthen this tradeoff by showing that the geometric mean of the same two parameters is Omega(m log^n m). Our second result is an alternate proof of Fredman's tradeoff in the one dimensional setting. The problem of answering range queries using canonical subsets can be formulated as factoring a specific boolean matrix as a product of two boolean matrices, one representing the canonical sets and the other capturing the appropriate disjoint unions of the former to output all possible range queries. In this formulation, we can ask what is an optimal data structure, i.e., a data structure that minimizes the sum of the two parameters mentioned above, and how does the balanced binary search tree compare with this optimal data structure in the two parameters? The problem of finding an optimal data structure is a non-linear optimization problem. In one dimension, Fredman's result implies that the minimum value of the objective function is Omega(m log m), which means that at least one of the parameters has to be Omega(m log m). We show that both the parameters in an optimal solution have to be Omega(m log m). This implies that balanced binary search trees are near optimal data structures for range querying in one dimension. We derive intermediate results on factoring matrices, not necessarily boolean, while trying to minimize the norms of the factors, that may be of independent interest.

Cite as

Swaroop N. Prabhakar and Vikram Sharma. Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{n.prabhakar_et_al:LIPIcs.FSTTCS.2018.45,
  author =	{N. Prabhakar, Swaroop and Sharma, Vikram},
  title =	{{Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{45:1--45:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.45},
  URN =		{urn:nbn:de:0030-drops-99440},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.45},
  annote =	{Keywords: range querying, lower bounds, matrix factorization, Lagrange dual function}
}

Search Results

Documents authored by Sharma, Vikram

On the Roots of Independence Polynomial: Quantifying the Gap

Abstract

Cite as

Stronger Tradeoffs for Orthogonal Range Querying in the Semigroup Model

Abstract

Cite as

Thanks for your feedback!

Could not send message