OFFSET
1,5
COMMENTS
The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to 1/2, the inducibility of the claw graph.
Brown and Sidorenko (1994) prove that a bipartite optimal graph (i.e., an n-node graph with a(n) induced claw graphs) exists for all n. For n >= 2, the size k of the smallest part of an optimal bipartite graph K_{k,n-k} is one of the two integers closest to n/2 - sqrt(3*n/4-1), and a(n) = binomial(k,3)*(n-k) + binomial(n-k,3)*k. Both are optimal if and only if n is in A271713. For 7 <= n <= 10 (and, trivially, n = 3), the tripartite graph K_{1,1,n-2} is also optimal.
LINKS
Jason I. Brown and Alexander Sidorenko, The inducibility of complete bipartite graphs, Journal of Graph Theory 18 (1994), 629-645.
PROG
(Python)
from math import comb, isqrt
def A352666(n):
if n <= 1: return 0
r = isqrt(3*n-4)
k0 = (n-r-1)//2
return max(comb(k, 3)*(n-k)+comb(n-k, 3)*k for k in (k0, k0+1))
CROSSREFS
KEYWORD
nonn
AUTHOR
Pontus von Brömssen, Mar 26 2022
STATUS
approved