Timeline for Forming Subsets
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 4, 2017 at 18:31 | comment | added | მამუკა ჯიბლაძე | @Alex sorry conclusion of the previous comment was wrong, let me start over. Beginning was correct: for any $i\leftarrow j\to k$, either $k\in B(i)\cap B(j)$ or $i\in B(j)\cap B(k)$. The correct conclusion is that, if disjointness is required, then for any $j\to k$ and any $i\ne j,k$ we must have $i\to j$. Then also for any $l\ne i,j,k$ we must have $l\to i$ and $l\to j$, so $j\in B(l)\cap B(i)$. Thus (if I am not making mistake again) disjointness only holds for a 3-cycle $i\to j\to k\to i$. | |
| Jun 3, 2017 at 16:50 | comment | added | მამუკა ჯიბლაძე | As for disjointness, for tournaments it is equivalent to the following condition: if $i\to j\to k$ then $k\to i$. | |
| Jun 3, 2017 at 10:07 | comment | added | მამუკა ჯიბლაძე | @Alex Note that I am not OP :D In my answer, an additional restriction is considered which coincides with the restriction in Fedor's answer, and also with the first restriction in the Olympiad question i. e. that the graph is a tournament (exactly one of $i\to j$, $j\to i$ holds for $i\ne j$). In presence of this restriction, the remaining OP conditions are equivalent to existence of $i\to k\to j$ for every $i\to j$, while in the Olympiad question it is existence of $i\to k\leftarrow j$ for every $i, j$. | |
| Jun 3, 2017 at 7:33 | comment | added | Alex | @მამუკაჯიბლაძე That is why I said the conditions are milder in the Olympiad formulation. You claim such configurations exists for $n = 4, 5, 6$ so it cannot be that your setup is equivalent to the Olympiad problem setup. But I was wondering if the constructions for the later would work also for your formulation. Disjointness seems stronger than your conditions 2) and 3) but maybe I'm just being silly. If that's the case then you have a construction for $n \geq 7$ which on top of your construction for $n = 4, 5, 6$ would give everything. | |
| Jun 2, 2017 at 18:37 | comment | added | მამუკა ჯიბლაძე | @Alex I've checked, actually the requirement is that it is a tournament (i. e. $i\notin B(i)$ and $i\in B(j)$ iff $j\notin B(i)$ for $i\ne j$) and moreover that $B(i)$ an $B(j)$ are not disjoint. I cannot see right away whether this is an equivalent problem... | |
| May 29, 2017 at 10:39 | comment | added | Alex | This question reminds me a lot of a 2003 Romanian Math Olympiad problem given for the 9th grade (I added the grade just in case one wants to look for the exact formulation). The conditions seemed a bit more mild in that problem. They only asked for $i \not\in B(i)$ plus condition 1) plus disjointness of the $B(i)$s. Then answer was that such configurations exist only for $n \geq 7$. For every $n \geq 7$ they gave explicit examples. | |
| May 26, 2017 at 8:33 | history | edited | Vivek Mishra | CC BY-SA 3.0 |
deleted 3 characters in body
|
| May 25, 2017 at 18:38 | answer | added | მამუკა ჯიბლაძე | timeline score: 1 | |
| May 25, 2017 at 12:47 | history | edited | Vivek Mishra | CC BY-SA 3.0 |
added 8 characters in body
|
| May 25, 2017 at 9:12 | comment | added | Vivek Mishra | @T.Amdeberhan : In the problem mentioned by you(mathoverflow.net/questions/268798/…) the size of subset is fixed. Here my subsets can be of any size. Though by the constraints you can prove that each of them have to be of atleast size 2. | |
| May 24, 2017 at 19:32 | history | edited | Shahrooz | CC BY-SA 3.0 |
Improved formating
|
| May 24, 2017 at 18:05 | answer | added | Fedor Petrov | timeline score: 6 | |
| May 24, 2017 at 17:48 | comment | added | Vivek Mishra | The dual problem of this seems to be messy. If you look at it from the graph theory perspective I am claiming that when the graph has only directed edge from i to j then it cannot have an edge from j to i. Also after constructing such subsets for all 1,2,...,n ; this condition would never get violated. This seems to be difficult considering the subset constraints that are present. Please let me know if you get better insights on it. If possible can you tell me what you think is a dual problem for this. | |
| May 24, 2017 at 17:37 | comment | added | Vivek Mishra | @Fedor: Could you elaborate on it or give me some link for reference. | |
| May 24, 2017 at 16:21 | comment | added | Fedor Petrov | A random tournament works for large $n$. | |
| May 24, 2017 at 16:20 | comment | added | T. Amdeberhan | If you think of the "dual" problem, then your question might be a relative of this mathoverflow.net/questions/268798/… | |
| May 24, 2017 at 16:17 | review | First posts | |||
| May 24, 2017 at 16:24 | |||||
| May 24, 2017 at 16:14 | history | asked | Vivek Mishra | CC BY-SA 3.0 |