Timeline for Given any finite relation $R$ what is the cardinality of $\langle R\rangle=\{\underbrace{R\circ R\cdots \circ R}_{n\text{ times}}:n\in\mathbb{N}\}$?
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 27, 2018 at 2:45 | comment | added | LSpice | Surely your $\langle R\rangle$ should be $\bigcup_{n = 0}^\infty R^{\circ n}$, not $\{R^{\circ n} : n \in \mathbb Z_{\ge0}\}$? | |
| Nov 24, 2018 at 10:38 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
added 9 characters in body
|
| Nov 21, 2018 at 0:22 | vote | accept | Ethan Splaver | ||
| Nov 13, 2018 at 16:56 | comment | added | Ale De Luca | I meant $\langle R\rangle$ of course, not $|R|$… | |
| Nov 13, 2018 at 9:46 | comment | added | Ale De Luca | Not useful for a solution, but: if I'm not mistaken, $|R|$ is the transitive closure of $R$ (or if $0\in\mathbb N$ for you, its reflexive and transitive closure), and is often denoted $R^+$ (resp. $R^*$) in the context of semigroup and formal language theory. | |
| Nov 12, 2018 at 18:41 | history | edited | YCor |
edited tags
|
|
| Nov 12, 2018 at 17:04 | answer | added | Aleksei Kulikov | timeline score: 6 | |
| Nov 12, 2018 at 14:29 | history | edited | YCor |
edited tags
|
|
| Nov 12, 2018 at 10:39 | comment | added | Aleksei Kulikov | Actually, this question true domain is the realm of finite automata! I asked specialist in my University who happens to be nearby and he pointed me to the following article of Chrobak and, more importantly, Chrobak’s normal form, which, I believe, gives us that the correct asymptotic is indeed $\exp(\Theta(\sqrt{R\log R}))$ (ac.els-cdn.com/0304397586901428/…). With some work I believe one can even get the correct constant in exponent. | |
| Nov 12, 2018 at 9:35 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
added 29 characters in body
|
| Nov 12, 2018 at 8:35 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 5 characters in body
|
| Nov 12, 2018 at 8:34 | comment | added | Aleksei Kulikov | Yes, of course we choose $x=\sqrt{R\log R}$, because for this choice we have that sum of primes up to $x$ is of order $R$. | |
| Nov 12, 2018 at 8:33 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 101 characters in body
|
| Nov 12, 2018 at 8:26 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 101 characters in body
|
| Nov 12, 2018 at 8:26 | comment | added | Aleksei Kulikov | @Ethan Yes, we choose $x=\sqrt{R\log R}$ and as you said product of primes is something of order $e^x$ so we have lower bound $\exp(x)$. | |
| Nov 12, 2018 at 8:23 | comment | added | Ethan Splaver | @AlekseiKulikov Just to make sure I'm following you, you chose $R$ so its digraph consisted of only oriented cycles which had prime lengths so that the least common multiple of their lengths was equal to the product of their lengths. And since $\prod_{p\leq x}p=\mathcal{O}(e^x)$ this means if we have cycles with prime lengths for every prime less then or equal to $x$ then we get $|\langle R \rangle|=\mathcal{O}(e^x)$. Also by the prime number theorem we get that $\log(R)|R|=x^2+\mathcal{O}(\frac{x^2}{\log(x)})$ therefore we have $|\langle R \rangle|=\mathcal{O}(e^{\sqrt{\text{log}(R)|R|}})$ | |
| Nov 12, 2018 at 8:07 | history | edited | Ethan Splaver |
edited tags
|
|
| Nov 12, 2018 at 8:05 | comment | added | Aleksei Kulikov | Firstly, if we consider graph which consists of oriented cycles with all prime lengths up to $\sqrt{R\log R}$(I’m not distinguishing between graphs and relations) then we will have something of order $\exp(\sqrt{R\log R})$. I have some vague idea how to prove that the answer is $O(c^R)$ for some $c$ (actually $O(lcm(1, 2, \ldots , R))$). When (and if) I’ll check up the details I’ll post it. | |
| Nov 12, 2018 at 8:01 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Nov 12, 2018 at 7:31 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 402 characters in body
|
| Nov 12, 2018 at 6:53 | history | rollback | Ethan Splaver |
Rollback to Revision 8
|
|
| Nov 12, 2018 at 6:34 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
added 62 characters in body
|
| Nov 12, 2018 at 3:42 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 1 character in body
|
| Nov 12, 2018 at 2:59 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
deleted 1 character in body
|
| Nov 12, 2018 at 2:51 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
edited tags
|
| Nov 12, 2018 at 2:44 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
added 212 characters in body
|
| Nov 12, 2018 at 2:34 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
added 195 characters in body
|
| Nov 12, 2018 at 2:27 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
added 195 characters in body
|
| Nov 12, 2018 at 1:52 | history | edited | Ethan Splaver | CC BY-SA 4.0 |
edited title
|
| Nov 12, 2018 at 1:44 | history | asked | Ethan Splaver | CC BY-SA 4.0 |