number of dense symmetric binary relations on {1,...,n} (A382693)

[Mark Bowron]

A binary relation R on {1,...,n} is "dense" iff:

(zRx implies zRy for all z) implies (x <= y).

For n = 1 to 6 my C program gives:

2, 4, 20, 234, 6308, 374586

Is this worth submitting?  (Seems like I already did, but I'm not 100% sure.)

I didn't detect a pattern in the adjacency matrices.

Mark

P.S. The condition above is called "density" at the top of p. 10 in this recent paper:

http://logicandanalysis.org/index.php/jla/article/view/514

[Charles Greathouse]

I would submit it and cite the paper (unless it cites another paper for the concept and you can find a copy).

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/e5ebb883-78d4-4326-bf0c-2f61f541f475n%40googlegroups.com.

[Brendan]

If I understand the definition, it counts binary matrices R(i,j) such that

for all j < j', there is some i for which R(i,j)=0 and R(i,j')=1.

Did I get that right?  It is certainly OEIS-worthy.

B/

--

[D. S. McNeil]

Definitely a nice sequence.  FWIW via brute force I match your numbers, and propose a(7)=47740076 and a(8)= 12788143462.

Doug

On Fri, Apr 4, 2025 at 4:09 PM Mark Bowron <mathema...@gmail.com> wrote:

--

[Mark Bowron]

For n = 2,3,4 on a computer I got precisely the same symmetric matrices that my density condition yields, so yes, the two conditions are apparently equivalent in general.

[Mark Bowron]

After posting here yesterday I noticed that a symmetric binary relation R is "dense" according to Wikipedia iff for all x,y we have

xRy implies (zRx and zRy for some z).   https://en.wikipedia.org/wiki/Dense_order#Generalizations

I found the original source for my "density" condition (a 2010 paper cited by the one I mentioned), so I will cite that in my OEIS submission.

[Mark Bowron]

Great!  Will include these values with attribution in my submission.

[Brendan]

Wait, your original post did not mention "symmetric".   Brendan.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/71b1e745-8b5e-4128-ad8b-f28e241bc92dn%40googlegroups.com.

[Mark Bowron]

The title states it, but I should have repeated it in the post.

This 2010 paper (Definition 2.1 on second page) appears to be where this type of "density" was introduced:

https://doi.org/10.1016/j.jpaa.2010.02.002

Within the confines of the "overlap" relation it always appears together with symmetry.

I stumbled on the sequence by mistake while coding the overlap relation in C.  I absentmindedly wrote the condition "x > y" (under the usual order) to represent "not x <= y" (under a general partial order <=).  When I didn't detect a pattern in the erroneously-generated output, I checked the OEIS for clues.

Mark

[Brendan]

Yes, indeed I missed the "symmetric" in the title.

The same definition without the requirement of symmetry is also interesting and OEIS-worthy.

B/

To view this discussion visit https://groups.google.com/d/msgid/seqfan/83441816-9601-452a-b38a-3ed74c601b1bn%40googlegroups.com.

[Mark Bowron]

OK I'll submit that one too.  Computing two ways---one with density and the other with your equivalent condition---produces 2, 7, 114, 9602, 3962940 for n = 1 to 5.  The symmetric version brings up several advanced matches, all of which look unrelated to density; this sequence brings up no advanced matches at all.  M.

[Brendan]

I agree with 2, 7, 114, 9602, 3962940 and continue with 7516789560, 62622777447552 .

The main improvement was to make only matrices with the rows in lexicographic order and

apply a multiplier to each solution according to the counts of equal rows.  The next value

is probably around 2 x 10^18 and would take too long with my code.

Brendan.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/6d0847b9-18e4-44fe-86c0-dfe69864076dn%40googlegroups.com.

[Mark Bowron]

I added these two values to the OEIS sequence (A382839).