Raghavendra Tripathi - cp's OEIS frontend

User: Raghavendra Tripathi

Raghavendra Tripathi has authored 2 sequences.

A381896 Number of n X n Erdős matrices up to equivalence.

1, 2, 6, 41

Offset: 1

Raghavendra Tripathi, Mar 09 2025

An n X n bistochastic matrix A is Erdős if Sum_{i=1..n} Sum_{j=1..n} A(i, j)^2 = max_{p in S_n} Sum_{i=1..n} A(i, p(i)), where S_n is the set of all permutations of [n]. It is known that any bistochastic matrix satisfies the inequality Sum_{i=1..n} Sum_{j=1..n} A(i, j)^2 <= max_{p in S_n} Sum_{i=1..n} A(i, p(i)).
Two Erdős matrices A and B are equivalent if A=PBQ for some permutation matrices P and Q.
The n-th term in the sequence a(n) >= p(n), where p(n) is the number of partitions of n [Tripathi, 2024].

			When n=1, there is only one bistochastic matrix, namely [1], which is clearly Erdős. This gives a(1)=1.
When n=2, there are only 3 Erdős matrices, namely [1, 0; 0, 1], [1/2, 1/2; 1/2, 1/2], and [0, 1; 1, 0]. Since [1, 0; 0, 1] and [0, 1; 1, 0] are equivalent, it follows that a(2)=2.
When n=3, there are only 6 Erdős matrices up to equivalence. This was shown by Bouthat, Mashreghi, and Morneau-Guérin in 2024. Here is a list of 6 non-equivalent Erdős matrices in dimension 3:
   [1, 0, 0; 0, 1, 0; 0, 0, 1],
   [1/3, 1/3, 1/3; 1/3, 1/3, 1/3; 1/3, 1/3, 1/3],
   [1, 0, 0 ; 0, 1/2, 1/2; 0, 1/2, 1/2],
   [0 , 1/2, 1/2; 1/2, 1/4, 1/4; 1/2, 1/4, 1/4],
   [0, 1/2, 1/2; 1/2, 0, 1/2; 1/2, 1/2, 0],
   [3/5, 0, 2/5; 0, 3/5, 2/5; 2/5, 2/5, 1/5]
A complete list 41 of non-equivalent Erdős matrices in dimension 4 was obtained by Kushwaha and Tripathi.

Ludovick Bouthat, Javad Mashreghi, and Frédéric Morneau-Guérin, On a question of Erdős on doubly stochastic matrices, Linear and Multilinear Algebra, Vol 72, (17) 2024, 2823-2844; arXiv preprint arXiv:2306.05518 [math.MG], 2023.
Aman Kushwaha and Raghavendra Tripathi, A note on Erdős matrices and Marcus--Ree inequality, arXiv:2503.09542 [math.MG], 2025.
Raghavendra Tripathi, Some observations on Erdős matrices, Linear Algebra and its Applications, Vol 708, 2025, 236-251; arXiv preprint arXiv:2410.06612 [math.MG], 2024.

Cf. A000041.

A381842 Triangle read by rows: T(n,k) is the number of non-equivalent subsets of size k in S_n, 0 <= k <= n!.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 4, 10, 41, 103, 309, 691, 1458, 2448, 3703, 4587, 5050, 4587, 3703, 2448, 1458, 691, 309, 103, 41, 10, 4, 1, 1, 1, 1, 6, 37, 715, 13710, 256751, 4140666, 58402198, 726296995, 8060937770, 80604620206, 732149722382

Offset: 0

Raghavendra Tripathi, Mar 09 2025

We say two subsets A, B of size k are equivalent if there are permutations p, q in S_n such that pAq=B.

The n-th row contains n! + 1 entries corresponding to subsets of S_n of size 0 to n!.

			Triangle begins:
  [0] 1, 1;
  [1] 1, 1;
  [2] 1, 1, 1;
  [3] 1, 1, 2, 2, 2, 1, 1;
  [4] 1, 1, 4, 10, 41, 103, 309, 691, 1458, 2448, 3703, 4587, 5050, ...;

Andrew Howroyd, Table of n, a(n) for n = 0..880 (rows 0..6)
Aman Kushwaha and Raghavendra Tripathi, A note on Erdős matrices and Marcus-Ree inequality, arXiv:2503.09542 [math.MG], 2025. See p. 12.

Cf. A000041, A362763 (up to conjugation).

T(n, 1) = 1.
T(n, 2) = A000041(n) - 1.
T(n, k) = T(n, n!-k).

a(39) onwards from Andrew Howroyd, Mar 09 2025

cp's OEIS Frontend

User: Raghavendra Tripathi

A381896 Number of n X n Erdős matrices up to equivalence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs