16
$\begingroup$

In preparation for a talk I am giving to our undergraduate mathematics society, I am trying to collect examples of combinatorial constructions that were found by computer. Thus my question is the following.

What are the most notable examples of combinatorial constructions found by computer search?

For example, one fertile area for such results is lower bounds on Ramsey numbers, for example this recent paper by Exoo and Tatarevic. (But since I am looking for constructions, computer-assisted upper bounds on Ramsey numbers don't count.)

Another non-example would be Aubrey de Grey's construction of a unit-distance graph on 1581 vertices with chromatic number 5 (thereby showing that the chromatic number of the plane is at least 5), since the graph was constructed by hand.

Improve this question
$\endgroup$
6
  • $\begingroup$ Is this a call for research cooperation (in which case it does not belong here), or do you have a specific question that we can actually answer? $\endgroup$
    – Andrej Bauer
    Commented Sep 20, 2018 at 20:16
  • 2
    $\begingroup$ One quick one: Ahmad Abu-Khazneh found (by computer search) an example of a (presumably!) extremal 4-uniform hypergraph for Ryser's conjecture with matching number 2 which doesn't partition into extremal examples with matching number 1. The relevance of this is that for 3-uniform hypergraphs it's known all extremal examples (for any matching number) do so partition, and it was believed this would hold for higher uniformities too. $\endgroup$
    – user36212
    Commented Sep 20, 2018 at 21:14
  • 3
    $\begingroup$ Another general area is small combinatorial designs: many examples exist where the construction involved substantial amounts of computer search. Look in the Journal of Combinatorial Designs at any paper proving the existence of a specific small design; this is likely to be an example for your question. $\endgroup$
    – user36212
    Commented Sep 20, 2018 at 21:15
  • 2
    $\begingroup$ You might enjoy mathoverflow.net/q/12085 . An answer I posted there may be notable as it was an undergraduate (Roger House) who initiated the search for matrices of various determinants. Gerhard "Still More To Be Found" Paseman, 2018.09.20. $\endgroup$
    – Gerhard Paseman
    Commented Sep 21, 2018 at 5:05
  • $\begingroup$ I have a few non-notable examples in one of my papers regarding counter-examples... $\endgroup$
    – Per Alexandersson
    Commented Sep 21, 2018 at 9:47

9 Answers 9

Reset to default
8
$\begingroup$

I don't know how notable this would be but here is another example from my paper "16,051 formulas for Ottaviani's invariant of cubic threefolds" with Christian Ikenmeyer and Gordon Royle, published in J. Algebra 2016. It is this graph: enter image description here

It represents the $SL_5$-invariant of degree 15 of cubics in 5 variables. It was found by a computer search of $1-(15,5,3)$ design with certain desired chromatic properties.

Improve this answer
$\endgroup$
8
$\begingroup$

There is a beautiful story involving the faithfulness question of the Burau representation of the braid group.

Moody showed that the Burau representation is unfaithful if $n$ (the number of strands) is at least 10. The method involved a beautiful reduction to an existence question for a simple closed curve, with certain unusual intersecton properties. Long and Patton improved this to $n \ge 6$ by finding more curves.

Bigelow did extensive computer calculations and found such an exceptional curve for $n=5$, thus showing unfaithfulness for this $n$. He also found a ridiculously simple example for $n = 6$:

https://arxiv.org/pdf/math/9904100.pdf

Improve this answer
$\endgroup$
6
$\begingroup$

there are results in graph theory of this sort, essentially enumerating all the graphs on at most N vertices with such and such properties, and seeing that there are none/some.

E.g. fullerens (modeled by planar graphs with certain properties) might nice topic, see https://doi.org/10.1006/jagm.1996.0806

the most famous computer-based result in graph theory is probably 4-color theorem https://en.m.wikipedia.org/wiki/Four_color_theorem

My humble self constructed few interesting graphs and digraphs on computer (although then publishing (mostly) "computer-free" proofs). https://doi.org/10.1016/j.aim.2017.03.029 https://doi.org/10.1016/0097-3165(95)90062-4

similarly, in finite group theory (which is quite combinatorial subject in a way) one might look in a complete database and reach some conclusion...

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there examples of published papers with such results? Any references? $\endgroup$
    – Nate Eldredge
    Commented Sep 21, 2018 at 14:32
  • $\begingroup$ I added few (posting from a phone - not easy :)) $\endgroup$
    – Dima Pasechnik
    Commented Sep 21, 2018 at 15:06
5
$\begingroup$

I would suggest browsing through the issues of Experimental Mathematics, which has many examples of the kind you seek. (Full disclosure: I am an editor, so you may construe this as tooting my own horn).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I have a submission there with this type of examples regarding polytopes, so you're tooting my horn as well, so its fair :) $\endgroup$
    – Per Alexandersson
    Commented Sep 22, 2018 at 8:09
4
$\begingroup$

Not sure whether this counts as combinatorial: there are several equations for generating functions that were found by computer. I think Bostan, Alin; Kauers, Manuel; Van Hoeij, Mark, The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc. 138, No. 9, 3063-3078 (2010). ZBL1206.05013. and its predecessor

Kauers, Manuel; Koutschan, Christoph; Zeilberger, Doron, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA 106, No. 28, 11502-11505 (2009). ZBL1203.05010. is very nice.

Personally, I am very fond of Exact formulas for the partition function?

Improve this answer
$\endgroup$
4
$\begingroup$

My group, The Permuta Triangle, has been working on automating the discovery of combinatorial specifications. Some of the discovered results for pattern avoiding permutations, set partitions and (soon) Motzkin paths can be viewed at the ComboPal website. Click "Random" in the left hand corner to go on a tour of specifications!

Improve this answer
$\endgroup$
3
$\begingroup$

Many coverings in La Jolla Covering Repository were found by computer.

Improve this answer
$\endgroup$
3
$\begingroup$

The bijection in

Rubey, Martin; Stump, Christian, Double deficiencies of Dyck paths via the Billey-Jockusch-Stanley bijection, J. Integer Seq. 20, No. 9, Article 17.9.6, 9 p. (2017). ZBL1384.05048.

was essentially found by computer.

Improve this answer
$\endgroup$
2
$\begingroup$

Emmanuel Jeandel, Michael Rao, An aperiodic set of 11 Wang tiles, https://arxiv.org/abs/1506.06492

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .