Razborov Graphs

[thenealon]

Here's a constructor for some interesting graphs. Be warned, razborovGraphs(n) constructs an order n^5 graph.

constructs the order n^5 Razborov graph -- these have chromatic number >= Theta(n^4) and rank <= O(n^3); as such, they have superlinear chromatic-rank gap, disproving a sequence of conjectures.

Razborov AA, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Disc. Math. 108 (1992) pp393--396.

def razborovGraphs(n):
    #constructs the order n^5 Razborov graph -- these have chromatic number >= Theta(n^4) and rank <= O(n^3); as such, they have superlinear chromatic-rank gap, disproving a sequence of conjectures.
    #Razborov AA, The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear, Disc. Math. 108 (1992) pp393--396.
    B = FiniteEnumeratedSet([1..n])
    C=cartesian_product([B,B,B,B,B])
    G=graphs.EmptyGraph()
    for c in C:
        G.add_vertex(c)
    for a in C:
        for b in C:
            x=[]
            for i in [0..4]:
                if a[i]==b[i]:
                    x.append(0)
                else:
                    x.append(1)
            if not x in [[0,0,0,0,0],[1,1,1,0,0],[1,1,0,1,0],[1,1,0,0,1],[1,1,1,1,0],[1,1,1,0,1],[0,0,1,1,1]]:
                G.add_edge(a,b)
    return G

[math1um]

Code works. Let's do 3 examples:

razborov_2 = razborovGraphs(2)

razborov_3 = razborovGraphs(3)

razborov_4 = razborovGraphs(4)

[jaritaes99]

added function with Docstring and examples to graphs list