Prove that the for all $n>1000$, we can arrange the number $1,2,\dots, \binom{n}{2}$ on edges of a complete graph with $n$ vertices so that the sum of the numbers assigned to edges of any length three path (possibly closed) is not less than $3n-1000log_2log_2 n$.
Problem
Source: 239 2014 S8
Tags: graph theory, combinatorics
BlazingMuddy
02.06.2020 13:30
I might have misinterpreted the problem, but I think one can definitely attain at least $\lfloor \frac{n^2}{4} \rfloor + 4$ for all $n \geq 3$.
Split the set of vertices into 2 sets $A$ and $B$ such that $0 \leq |A| - |B| \leq 1$ (in particular, $A = \lceil \frac{n}{2} \rceil$ and $B = \lfloor \frac{n}{2} \rfloor$ . Then, for any edge $e = xy$ where $x \in A$ and $y \in B$, assign an integer less than or equal to $|A||B| = \lfloor \frac{n^2}{4} \rfloor$. Then, assign any of the remaining value to all the other edges.
Now, for any triangle, at least one of the edges of the triangle joins two vertices, where either both of them are in $A$ or both are in $B$. The number assigned to this edge is at least $|A||B| + 1 = \lfloor \frac{n^2}{4} \rfloor + 1 > 3n$, so the sum of all the numbers is strictly greater than $3n$.
DVDthe1st
02.06.2020 15:03
The correct problem should be that "the sum of the numbers assigned to the edges of any length 3 path (possibly closed) is ..."
Oksutok
08.11.2023 16:54
Bumppp...