Skip to main content
added 17 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

For $n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, $b\to a$, take $i=j=a$, $k=b$. If not, consider a vertex $a$ with maximal indegree, it is at least $n-1$ (allsince all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there are arrows fromis an arrow $c\to b$ $C$ to $B$, we find a trianglemay take $i=c,j=a,k=b$. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$, this. It gives two opposite edges iffor $n>2$.

For $n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, $b\to a$, take $i=j=a$, $k=b$. If not, consider a vertex $a$ with maximal indegree, it is at least $n-1$ (all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there are arrows from $C$ to $B$, we find a triangle. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$, this gives two opposite edges if $n>2$.

For $n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, $b\to a$, take $i=j=a$, $k=b$. If not, consider a vertex $a$ with maximal indegree, it is at least $n-1$ (since all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there is an arrow $c\to b$ $C$ to $B$, we may take $i=c,j=a,k=b$. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$. It gives two opposite edges for $n>2$.

Post Undeleted by Fedor Petrov
added 556 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

For arbitrary $n$$n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, let $S_a$ be$b\to a$, take $i=j=a$, $k=b$. If not, consider a set of numbersvertex $a$ with parity differentmaximal indegree, it is at least $n-1$ (all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there are arrows from $a$'s$C$ to $B$, we find a triangle. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$, this gives two opposite edges if $n>2$.

For arbitrary $n$, let $S_a$ be a set of numbers with parity different from $a$'s.

For $n>2$ this is true. Consider a directed graphs with arrows from $a$ to $S_a\setminus a$. If it has arrows $a\to b$, $b\to a$, take $i=j=a$, $k=b$. If not, consider a vertex $a$ with maximal indegree, it is at least $n-1$ (all outdegrees are equal to $n-1$). Let $B=\{i\ne a:a\in S_i\}$, $C=S_a\setminus a$. Now $B,C$ are disjoint and each of them contains at least $n-1$ vertices. If there are arrows from $C$ to $B$, we find a triangle. If not, all arrows from $C$ go to $D=V\setminus (B\cup a)$, but this set contains at most $n$ elements and this may happen only if $S_c=D$ for all $c\in C$, this gives two opposite edges if $n>2$.

Post Deleted by Fedor Petrov
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

For arbitrary $n$, let $S_a$ be a set of numbers with parity different from $a$'s.