2
$\begingroup$

The clique-coclique inequality states that for a graph $G$ on $n$ vertices that is either distance-regular or vertex-transitive, the independence number $\alpha(G)$ and the clique number $\omega(G)$ satisfy $$ \alpha(G) \omega(G)\le n. $$ The uncertainty inequality (well, one of its numerous variations) states that for an abelian group $G$ of order $n$, and any function $f\in L(G)$, the support of $f$ and that of its Fourier transform $\hat f$ satisfy $$ |\mathrm{supp} f||\mathrm{supp}\hat f|\ge n. $$

Even though the inequalities go in opposite directions, they manifest a striking similarity. Is this a mere coincidence, or there is a hidden reason for them to be similar?

$\endgroup$
1
  • 2
    $\begingroup$ An inequality that does go in the same direction (and holds for all graphs) is $\chi(G)\chi(\overline G)\ge n$. I have no idea whether it is related to any of this. $\endgroup$ Commented Oct 4, 2023 at 9:24

0

You must log in to answer this question.

Browse other questions tagged .