A355756 Triangle read by rows: A(n,k) is the intersection number of the Turán graph T(n,k), 1 <= k <= n.

0, 0, 1, 0, 2, 1, 0, 4, 2, 1, 0, 6, 4, 2, 1, 0, 9, 4, 4, 2, 1, 0, 12, 6, 4, 4, 2, 1, 0, 16, 9, 5, 4, 4, 2, 1, 0, 20, 9, 6, 5, 4, 4, 2, 1, 0, 25, 12, 9, 6, 5, 4, 4, 2, 1, 0, 30, 16, 9, 6, 6, 5, 4, 4, 2, 1

Offset: 1

Author

Pontus von Brömssen, Jul 16 2022

Keywords

• nonn
• tabl
• more

Examples

			Triangle begins:
  n\k | 1  2  3  4  5  6  7  8  9 10 11
  ----+--------------------------------
   1  | 0
   2  | 0  1
   3  | 0  2  1
   4  | 0  4  2  1
   5  | 0  6  4  2  1
   6  | 0  9  4  4  2  1
   7  | 0 12  6  4  4  2  1
   8  | 0 16  9  5  4  4  2  1
   9  | 0 20  9  6  5  4  4  2  1
  10  | 0 25 12  9  6  5  4  4  2  1
  11  | 0 30 16  9  6  6  5  4  4  2  1
		

Links

• Wikipedia, Intersection number
• Wikipedia, Turán graph

Crossrefs

Cf. A002620, A008133, A355754.

Programs

Python

from networkx import find_cliques,turan_graph
from itertools import combinations,count
def A355756(n,k):
    if k==1: return 0
    G=turan_graph(n,k)
    cliques=[sorted(c) for c in find_cliques(G)]
    ne=G.number_of_edges()
    for r in count(1):
        for c0 in combinations(cliques[1:],r-1):
            c=(cliques[0],)+c0
            if len(set().union(e for i in range(r) for e in combinations(c[i],2)))==ne:
                return r

Formula

A(n,1) = 0.

A(n,2) = floor(n^2/4) = A002620(n).

A(n,3) = floor((n+1)/3)*floor((n+2)/3) = A008133(n+1).

A(n,n-k) = A(2*k,k) for 2 <= k <= n/2.

A(n,n-1) = 2 for n >= 3.

A(n,n) = 1 for n >= 2.

A(n,k) >= floor((n+k-1)/k)*floor((n+k-2)/k) for k >= 2.