cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A352666 Maximum number of induced copies of the claw graph K_{1,3} in an n-node graph.

Original entry on oeis.org

0, 0, 0, 1, 4, 10, 20, 40, 70, 112, 176, 261, 372, 520, 704, 935, 1220, 1560, 1976, 2464, 3038, 3710, 4480, 5376, 6392, 7548, 8856, 10320, 11970, 13800, 15840, 18095, 20580, 23320, 26312, 29601, 33176, 37072, 41300, 45875, 50830, 56160, 61920, 68096, 74732
Offset: 1

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

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

Crossrefs

Cf. A271713.
Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352667 (paw graph), A352668 (diamond graph), A352669 (cycles).

Programs

  • 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))

A352667 Maximum number of induced copies of the paw graph in an n-node graph.

Original entry on oeis.org

0, 0, 0, 1, 4, 9, 18, 36, 60, 97, 152, 224
Offset: 1

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

Comments

The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to 3/8, the inducibility of the paw graph (Hirst 2014).
Assuming that the extremal graph is KK(j_1, j_2; k_1, k_2), as defined in the Example section below, for some j_1, j_2, k_1, k_2 (these graphs are asymptotically extremal), the sequence would continue as follows, with a(n) = (binomial(j_1,2)*j_2 + binomial(j_2,2)*j_1)*(k_1 + k_2) + (binomial(k_1,2)*k_2 + binomial(k_2,2)*k_1)*(j_1 + j_2).
n | a(n) | (j_1, j_2), (k_1, k_2)
|(conjectural)|
-------------------------------------------------------
13 316 (2,2), (4,5)
14 440 (2,2), (5,5)
15 590 (2,3), (5,5)
16 780 (3,3), (5,5)
17 1008 (2,3), (6,6), or (3,3), (5,6)
18 1296 (3,3), (6,6)
19 1620 (3,3), (6,7), or (3,4), (6,6)
20 2016 (3,3), (7,7), or (4,4), (6,6)
21 2478 (3,4), (7,7)
22 3024 (4,4), (7,7)
23 3632 (4,4), (7,8)
24 4352 (4,4), (8,8)
25 5152 (4,5), (8,8)
26 6080 (5,5), (8,8)
27 7100 (5,5), (8,9)
28 8280 (5,5), (9,9)
29 9558 (5,6), (9,9)
30 11016 (6,6), (9,9)
31 12600 (5,6), (10,10), or (6,6), (9,10)
32 14400 (6,6), (10,10)
33 16320 (6,6), (10,11), or (6,7), (10,10)
34 18480 (6,6), (11,11), or (7,7), (10,10)
35 20812 (6,7), (11,11)
36 23408 (7,7), (11,11)
37 26166 (7,7), (11,12)
38 29232 (7,7), (12,12)
39 32496 (7,8), (12,12)
40 36096 (8,8), (12,12)
41 39904 (8,8), (12,13)
42 44096 (8,8), (13,13)
43 48516 (8,9), (13,13)
44 53352 (9,9), (13,13)
45 58446 (9,9), (13,14)
46 64008 (9,9), (14,14)
47 69832 (9,10), (14,14)
48 76160 (10,10), (14,14)
49 82800 (9,10), (15,15), or (10,10), (14,15)
50 90000 (10,10), (15,15)
For n > 10, more than one optimal graph of the form KK(j_1, j_2; k_1, k_2) seem to exist exactly when n = 2*m^2 + i, where m >= 3 and i = -1, 1, or 2.

Examples

			All extremal graphs (i.e., n-node graphs having a(n) induced paw graphs) for 4 <= n <= 12 are listed below. Here, KK(j_1, j_2; k_1, k_2) denotes the complement of the disjoint union of K_{j_1, j_2} and K_{k_1, k_2}.
  n = 4: KK(0,1;1,2) (the paw graph);
  n = 5: KK(0,1;2,2) (the butterfly graph);
  n = 6: KK(0,1;2,3);
  n = 7: KK(0,1;3,3), KK(0,2;2,3), and KK(1,1;2,3);
  n = 8: KK(0,2;3,3) and KK(1,1; 3,3);
  n = 9: KK(0,2;3,4), KK(1,1;3,4), and KK(1,2;3,3);
  n = 10: KK(1,2;3,4);
  n = 11: KK(1,2;4,4);
  n = 12: KK(2,2;4,4).

Links

Crossrefs

Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352668 (diamond graph), A352669 (cycles).

Extensions

a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 05 2022

A352668 Maximum number of induced copies of the diamond graph K_{1,1,2} in an n-node graph.

Original entry on oeis.org

0, 0, 0, 1, 4, 12, 24, 48, 84, 138, 216, 324, 459, 636, 864, 1152, 1488, 1900, 2400, 3000, 3675, 4470, 5400, 6480, 7668, 9030, 10584, 12348, 14259, 16408, 18816, 21504, 24384, 27576, 31104, 34992, 39123, 43650, 48600, 54000, 59700, 65890, 72600, 79860, 87483, 95742
Offset: 1

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

Comments

The sequence (a(n)/binomial(n,4)) is decreasing for n >= 4 and converges to 72/125, the inducibility of the diamond graph (Hirst 2014).
It is known that there exists a complete multipartite optimal graph (i.e., an n-node graph with a(n) induced diamond graphs) for all n (Brown and Sidorenko 1994) and that a complete 5-partite graph is asymptotically optimal (Hirst 2014). For 3 <= n <= 7, the 3-partite Turán graph is optimal, and for 7 <= n <= 45, the 4-partite Turán graph is optimal. (For n = 7 both are optimal.) It appears that the 5-partite Turán graph is optimal for all n >= 46 (verified up to n = 75).

Links

Crossrefs

Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352667 (paw graph), A352669 (cycles).

Programs

  • Python
    from sympy.utilities.iterables import combinations,partitions
from sympy.combinatorics import IntegerPartition
f=lambda p:sum(q[0]*q[1]*q[2]*(q[0]+q[1]+q[2]-3)//2 for q in combinations(p,3)) # number of induced diamond graphs in the multipartite graph with parts of sizes given by p
def A352668(n):
    return max(f(IntegerPartition(p).partition) for p in partitions(n))

A352669 Maximum number of induced cycles in an n-node graph.

Original entry on oeis.org

0, 0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 225
Offset: 1

Views

Author

Pontus von Brömssen, Mar 26 2022

Keywords

Comments

For 3 <= n <= 11, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is the unique extremal graph, but a(12) = 225 > binomial(12,3), where the unique extremal graph is K_{6,6}.
Morrison and Scott (2017) prove that, for sufficiently large n (they say it ought to be true for n >= 30), a(n) = A276401(n), with the unique extremal graph being the empty cyclic braid graph with one cluster of size 4 if n == 1 (mod 3), one cluster of size 2 if n == 2 (mod 3), and all other clusters of size 3. (The empty cyclic braid graph is obtained by arranging clusters of nodes of the appropriate sizes in a cycle and joining all pairs of nodes in neighboring clusters with edges.) For 14 <= n <= 21, this graph is not extremal, because the balanced bipartite graph K_{floor(n/2),ceiling(n/2)} has A028723(n+1) > A276401(n) induced cycles.

Links

Crossrefs

Cf. A000292, A028723, A276401.
Maximum number of induced copies of other graphs: A028723 (4-node cycle), A111384 (3-node path), A352665 (4-node path), A352666 (claw graph), A352667 (paw graph), A352668 (diamond graph).

Extensions

a(10)-a(12) added using tinygraph by Falk Hüffner, Apr 07 2022
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.