cp's OEIS Frontend

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

%I A355756 #8 Jul 18 2022 19:29:58
%S A355756 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,
%T A355756 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,
%U A355756 1
%N A355756 Triangle read by rows: A(n,k) is the intersection number of the Turán graph T(n,k), 1 <= k <= n.
%H A355756 Wikipedia, <a href="https://en.wikipedia.org/wiki/Intersection_number_(graph_theory)">Intersection number</a>
%H A355756 Wikipedia, <a href="https://en.wikipedia.org/wiki/Turán_graph">Turán graph</a>
%F A355756 A(n,1) = 0.
%F A355756 A(n,2) = floor(n^2/4) = A002620(n).
%F A355756 A(n,3) = floor((n+1)/3)*floor((n+2)/3) = A008133(n+1).
%F A355756 A(n,n-k) = A(2*k,k) for 2 <= k <= n/2.
%F A355756 A(n,n-1) = 2 for n >= 3.
%F A355756 A(n,n) = 1 for n >= 2.
%F A355756 A(n,k) >= floor((n+k-1)/k)*floor((n+k-2)/k) for k >= 2.
%e A355756 Triangle begins:
%e A355756   n\k | 1  2  3  4  5  6  7  8  9 10 11
%e A355756   ----+--------------------------------
%e A355756    1  | 0
%e A355756    2  | 0  1
%e A355756    3  | 0  2  1
%e A355756    4  | 0  4  2  1
%e A355756    5  | 0  6  4  2  1
%e A355756    6  | 0  9  4  4  2  1
%e A355756    7  | 0 12  6  4  4  2  1
%e A355756    8  | 0 16  9  5  4  4  2  1
%e A355756    9  | 0 20  9  6  5  4  4  2  1
%e A355756   10  | 0 25 12  9  6  5  4  4  2  1
%e A355756   11  | 0 30 16  9  6  6  5  4  4  2  1
%o A355756 (Python)
%o A355756 from networkx import find_cliques,turan_graph
%o A355756 from itertools import combinations,count
%o A355756 def A355756(n,k):
%o A355756     if k==1: return 0
%o A355756     G=turan_graph(n,k)
%o A355756     cliques=[sorted(c) for c in find_cliques(G)]
%o A355756     ne=G.number_of_edges()
%o A355756     for r in count(1):
%o A355756         for c0 in combinations(cliques[1:],r-1):
%o A355756             c=(cliques[0],)+c0
%o A355756             if len(set().union(e for i in range(r) for e in combinations(c[i],2)))==ne:
%o A355756                 return r
%Y A355756 Cf. A002620, A008133, A355754.
%K A355756 nonn,tabl,more
%O A355756 1,5
%A A355756 _Pontus von Brömssen_, Jul 16 2022