The numbers of dependent k-sets in a graph are log concave
From MaRDI portal
(Redirected from The numbers of dependent k-sets in a graph are log concave)
The numbers of dependent \(k\)-sets in a graph are log concave
The numbers of dependent \(k\)-sets in a graph are log concave
A set of vertices in a graph is dependent if it is not independent. Let \(p_k(G)\) denote the number of dependent sets of size \(k\) in a graph \(G\). The author shows that for any graph \(G\) the sequence \(\{p_k(G)\}\) is log concave, i.e., \(p_k^2 \geq p_{k-1}p_{k+1}\) for all \(k\) \((1 \leq k \leq n-1)\) where \(n\) is the order of \(G\). The author uses a modification of the partitioning technique used by Hamidoune.
Recommendations
Cites work
- Graph theory with applications
- scientific article; zbMATH DE number 3974960 (Why is no real title available?)
- scientific article; zbMATH DE number 568836 (Why is no real title available?)
- scientific article; zbMATH DE number 718851 (Why is no real title available?)
- scientific article; zbMATH DE number 1556740 (Why is no real title available?)
- Logarithmic concavity and \({\mathfrak {sl}}_2({\mathbf C})\)
- On a conjecture on the Sperner property
- On Lih's conjecture concerning Spernerity
- On the numbers of independent k-sets in a claw free graph
Cited in
(6)- On the numbers of independent k-sets in a claw free graph
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- On the unimodality of domination polynomials
- scientific article; zbMATH DE number 1556740 (Why is no real title available?)
- scientific article; zbMATH DE number 1792666 (Why is no real title available?)
- The independence polynomial of trees is not always log-concave starting from order 26
This page was built for publication: The numbers of dependent \(k\)-sets in a graph are log concave
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850583)
