Attempting the Impossible: Enumerating Extremal Submodular Functions for n = 6
Our latest paper has appeared in the Recent Advances in Scientific Computing & Applications issue of Mathematics by MDPI! The paper furthers research into a type of mathematical function called submodular functions, which have been used in information inequalities, operational research, combinatorial optimization and social sciences, and they have also found fundamental applications in game theory and machine learning. Submodular functions can be thought of as occupying a region of space, and knowing where the vertices (actually, extremal rays) of this region are can simplify optimization problems to a simple search for the best vertex or ray.
These rays had been listed for submodular functions defined over 3, 4 and 5 base elements. While for 5 elements there are only about 120,000 extremal rays, it was not known whether it would be possible to calculate all extremal rays for 6. This paper reports the results of attempting to do so. Using improved tools from polyhedral geometry, we have computed 360 billion of them, and provide the first reasonable estimate of their total number, which is expected to be between 1,000 and 10,000 times this number. We also present insights into the symmetries of these functions, as well as two new inequality insertion orders that allow processing them further than before.