Searching for combinatorial covers using integer linear programming
Bjarni Jens Kristinsson · 2019
We introduce the CombCov framework which is a generalization of the Struct algorithm introduced by Bean, Gudmundsson, and Ulfarsson in “Automatic discovery of structural rules of permutation classes”. We give a simple example of an application of the framework to avoidance sets of words and discuss in detail how to generate rules of lesser complexity and how a cover is verified up to a certain size using integer linear programming. We then apply the framework to various published results on permutations avoiding mesh patterns and try to find covers of similar problems with some success. We show that CombCov is a powerful tool in guiding humans by coming up with conjectures that would otherwise have required substantial effort to discover manually.; Við kynnum hugbunaðinn CombCov sem er utvikkun a Struct reikniritinu eftir Christian, Bjarka og Henning ur „Automatic discovery of structural rules of permutation classes“. Við skoðum einfalt daemi um notkun þess með forðunarmengjum af orðum og skýrum hvernig reglur eru bunar til og hvernig þakning er sannreynd upp að akveðinni lengd með hjalp linulegrar heiltolubestunar. Siðan beitum við hugbunaðinum a ýmis þekkt vandamal a sviði umraðana sem forðast moskvamynstur og reynum einnig að finna lausnir a aður oleystum vandamalum með einhverjum arangri. Þannig sýnum við að CombCov er oflugt tol sem getur aðstoðað mannfolk við að fa hugmyndir að lausnum sem þvi hefði annars kannski ekki dottið i hug nema með mikilli fyrirhofn.