A350189 -id:A350189 - cp's OEIS frontend

A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.

1, 3, 6, 9, 12, 16, 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115, 122

Offset: 1

Xuli Le (leshlie(AT)eyou.com), Jun 21 2002

Proving a(13) < 53 and finding a(7) were problems at the 1975 USSR National Olympiad and are presented in the Ross Honsberger 1985 book "Mathematical Gems III" (see links). - Tanya Khovanova, Oct 12 2007
The growth rate of a(n) is O(n^{3/2}). For a lower bound, take the incidence graph of a finite projective plane. For prime powers q, you get a(q^2+q+1) >= (q+1)(q^2+q+1). For an upper bound, the matrix is an adjacency matrix of a bipartite graph of girth 6. These have at most O(n^{3/2}) edges. - Peter Shor, Jul 01 2013
Conjecture: the same number of 1s is achieved for symmetric n X n matrices (cf. A350189). - Max Alekseyev, Apr 03 2022

			Examples of a(2)=3, a(3)=6, and a(4)=9:
11   110   1110
10   101   1001
     011   0101
           0011
a(4)=9 is also achieved at a symmetric matrix:
0111
1010
1100
1001 - _Max Alekseyev_, Apr 03 2022

Brendan McKay's Largest graphs of girth at least 6, MathOverflow, 2012. [The number of edges given there for even n seem to be the terms of this sequence. They are certainly bounded above by them.]
Stefan Neuwirth, The size of bipartite graphs with girth eight, arXiv:math/0102210 [math.CO], 2001.
I. Reiman, Über ein Problem von K. Zarankiewicz, Acta Mathematica Academiae Scientiarum Hungarica, Volume 9, Issue 3-4 , pp 269-273.
R. Honsberger, Two Problems from the 1974 USSR National Olympiad (#4 and #9). Excerpt from "Mathematical Gems III" book, 1985. [In fact, these problems are from the olympiad of 1975, not 1974, and were published as Problem M335 in Kvant 7 (1975).]
E. Belaga, Solution to Problem M335, Kvant 3 (1976), 42-44. (in Russian)

Cf. A001197.

For prime powers q, a(q^2+q+1) = (q+1)(q^2+q+1). It follows from equality case of Reiman inequality. For example, a(21)=105 and a(31)=186. - Senya Karpenko, Jul 23 2014

a(n) = A001197(n) - 1 for n>=2. - Rob Pratt, Aug 09 2019

a(1) = 1 from Don Reble, Oct 13 2007
More terms (using formula and A001197) from Rob Pratt, Aug 09 2019
a(22)-a(24) from Jeremy Tan, Jan 23 2022
Edited by Max Alekseyev, Apr 03 2022

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 12, 1, 10, 45, 120, 195, 162, 15, 1, 15, 105, 455, 1320, 2508, 2680, 900, 1, 21, 210, 1330, 5880, 18564, 40474, 54750, 35595, 6615, 1, 28, 378, 3276, 20265, 93240, 320040, 795120, 1333080, 1323840, 619920, 90720, 1, 36, 630, 7140, 58527, 364896

Offset: 1

R. J. Mathar, Mar 17 2022

Symmetry and traceless mean that the number of 1's is always even; the corresponding zeros for odd numbers are not shown here.

			The triangle starts at 1 X 1 matrices and 0,2,4,... ones as
1: 1;
2: 1  1;
3: 1  3   3    1;
4: 1  6  15   20    12;
5: 1 10  45  120   195    162      15;
6: 1 15 105  455  1320   2508    2680     900;
7: 1 21 210 1330  5880  18564   40474   54750    35595     6615;
8: 1 28 378 3276 20265  93240  320040  795120  1333080  1323840   619920    90720;
9: 1 36 630 7140 58527 364896 1763076 6578640 18514935 37535932 50808870 40684140 15892065 1995840;

Max Alekseyev, Table of n, a(n) for n = 1..205
Index entries for sequences of squarefree graphs

Cf. A350189 (allows nonzero trace), A345249 (row sums), A006855 (row lengths minus 1), A191966 (rightmost values).

T(n,1) = A000217(n-1). - R. J. Mathar, Mar 25 2022
T(n,2) = 3*A000332(n+1). T(n,3) = A093566(n+1). - Conjectured by R. J. Mathar, Mar 25 2022; proved by Max Alekseyev, Apr 02 2022
G.f.: F(x,y) = Sum_{n,k} T(n,k)*(x^n/n!)*y^k = exp( Sum_G x^n(G) * y^e(G) / |Aut(G)| ), where G runs over the connected squarefree graphs (cf. A077269), n(G) and e(G) are the numbers of nodes and edges in G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + (1/2)*x^2*y + ((1/2)*x^3 + (1/8)*x^4)*y^2 + ((1/6)*x^3 + (2/3)*x^4 + (1/4)*x^5 + (1/48)*x^6)*y^3 + O(y^4)), implying the above formulas for T(n,2) and T(n,3). - Max Alekseyev, Apr 02 2022

A352258 Number of symmetric binary n X n matrices with no 2 X 2 submatrix of all 1s.

Original entry on oeis.org

2, 7, 42, 399, 5614, 112221, 3102020, 116076057, 5774524092, 376068483351, 31643635513816, 3401292647423655, 462391295351625128, 78801283167350942685, 1775935516860530625139, 230933325874558862792569

Offset: 1

Brendan McKay, Mar 09 2022

Equivalently, the number of labeled graphs (loops but not multiple edges allowed) with none of these subgraphs: 4-cycle, edge with a loop on each end, triangle with at least one loop.

Row sums of A350189.

Cf. A345249 (traceless matrices).

A352801 Number of symmetric n X n 01-matrices with maximum number of 1s and no 2 X 2 all-1 submatrix.

Original entry on oeis.org

1, 1, 2, 4, 16, 170, 360, 840, 82320, 181440, 1512000, 19958400, 79833600, 259459200, 14529715200

Offset: 0

Max Alekseyev, Apr 03 2022

Cf. A072567, A191874, A191966, A335820, A350189, A351335, A352258.

a(n) is the last element in the n-th row of triangle A350189.

Conjecture: the maximum number of 1s equals A072567(n), and so a(n) = A350189(n, A072567(n)).

cp's OEIS Frontend

A072567 A variant of Zarankiewicz problem: maximal number of 1s in n X n 01-matrix with no four 1s forming a rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A352258 Number of symmetric binary n X n matrices with no 2 X 2 submatrix of all 1s.

Views

Author

Keywords

Comments

Crossrefs

A352801 Number of symmetric n X n 01-matrices with maximum number of 1s and no 2 X 2 all-1 submatrix.

Views

Author

Keywords

Crossrefs

Formula