[seqfan] Re: Max no. of edges in graph with no 4-cycles

Richard J. Mathar mathar at mpia-hd.mpg.de
Tue Mar 8 17:26:56 CET 2022


Related to A006855 I stumbled across the Erd"os-Kleitman paper
https://doi.org/10.1090/S0002-9939-1971-0270924-9
"On collections of subsets containing no 4-member boolean algebra"
Proc. Am. Math. Soc. 28 (1) (1971) page 87
I'm trying to count the number of symmetric binary (with entries of {0,1})
nXn matrices which have no 2x2 submatrix with all 4 entries =1.
For n=1,2,3,.. I get
2,
7,
42,
399,
5614
112221
3102020
116076057
which is not in the OEIS. Can anyone confirm these (and submit
the known terms)?
If the requirement on the 2x2 submatrices is dropped, all
symmetric binary matrices are counted, which is 2^(n*(n+1)/2)),
because there are n*(n+1)/2 independent elements in the (upper or lower)
triangular submatrix.

See perhaps also A350296, A350304.
This is also weakly related to A350237

Best regards, Richard Mathar



More information about the SeqFan mailing list