Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.18771 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911461253578752 |
|---|---|
| author | Faal, Hossein Teimoori |
| author_facet | Faal, Hossein Teimoori |
| contents | Let $G$ be a finite simple graph and $B \subseteq V(G)$.
We study the \emph{$B$-restricted clique polynomial} $C_B(G;x)$, including its weighted version allowing vertex multiplicities, as a versatile tool to capture structural properties of vertex subsets.
First, we develop a complete deletion theory for $C_B(G;x)$, including vertex and edge recurrences that generalize classical clique polynomial results.
These recurrences yield monotonicity principles for the largest negative root $ζ_G(B)$: it is monotone under induced subgraphs and reverse-monotone under spanning subgraphs.
Consequently, we derive explicit bounds on $B$-independence numbers, chromatic numbers, $B$-girth, and Hamiltonicity constraints, showing that $ζ_G(B)$ serves as a unifying local invariant.
Next, we connect $B$-clique polynomials to spectral graph theory.
For $(n,d,λ)$-graphs, spectral techniques, including the Expander Mixing Lemma and Tanner's inequality, provide uniform bounds on $B$-restricted clique coefficients, demonstrating that clique growth within $B$ is naturally controlled by the spectral gap.
Finally, we show that weighted $B$-clique polynomials encode \emph{homomorphism constraints}.
Specifically, if $f: G \to H$ is a surjective homomorphism mapping $B_G$ onto $B_H$, then $ζ_G(B_G) \ge ζ_H(B_H)$, yielding a local \emph{no-homomorphism criterion} based on $B$-roots.
Overall, $C_B(G;x)$ provides a unified framework capturing combinatorial, spectral, and homomorphic information in vertex-restricted analysis, highlighting its power for both global and local structural insights. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18771 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A $B$-Restricted Clique Polynomial and Connections to Tanner's Inequality Faal, Hossein Teimoori Combinatorics Let $G$ be a finite simple graph and $B \subseteq V(G)$. We study the \emph{$B$-restricted clique polynomial} $C_B(G;x)$, including its weighted version allowing vertex multiplicities, as a versatile tool to capture structural properties of vertex subsets. First, we develop a complete deletion theory for $C_B(G;x)$, including vertex and edge recurrences that generalize classical clique polynomial results. These recurrences yield monotonicity principles for the largest negative root $ζ_G(B)$: it is monotone under induced subgraphs and reverse-monotone under spanning subgraphs. Consequently, we derive explicit bounds on $B$-independence numbers, chromatic numbers, $B$-girth, and Hamiltonicity constraints, showing that $ζ_G(B)$ serves as a unifying local invariant. Next, we connect $B$-clique polynomials to spectral graph theory. For $(n,d,λ)$-graphs, spectral techniques, including the Expander Mixing Lemma and Tanner's inequality, provide uniform bounds on $B$-restricted clique coefficients, demonstrating that clique growth within $B$ is naturally controlled by the spectral gap. Finally, we show that weighted $B$-clique polynomials encode \emph{homomorphism constraints}. Specifically, if $f: G \to H$ is a surjective homomorphism mapping $B_G$ onto $B_H$, then $ζ_G(B_G) \ge ζ_H(B_H)$, yielding a local \emph{no-homomorphism criterion} based on $B$-roots. Overall, $C_B(G;x)$ provides a unified framework capturing combinatorial, spectral, and homomorphic information in vertex-restricted analysis, highlighting its power for both global and local structural insights. |
| title | A $B$-Restricted Clique Polynomial and Connections to Tanner's Inequality |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.18771 |