Timeline for Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2023 at 9:14 | comment | added | Emil Jeřábek | On second thought, the paths from $v_p$ to $y$ are not needed at all; one can just include edges from all but one vertex of each cycle to $y$. I see that this was meanwhile used in YCor’s answer. So it’s really $2+{}$ the sum of lengths of the cycles. | |
| Nov 22, 2023 at 8:33 | history | edited | domotorp | CC BY-SA 4.0 |
added update
|
| Nov 22, 2023 at 8:29 | comment | added | Aleksei Kulikov | I completely forgot that I've answered a related question some 5 years ago here ... The number of possible sets is of course at most $2^N$, but it is also bounded by $\exp(\sqrt{N\log (N)}(1+o(1))$ (in fact, by the Landau function plus a tiny error). So, the example of @EmilJeřábek is almost optimal. | |
| Nov 22, 2023 at 8:19 | comment | added | Emil Jeřábek | You can get paths of length $1,\dots,p-1$ from $v_p$ to $y$ using just $p-2$ vertices (other than $v_p$ and $y$). Just take a path of length $p-1$, and include edges from $v_p$ to all other vertices on the path. This reduces the size of the graph to $O\bigl(\sum_{p\le N}p\bigr)$. | |
| Nov 22, 2023 at 8:17 | comment | added | Aleksei Kulikov | For your last question, $2^N$ is enough -- consider, for each $k$, the set of points which are reachable from $x$ in exactly $k$ moves. There are $2^N$ different sets, so they are eventually periodic before $2^N$'th step, and if in every one of them we had $y$, then $y$ will be every time afterwards. Your example is something like $\exp(\sqrt[3]{N})$, but we can improve it to $\exp(\sqrt{N})$ by treating all the paths of length $s$ coming from different $v_p$'s as the same path. So we are between $\exp(\sqrt{N})$ and $\exp(N)$, not too close, but not too far either. | |
| Nov 22, 2023 at 4:10 | history | edited | Michael Hardy | CC BY-SA 4.0 |
added 2 characters in body
|
| Nov 22, 2023 at 0:13 | comment | added | YCor | Variant with 9 vertices: $x,v_2,v_5,y$. Write the cycle $v_2$ as $b_0,b_1$, and the cycle $v_5$ as $c_0,\dots,c_4$. Join $x\to y$, $x\to b_0$, $b_1\to y$, $x\to c_0$, $c_i\to y$ for $i\neq 3$ (and the cycles, i.e. $b_0\to b_1\to b_0$, $c_0\to c_1\to\dots\to c_4\to c_0$). Then for $m\ge 0$ there is a path from $x$ to $y$ of length $m$ iff $m$ is nonzero modulo $10$. | |
| Nov 21, 2023 at 23:51 | comment | added | YCor | Or even better, $n=12$ with choosing $p=3,4$, and the following trick: identify the middle vertex in the length 2 arrows from $v_3$ and $v_4$. | |
| Nov 21, 2023 at 23:47 | comment | added | YCor | If I'm correct the smallest $n$ for which this yields counterexamples is $n=20$. Namely for $n=20$, take for $p$ the numbers $4$, $5$ only ($p$ prime doesn't matter, coprime is the point). This gives $20$ vertices ($x$, $y$, the $4$-loop, the $5$-loop, $0+1+2$ more vertices for arrows from $v_4$, $0+1+2+3$ more for the arrows from $v_5$), while the first forbidden length is $21=4\times 5+1$. | |
| Nov 21, 2023 at 22:23 | history | answered | domotorp | CC BY-SA 4.0 |