A006855 -id:A006855 - cp's OEIS frontend

A191965 A problem of Zarankiewicz: maximal number of 1's in a symmetric n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

0, 2, 6, 8, 12, 14, 18, 22, 26, 32, 36, 42, 48, 54, 60, 66, 72, 78, 84, 92, 100, 104, 112, 118, 126, 134, 142, 152, 160, 170, 180, 184, 192, 204, 212, 220, 226, 234, 244, 254

Offset: 1

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

In other words, the pattern
1...1
.....
1...1
is forbidden.
Such matrices are adjacency matrices of squarefree graphs (cf. A006786). The number of matrices with a(n) ones is given by A191966 and A335820 (up to permutations of rows/columns). - Max Alekseyev, Jan 29 2022

B. Bollobas, Extremal Graph Theory, pp. 309ff.

D. Bienstock E. Gyori, An extremal problem on sparse 0-1 matrices. SIAM J. Discrete Math. 4 (1991), 17-27.

Cf. A006786, A006855, A077269, A191873 A191874, A191966, A300756, A335820, A352472.

a(n) = 2 * A006855(n). - Max Alekseyev, Jan 29 2022

a(11)-a(40) computed from A006855 by Max Alekseyev, Jan 28 2022; Apr 02 2022; Mar 14 2023

A191966 Number of n X n symmetric (0,1) matrices that achieve the record mentioned in A191965.

Original entry on oeis.org

1, 1, 1, 12, 15, 900, 6615, 90720, 1995840, 1360800, 197920800, 359251200, 1297296000, 7264857600, 119870150400, 2615348736000, 29640619008000, 533531142144000, 101370917007360000, 101370917007360000, 425757851430912000, 3325168819675422720000

Offset: 1

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

nonn

Number of labeled squarefree graphs on n nodes with A006855(n) edges. - Max Alekseyev, Jan 29 2022

Max Alekseyev, Table of n, a(n) for n = 1..37

Labeled version of A335820. Rightmost values in A352472.

Cf. A006786, A006855, A077269, A191965, A300756.

a191966 = lambda n: sum( factorial(n) // g.automorphism_group(return_group=False, order=True) for g in graphs.nauty_geng(options=f'-c -f {n} {oeis(6855)(n)}:0') ) # Max Alekseyev, Jan 29 2022

a(11)-a(21) from Max Alekseyev, Jan 29 2022

Corrected and extended to a(37) by Max Alekseyev, Mar 12 2023

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

Original entry on oeis.org

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

N. J. A. Sloane, Jan 31 2012

nonn

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

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.

Cf. A006855.

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

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

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

A335820 Number of squarefree graphs on n nodes with maximal number of edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 5, 5, 10, 2, 11, 3, 2, 1, 2, 2, 1, 1, 5, 1, 1, 13, 1, 20, 9, 8, 7, 1, 2, 1, 1, 9, 18, 1, 1, 5, 11

Offset: 1

Jason Zimba, Jul 22 2020

Number of squarefree graphs on n nodes with A006855(n) edges.

			There are 2 squarefree graphs on 10 nodes that have maximal number of edges.

C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without Four-Cycles, Journal of Graph Theory, 31 (1989), 29-47.
D. B. West, A. Bialostocki, and J. Schonheim, E3387 (Large Graphs with No 4-cycle), The American Mathematical Monthly, 98 (Aug. - Sep. 1991), 653-655.

Unlabeled version of A191966.

Cf. A006786, A006855, A077269, A300756.

a(22)-a(37) from Brendan McKay, Mar 08 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

A352178 Let S = {t_1, t_2, ..., t_n} be a set of n distinct integers and consider the sums t_i + t_j (i

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 11, 13, 15, 17, 19, 21, 24, 26, 29, 31, 34, 36, 39, 41

Offset: 1

N. J. A. Sloane, Mar 07 2022

Given distinct integers t_1, ..., t_n, form a graph G with n vertices labeled by the t_i, and with an edge from t_i to t_j, labeled t_i + t_j, whenever t_i + t_j is a power of 2.
See the Pratt link for the best lower bounds known, and examples of sets achieving these bounds, for 1 <= n <= 100. - N. J. A. Sloane, Sep 26 2022
The following remarkable theorem is due to M. S. Smith (email of Mar 06 2022).
Theorem: G contains no 4-cycles.
Proof. Suppose the contrary, and assume the vertices t_1, t_2, t_3, t_4 form a 4-cycle, with edges labeled b_1 = t_1+t_2, b_2 = t_2+t_3, b_3 = t_3+t_4, b_4 = t_4+t_1. The b_i are powers of 2.
Since the t_i are distinct, b_1 != b_4, b_2 != b_1, b_3 != b_2, and b_4 != b_3.
We also have
   (*) b_1+b_3 = b_2+b_4 = t_1+t_2+t_3+t_4.
However, the powers of 2 form a Sidon set (all pairwise sums are distinct), so (*) implies that either b_1=b_2 and b_3=b_4 or b_1=b_4 and b_3=b_2, both of which are impossible. QED
Let c(n) = A006855(n) denote the maximum number of edges in a graph on n nodes containing no 4-cycle.
Corollary: a(n) <= c(n).
The values of c(n) agree with the lower bounds on a(n) for n <= 9 (see A347301), which establishes the first 9 values of a(n).
Another corollary is that a(n) is bounded asymptotically by (n/4)*(sqrt(4n-3)+1) (see A006855).
The theorem is remarkable, since before the only known values of a(n) were the trivial values for n <= 3.
In summary, we have a(n) >= A347301(n) for n >= 6, and
a(n) <= A006855(n) for all n.
From Thomas Scheuerle, Sep 23 2022: (Start)
Subgraphs of G consisting only of edges between positive numbers are free from any cycles. Proof: If  b + c = 2^t then either (b-1)XOR(c) or (b)XOR(c-1) will be 2^t-1. The properties of XOR allow in this case only a chain for Sidon sets. (XOR means bitwise exclusive or).
From this we can conclude that all cycles in the graph G must contain at least one negative number.
Conjecture A: The count of negative numbers in an optimal solution is either equal to the count of positive numbers or one less.
This leads to Conjecture B: a(n) <= floor((n+1)*3/2). (End)
Max Alekseyev points out that both conjectures are wrong.
(A)  Counterexamples are given by examples from A347301:
  a(12) = 19: {  -9, -7, -5, -3, -1, 1, 3,  5,  7,  9, 11, 13 }
  a(13) = 21: { -11, -7, -5, -3, -1, 1, 3,  5,  7,  9, 11, 13, 15 }
(B)  For n=14, this bound is 22, but it is smaller than a(14) = 24. N. J. A. Sloane, Sep 25 2022

			a(3) = 3 from S = {-1, 3, 5}.
a(4) >= 4 from S = {-3, -1, 3, 5}, a(4) <= A006855(4) = 4, so a(4) = 4.
a(5) >= 6 from S = {-3, -1, 3, 5, 11},  a(5) <= A006855(5) = 6, so a(5) = 6.
From _Thomas Scheuerle_, Sep 26 2022: (Start)
a(13): { -11, -7, -5, -3, -1, 1, 3,  5,  7,  9, 11, 13, 15 }
      13
      |
9-7-1-3-5-11
    |
    15  -> Four loose ends k = 4. Eight positive numbers p = 8.
a(13) = 21 < (p-1) + (n-p)*k
a(10): {-9, -5, -3, -1, 3, 5, 7, 9, 11, 13}
  13-3-5-11  7-9 -> Two times two loose ends k = 4. Six positive numbers p = 6.
a(10) = 15 < (p-1) + (n-p)*k
(End)

M. S. Smith, Email to N. J. A. Sloane, Mar 06 2022.

Max Alekseyev, On computing sets of integers with maximum number of pairs summing to powers of 2, arXiv:2303.02872 [math.CO], 2023.
Matthew Bolan, Stan Wagon 1321 Solution, Sep 22, 2022 [Shows that a(10) = 15]
Alex Bradley, Pairwise Powers of 2 Problem, Sep 22 2022 [Short proof that there do not exist four distinct numbers all of whose pairwise sums are powers of 2]
C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without four-cycles, J. Graph Theory 13 (1) (1989) 29-47
Charlotte Darroch, Comments on Stan Wagon's Powers of 2 Problem, Sep 22 2022
Christof Haase, Decidability of the Powers of Two Problem, Sep 22 2022
Péter Hajnal, Binary Numeration System with Alternating Signed Digits and Its Graph Theoretical Relationship, Algorithms (2024) Vol. 17, Art. No. 55. See p. 9.
Brady Haran and N. J. A. Sloane, Problems with Powers of Two, Youtube Numberphile Video, Sep 21 2022
Brady Haran and N. J. A. Sloane, STOP PRESS: Postscript to Problems with Powers of Two, Sep 21 2022
Noam Kimmel, Asymptotics (upper and lower bounds) for a(n)
Firas Melaih, On The OEIS Sequence A352178 [Shows a(10) = 15, a(12) < 21, and some impossibility results on the graphs]
Firas Melaih, a(11) = 17 [Proves a(11) = 17 from an uploaded paper]
Rob Pratt, The best lower bounds known for 1 <= n <= 100 as of Sep 25 2022 [Gives n, best lower bound known, and an example of an n-set achieving that bound]
Thomas Scheuerle, The best lower bounds known for 1 <= n <= 351 as of Sep 28 2022 [Gives n, best lower bound known, and an example of an n-set achieving that bound]
István Selek, A possible proof of the Powers of Two problem, Sep 22 2022 [A solution for the case n = 4 using linear algebra]
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences: An illustrated guide with many unsolved problems, Guest Lecture given in Doron Zeilberger's Experimental Mathematics Math640 Class, Rutgers University, Spring Semester, Apr 28 2022: Slides; Slides (an alternative source).
Stan Wagon, Problem of the Week 1321: Powers of Two, Apr 16 2021.

Cf. A006855, A347301, A357409.

a(n) <= (p-1) + (n-p)*k. k is the count of loose ends of the subgraphs of positive numbers. Subgraphs means here the biggest sets of positive numbers connected by sums which are equal to a power of two. There may be multiple such sets which are not interconnected directly. From observation it appears that a(n) <= (p-1) + (n-p)*(k-1) does hold in most cases. - Thomas Scheuerle, Sep 26 2022

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

a(10) from Matthew Bolan, Sep 22 2022 - see link. - N. J. A. Sloane, Sep 22 2022
Edited by N. J. A. Sloane, Sep 22 2022
a(12)-a(18) from Max Alekseyev, Sep 25 2022, Sep 29 2022
a(19)-a(20) from Max Alekseyev, Dec 02 2023
a(21) from Max Alekseyev, May 01 2024

A375619 a(n) is the largest integer such that there exists a simple graph with n vertices, a(n) edges, and no cycles of length 0 mod 4.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 11, 12, 14, 15, 17, 19, 20, 22, 23, 25, 26, 28, 30, 31, 33, 34, 36, 38, 39, 41, 42, 44, 45, 47, 49, 50, 52, 53, 55, 57, 58, 60, 61, 63, 64, 66, 68, 69, 71, 72, 74, 76, 77, 79, 80, 82, 83, 85, 87, 88, 90, 91, 93, 95, 96, 98, 99, 101, 102

Offset: 1

Luc Ta, Aug 21 2024

In the parlance of extremal graph theory, a(n) is the extremal number ex(n, C_(0 mod 4)).

			For n = 4, any simple graph with 4 vertices and 5 edges contains a cycle of length 4 == 0 (mod 4), so a(4) < 5. There are exactly two nonisomorphic graphs with 4 vertices and 4 edges. One of them has no cycles of any length other than 3, so a(4) = 4.

Luc Ta, Table of n, a(n) for n = 1..10000
Ervin Győri, Binlong Li, Nika Salia, Casey Tompkins, Kitti Varga, and Manran Zhu, On graphs without cycles of length 0 modulo 4, arXiv: 2312.09999 [math.CO], 2023.
Index entries for sequences related to graphs

Cf. A172272, A056576, A006855, A000066, A345248, A006184.

Mathematica
```
Table[Floor[19/12 * (n - 1)], {n, 100}]
```

a(n) = floor(19/12(n-1)). See Győri et al. in Links.
a(n) = A172272(n-1) for all n <= 77; then a(78) = 121 != 122 = A172272(77).
a(n) = A056576(n-1) for all n <= 53; then a(54) = 83 != 84 = A056576(53).

cp's OEIS Frontend

A191965 A problem of Zarankiewicz: maximal number of 1's in a symmetric n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A191966 Number of n X n symmetric (0,1) matrices that achieve the record mentioned in A191965.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Sage

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A335820 Number of squarefree graphs on n nodes with maximal number of edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A352178 Let S = {t_1, t_2, ..., t_n} be a set of n distinct integers and consider the sums t_i + t_j (i

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A375619 a(n) is the largest integer such that there exists a simple graph with n vertices, a(n) edges, and no cycles of length 0 mod 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula