This website is a collection of results; still in progress!

SAT VS Bicolored Point Sets

We investiaged the following properties on bicolored (abstract) point sets: Note that a convex $k$-hole is a $k$-island by definition and that a $k$-island admits a general $k$-hole. We remark that the horton set can be "doubled" and colored in a way such that it does not contain monochromatic convex 5-holes.

The following abstract point sets were found using SAT solvers in combination with signature functions. The point sets were found using our library pyotlib by improving existing examples and some of the abstract point sets could even be realized.

Sets without monochromatic convex 4-holes

The previously best known example had $n = 46$ points; we refer to arXiv:0910.2700 or the point set zoo.

Abstract

data/bcc4h/n0047bcc4h000000.clt

data/bcc4h/n0048bcc4h000000.clt

data/bcc4h/n0049bcc4h000000.clt

data/bcc4h/n0050bcc4h000000.clt

data/bcc4h/n0051bcc4h000000.clt

data/bcc4h/n0052bcc4h000000.clt

data/bcc4h/n0053bcc4h000000.clt

data/bcc4h/n0054bcc4h000000.clt

data/bcc4h/n0055bcc4h000000.clt

data/bcc4h/n0056bcc4h000000.clt

data/bcc4h/n0057bcc4h000000.clt

data/bcc4h/n0058bcc4h000000.clt

data/bcc4h/n0059bcc4h000000.clt

data/bcc4h/n0060bcc4h000000.clt

data/bcc4h/n0065bcc4h000000.clt

data/bcc4h/n0067bcc4h000000.clt

data/bcc4h/n0068bcc4h000000.clt

data/bcc4h/n0069bcc4h000000.clt

data/bcc4h/n0071bcc4h000000.clt

data/bcc4h/n0077bcc4h000000.clt

We remark that computing n0069bcc4h000000.clt took 32 hours on a 2GHz CPU using GLPK+minisat.

Real

data/bcc4h/n0046bcc4h000000.psz

data/bcc4h/n0047bcc4h000001.psz

data/bcc4h/n0048bcc4h000002.psz

Sets without monochromatic 4-islands

The previously best known example had $n = 35$ points; see for example the point set zoo.

Abstract

data/bc4i/n0036bc4i000000.clt

data/bc4i/n0037bc4i000000.clt

data/bc4i/n0038bc4i000000.clt

data/bc4i/n0039bc4i000000.clt

data/bc4i/n0040bc4i000000.clt

data/bc4i/n0041bc4i000000.clt

data/bc4i/n0042bc4i000000.clt

data/bc4i/n0043bc4i000000.clt

data/bc4i/n0044bc4i000000.clt

data/bc4i/n0045bc4i000000.clt

data/bc4i/n0046bc4i000000.clt

We remark that computing n0046bc4i000000.clt took 60 hours on a 2GHz CPU using GLPK+minisat.

Real

data/bc4i/n0035bc4i000000.psz

data/bc4i/n0036bc4i000001.psz

Sets without monochromatic general 4-holes

The previously best known example had $n = 22$ points; see for example the point set zoo.

Abstract

data/bcg4h/n0025bcg4h000000.clt

Real

data/bcg4h/n0024bcg4h000000.psz

Sets without monochromatic 5-islands

The previously best known example had $n = 61$ points; see for example the point set zoo.

Abstract

Real

data/bc5i/n0064bc5i000000.psz

data/bc5i/n0065bc5i000003.psz

Sets without monochromatic general 5-holes

Abstract

Real

data/bcg5h/n0030bcg5h000000.psz

data/bcg5h/n0031bcg5h000003.psz

Last update: 09.03.2017, (c) 2017 Manfred Scheucher