On the algebra generated by three commuting matrices: combinatorial cases

Gerstenhaber proved in 1961 that the unital algebra generated by a pair of commuting $d\times d$ matrices over a field has dimension at most $d$. It is an open problem whether the analogous statement is true for triples of matrices which pairwise commute. We answer this question for special classes of triples of matrices arising from combinatorial data.