Turán's brick factory problem

Written By Michael Breen-McKay

As one of the first edge crossing problems in graph theory, Turán’s brick factory problem asks a fairly simple question: Given a complete bipartite graph arrange the vertices on the plane so as to minimized the number of edge crossings.

We assume our edges are straight line segments and that no vertex lies on an edge unless it is an endpoint of that edge. It is conjectured that a positioning strategy of Zarankiewicz achieves the minimum. K4,7 is shown in the picture below.

I thought it would be interesting to write a small bit of python code to search for a counterexample to this conjecture. We know that if a counterexample exists than it first occurs when both n and m are odd for Kn,m, and that n, m > 7. 

import sys
import numpy as np
import random
import math
import matplotlib.pyplot as plt



A = 11
B = 11

edges = []
for i in range(A):
    for j in range(B):
        edges.append([i,j])



def assignRand(A,B):
    allTuples = []
    Atuples = []
    Btuples = []
    while len(Atuples) < A:
        for i in range(A):
            rand = (random.randint(0,1000),random.randint(0,1000))
            if rand not in allTuples:
                Atuples.append(rand)
                allTuples.append(rand)
    
    while len(Btuples) < B:
        for i in range(B):
            rand = (random.randint(0,1000), random.randint(0,1000))
            if rand not in allTuples:
                Btuples.append(rand)
                allTuples.append(rand)
                
    return(Atuples,Btuples)
    

def ccw(A,B,C):
    return (C[1]-A[1]) * (B[0]-A[0]) > (B[1]-A[1]) * (C[0]-A[0])

# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
    return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
    

    
def checkCrossings(Atuples,Btuples,edges):
    crossings = 0
    for i in range(0,len(edges)):
        for j in range(i+1,len(edges)):
            if edges[i][0] == edges[j][0]:
                continue
            if edges[i][1] == edges[j][1]:
                continue
            Ax1 = Atuples[edges[i][0]][0]
            Ay1 = Atuples[edges[i][0]][1]
            Ax2 = Atuples[edges[j][0]][0]
            Ay2 = Atuples[edges[j][0]][1]
            Bx1 = Btuples[edges[i][1]][0]
            By1 = Btuples[edges[i][1]][1]
            Bx2 = Btuples[edges[j][1]][0]
            By2 = Btuples[edges[j][1]][1]
            if Bx1 - Ax1 != 0:
                slope1 = (By1 - Ay1)/(Bx1 - Ax1)
            else:
                slope1 = None
            if Bx2 - Ax2 != 0:
                slope2 = (By2 - Ay2)/(Bx2 - Ax2)
            else:
                slope2 = None
            if (Bx1 - Ax1) == 0 and (Bx2 - Ax2) == 0:
                continue
            if slope1 is not None and slope2 is not None:
                if slope1 == slope2:
                    continue
            crossings += intersect([Ax1,Ay1],[Bx1,By1],[Ax2,Ay2],[Bx2,By2])
            
            
            
    return crossings
    
target = math.floor(A/2)*math.floor((A-1)/2)*math.floor(B/2)*math.floor((B-1)/2)
test = assignRand(A,B)
print("Target: " + str(target))

iterations = 5000
currBestTuples = []
count = 0
test = assignRand(A,B)
currBest = checkCrossings(test[0],test[1],edges)
while count < iterations:
    group = random.randint(0,1)
    choice = random.randint(0,8)
    newCoord = (random.randint(0,1000),random.randint(0,1000))
    if newCoord in test[0]:
        continue
    if newCoord in test[1]:
        continue
    oldCoord = test[group][choice]
    test[group][choice] = newCoord
    count += 1
    crossings = checkCrossings(test[0],test[1],edges)
    if crossings < currBest:
        print(crossings)
        currBest = crossings
        currBestTuples = []
        currBestTuples.append(test[0])
        currBestTuples.append(test[1])
    else:
        test[group][choice] = oldCoord
        
xa = [i[0] for i in test[0]]
ya = [i[1] for i in test[0]]
xb = [i[0] for i in test[1]]
yb = [i[1] for i in test[1]]
x = xa+xb
y = ya+yb
colors1 = ["blue"]*A
colors2 = ["red"]*B
colors = colors1 + colors2
fig, ax = plt.subplots()
ax.scatter(x,y,c=colors,vmin=0,vmax=1000)
plt.show()
print(currBestTuples)

Running the code we see that our positioning that minimizes the crossings tends towards the Zarankiewicz pattern. In the future I plan to implement a machine learning algorithm schema as well.

Michael Breen-McKay