# Anurag Bishnoi, anurag.2357@gmail.com, ORCID http://orcid.org/0000-0003-0232-428X
# SAGE code for the paper titled ``On generalized hexagons of order (3, t) and (4, t) containing a subhexagon'' by Anurag Bishnoi and Bart De Bruyn
# run this code after running main.g, since it needs all the points, lines and automorphism groups of the point-line geometries
def read_lines_from_file(name):
"""
Read a file containing the lines of the geometry.
Args:
name -- the file name (each line of the file should have integers separated by a space)
Returns:
a list whose each element is a line of the geometry stored as a list of points incident to the line
"""
L = []
f = open(name, 'r')
for l in f.readlines():
l = l.split()
L.append([int(x) for x in l])
f.close()
return L
def read_group_from_file(name):
"""
Read a file containing the automorphism group of the geometry.
Args:
name -- the file name
Returns:
a GAP object that is the automorphism group of the geometry
"""
f = open(name, 'r')
s = f.read()
s = s.replace("\\","") # for some reason the groups written in the file using GAP contain these characters
f.close()
return gap(s)
def get_data(name):
"""
Get the necessary data regarding the geometry.
Args:
name -- the name of the geometry (H2, H2D, H3, etc.)
Returns:
a tuple of points, lines, automorphism group, collinearity graph, distance function
"""
lines = read_lines_from_file(name + "_lines")
G = read_group_from_file(name + "_group")
edges = []
for l in lines:
edges.extend(Combinations(l,2))
T = Graph(edges)
points = T.vertices()
D = T.distance_all_pairs()
return (points, lines, G, T, D)
def ovoids(P,L):
"""
Find all exact hitting sets, or 1-ovoids, in the hypergraph (geometry) using the Dancing Links algorithm.
Args:
P -- the vertices (points) of the hypergraph (geometry)
L -- the edges (lines) of the hypergraph (geometry)
Returns:
a list of all exact hitting sets (1-ovoids) in the hypergraph (geometry).
"""
map = dict()
for p in P:
map[p] = []
for i in range(len(L)):
for p in L[i]:
map[p].append(i)
E = [map[p] for p in P]
return list(DLXCPP(E))
def semi_singular_hyperplanes(points,lines, D, p):
"""
Computer all semi-singular hyperplanes of a point line geometry with a fixed point as center.
Args:
points -- a list of points
lines -- a list of lines
D -- the distance function of the collinearity graph
p -- the fixed point
Returns:
a list of all hyperplanes
"""
dist3 = [x for x in points if D[x][p] == 3]
L = [l for l in lines if any([x in dist3 for x in l])]
L = [[x for x in l if x in dist3] for l in L]
return [sorted([x for x in points if x in O or D[x][p] <= 1]) for O in list(ovoids(dist3,L))] # the hyperplanes are complements of the ovoids
# H(2)^D
points, lines, G, T, D = get_data("H2D")
print "Check H(2)^D: " + str(len(ovoids(points, lines)) == 0)
# H(2)
points, lines, G, T, D = get_data("H2")
p = points[0]
hyp_p = semi_singular_hyperplanes(points, lines, D, p)
dist3 = [x for x in points if D[x][p] == 3]
q = dist3[0] # an arbitrary point at distance 3 from points[0]
# It suffices to check intersection between all semi-singular hyperplane with center p and those with center q
hyp_q = semi_singular_hyperplanes(points, lines, D, q)
S = {len(set(x) & set(y)) for x in hyp_p for y in hyp_q} # intersection sizes
# print S
print "Check H(2): " + str(min(S) > 3)
# H(4)
points, lines, G, T, D = get_data("H4")
p = points[0]
hyp_p = semi_singular_hyperplanes(points, lines, D, p)
dist3 = [x for x in points if D[x][p] == 3]
q = dist3[0] # an arbitrary point at distance 3 from points[0]
hyp_q = semi_singular_hyperplanes(points, lines, D, q)
# S = {len(set(x) & set(y)) for x in hyp_p for y in hyp_q}
# print S
print "Check H(4): " + str(min(S) > 5)
# H(3)
points, lines, G, T, D = get_data("H3")
p = points[0]
ovoids_p = [O for O in ovoids(points, lines) if p in O]
hyp_p = semi_singular_hyperplanes(points, lines, D, p)
S = {len(set(x) & set(y)) for x in ovoids_p for y in hyp_p}
# print S
print "Check H(3): "+ str(min(S) > 3)