Integer.tex

\section{Integer programming}\label{integer-sec}

Integer programming is linear programming with solutions restricted to the integers. A number of packages, for example Maple.12, can solve these problems. It was used in several places during this project.

The first place it was used was to find $c_5$, the maximal subset of $[3]^5$ with no combinatorial lines. One 0/1-variable was used for each point in the cube, and one linear inequality for each combinatorial line. The computer found twelve solutions with 150 points, and found that there were no solutions with 151 points, so $c_5 = 150$. It follows easily that $c_6 = 450$, but the same program was used as a check to show that any set of 451 points in $[3]^6$ has a combinatorial line.

The following routine was used for the 5 dimensional Moser problem to show that $c'_5\ge 124$. Let G be the 3-hypergraph with vertex set equal to $[3]^5$ as before and set $(I,J,K)\in E_3$ to be a 3-edge if and only if it is a geometric line. $c'_5$ is then the size of a maximal independent set. Let

$$ f(x) = \sum_I x_I - \sum_{(I,J,K)\in E_3} x_Ix_Jx_K. $$

The following then holds,

$$c'_n = max_{x\in\{0,1\}^{3^n}} f(x) = max_{x\in [0,1]^{3^n}} f(x).$$

To check the first equality, if $V$ is a line-free set in $G$ of size $k$, set $x_J=1$ for $J\in V$, and zero otherwise. Then $f(x) = k$ because $V$ is line-free, so all the cubic terms are zero. So $c'_n \le max_{x\in\{0,1\}^{3^n}} f(x)$. Conversely, if for some $x\in\{0,1\}^{3^n}$, $f(x)=k$ and if there are triplets $x_I=x_J=x_K=1$ with $(I,J,K)\in E_3$, we change $x_I$ to 0. This reduces $\sum_I x_I$ by 1 but also reduce the second term of $f(x)$ by at least one. So repeating we can find an $x\in\{0,1\}^{3^n}$ with $f(x)\ge k$ and $x_Ix_Jx_K=0$ if $(I,J,K)\in E_3$, i.e. an independent set of size $\ge k$. So $c'_n \ge max_{x\in\{0,1\}^{3^n}} f(x)$. The second equality follows from the maximum principle since $f$ is a square free polynomial. $-f$ was then minimized using Matlab's built-in minimization routine, and found a 124-point subset of $[3]^5$ with no geometric lines.

A third application of integer programming is expanded in some detail in Section \ref{moser-upper-sec}. Each point is classified by how many of its coordinates are 2. Then the possible histograms or 'statistics' of points in a low-dimensional line-free set were computed by brute-force. Since a low-dimensional space fits into a higher-dimensional space in many ways, the low-dimensional statistics had consequences for higher-dimensional sets. Many dozens of inequalities were found for six-dimensional and higher spaces, and Maple's integer programming routine was used to find limits on $c'_n$.

A fourth application of integer programming found many of our best lower bounds for both the DHJ problem and the Moser problem. Assume that a solution is made up of complete $\Gamma(a,b,c)$ cells. This drastically reduces the number of variables, from $3^n$ to $(n+2)(n+1)/2$ binary variables, one for each Gamma set. In the DHJ problem, points in a combinatorial line will lie in cells of the form $\Gamma(a+r,b,c)$, $\Gamma(a,b+r,c)$ and $\Gamma(a,b,c+r)$ for some positive $r$. Thus the line-free condition is met if we prevent equilateral triangles of this sort. The Fujimora problem was to maximize the number of Gamma sets under this restriction, searching over the $(n+2)(n+1)/2$ binary variables. The weighted Fujimora problem was to maximize the total number of points. Thus each Gamma set $\Gamma(a,b,c)$ is weighted by its size $(a+b+c)!/(a!b!c!)$, but the restrictions are the same.

In the Moser-Fujimura problem, we look for collections of $\Gamma(a,b,c)$ that do not contain geometric lines. This is satisfied if there are no isosceles triangles of the form $(a+r,b,c+s)$, $(a,b+r+s,c)$, $(a+s,b,c+r)$. Again, we run a search over the $(n+2)(n+1)/2$ binary variables, with $\Gamma(a,b,c)$ weighted by $(a+b+c)!/(a!b!c!)$, to maximize the total number of points.