A205805 Maximum number of edges in a squarefree bipartite graph on n vertices.

0, 1, 2, 3, 4, 6, 7, 9, 10, 12, 14, 16, 18, 21, 22, 24, 26, 29, 31, 34, 36, 39, 42, 45, 48, 52, 53, 56, 58, 61, 64, 67, 70, 74, 77, 81, 84, 88, 92, 96, 100, 105, 106, 108, 110, 115, 118, 122, 126, 130, 134, 138, 142, 147, 151, 156, 160, 165, 170, 175, 180, 186, 187

Offset

1,3

Comments

Zarankiewicz number z(n; C_4).

The corresponding extremal graphs for n in {1, 2, 6, 14, 26, 28, 42, 46, 62} are regular and unique. The extremal graphs for n = 16 consist of a regular graph and three other graphs. - Max Alekseyev, Mar 14 2023

Links

Table of n, a(n) for n=1..63.

Wayne Goddard, Michael A. Henning, and Ortrud R. Oellermann, Bipartite Ramsey numbers and Zarankiewicz numbers, Discrete Math. 219 (2000), no. 1-3, 85-95.

Brendan McKay, Extremal Graphs and Turan numbers.

Formula

For n > 2, a(n) <= floor( a(n-1)*n/(n-2) ). - Max Alekseyev, Mar 09 2023

Crossrefs

Cf. A006855.

Sequence in context: A248635 A171511 A225819 * A246372 A006254 A111333

Adjacent sequences: A205802 A205803 A205804 * A205806 A205807 A205808

Keyword

nonn

Author

N. J. A. Sloane, Jan 31 2012

Extensions

a(21)-a(45) from Max Alekseyev, Mar 13 2023

a(46)-a(63) from Brendan McKay, communicated by Max Alekseyev, Mar 14 2023

Status

approved