What is a combinatorial interpretation?

2022/09/13 by Pak, Igor · 4 citations
#05A20 #68Q15 #68R10 #68R99 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.1.3 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2

paper · doi:10.48550/arxiv.2209.06142

Abstract

In this survey we discuss the notion of combinatorial interpretation in the context of Algebraic Combinatorics and related areas. We approach the subject from the Computational Complexity perspective. We review many examples, state a workable definition, discuss many open problems, and present recent results on the subject.

Cited by

• Plethysm is in #BQP
• Vanishing of Schubert coefficients in probabilistic polynomial time
• Asymptotics of higher Lie characters
• Which graph motif parameters count?

Related

• The many faces of modern combinatorics
• Combinatorics
• Combinatorial Representation Theory
• An Introduction to Algebraic Combinatorics
• Discrete mathematics: methods and challenges