I have no idea how to do this problem, but I do have this one thought: Does this have something to do with how 2015 has 11 digits when written in binary?

It's been about a month and no one has posted a solution yet, so I'll post the first official solution.

I will call a subset of the vertices of a graph odd-cyclic if it has an odd number of vertices and there is a cycle in the graph containing exactly those vertices. (Subsets containing one vertex are not considered odd-cyclic.) It is enough to show that every graph $G$ with chromatic number $n$ has at least $2^{n-1} - n$ odd-cyclic subsets. [Indeed just construct a graph $G$ with vertices the members of the company joining two of them if and only if they are enemies. If we cannot partition the company as desired, then $\chi(G) \geqslant 12$. So $G$ has $2^{11}-12 > 2015$ odd-cyclic subsets. But every odd-cyclic subset is an unsociable group of people, a contradiction.] I proceed with induction on $n$. The cases $n=1,2$ are trivial while the case $n=3$ is the well-known result that every graph $G$ with $\chi(G) \geqslant 3$ has an odd cycle. Let us now assume that the result is true for $n=k$ and let $G$ be a graph with $\chi(G) = k+1$. If I can remove a vertex from $G$ without changing its chromatic number then I do so. Of course, the odd-cyclic subsets do not increase. Repeating this, I can assume that for every vertex $v$ of $G$ I have $\chi(G-v) = k$. So let us take any vertex $v$. Then $\chi(G-v) = k$ so by the induction hypothesis $G-v$ has at least $2^{k-1}-k$ odd-cyclic subsets. So it is enough to show that $G$ has at least \[ (2^k - (k+1)) - (2^{k-1} - k) = 2^{k-1} - 1\] odd-cyclic subsets containing the vertex $v$. Let $V_1,\ldots,V_k$ be any partition of $G-v$ into independent sets. The set $\{1,2,\ldots,k\}$ has $2^{k-1}-1$ even and non-empty subsets. So it is enough to show that for every such subset $I$, the graph $G$ has an odd-cyclic subset containing vertex $v$, at least one vertex from each $V_i$ with $i \in I$, and no vertex from any $V_j$ with $j \notin I$. Without loss of generality assume $ I = \{1,2,\ldots,2r\}$. For $1 \leqslant i \leqslant 2r$ let us write $A_i$ for the neighbours of $v$ in $V_i$. Let also $B_i$ be the subset of all vertices $w$ of $V_i$ for which there is a path $v_1v_2 \cdots v_t$ from some $v_1 \in A_1$ to $v_t = w$ with $v_k \in V_{j(k)}$ where $j(k)$ is the unique element of $I$ with $j(k) \equiv k \bmod 2r$. I will show that $A_{2r} \cap B_{2r} \neq \emptyset$. Then I will be done. Indeed then I can take a path $v_1 \cdots v_t$ with $v_1 \in A_1$ and $v_t \in A_{2r} \cap B_{2r}$. The length of the path is odd (as $t \equiv 2r \bmod 2r$) and has at least one vertex from each one of $V_1,\ldots,V_{2r}$. Also, it has no vertex from any other $V_j$. Thus, $vv_1\cdots v_tv$ is an odd cycle producing the odd-cyclic subset I want. It remains to show that $A_{2r} \cap B_{2r} \neq \emptyset$. So let us assume that the opposite happens. Let $V_i' = (V_i \setminus B_i) \cup B_{i-1}$ where $B_0 = B_{2r}$. The sets $V_i'$ are independent. Indeed if there was an edge $uw$ with $u \in B_{i-1}$ and $w \in V_i$ then by definition we would have $w \in B_i$ and so $w \notin V_i'$. In addition, because $A_1 \subseteq B_1$ and because $A_{2r} \cap B_{2r} = \emptyset$, vertex $v$ has no neighbouring vertices in $V_1' = (V_1 \setminus B_1) \cup B_{2r}$. But then putting $v$ inside $V_1'$ we get that $G$ has chromatic number $k$. This is a contradiction, thus completing the proof.

CantonMathGuy wrote: It's been about a month and no one has posted a solution yet, so I'll post the first official solution.

How can I have official solution??

CantonMathGuy wrote: Recall that the chromatic number of $G$ is the least $k$ such that a proper coloring \[V = V_1 \sqcup \cdots \sqcup V_k\]exists. What does the symbol $\sqcup$ mean?

It's disjoint union notation.

The following solution uses some spanning tree technique and constructs an natural algorithm of coloring the vertices. Let $G$ be the corresponding graph, it has at most $2015$ odd cycles. We want to color its vertices with $11$ colors. We can assume $G$ is connected, otherwise we apply the following argument to each connected component of $G$. Let us construct a spanning tree $T$ on $G$ by using breadth-first-search algorithm. It insures that all the edges of $G$ are "vertical" with respect to $T$, i.e. there are not cross edges in $T$. We begin to color the vertices of $T$ with colors $1,2,\dots$, starting from the root and going up using the following algorithm. First, color all vertices with color "$1$". Then, we step at the root of $T.$ All the vertices it is connected with (in $G$), we color with color "$2$". Next, we go one step up along $T$ and step at a vertex, call it $v$. If there exist upper vertices (with respect to $T$) $v_1,v_2,\dots, v_k$, that $v$ is connected with (in $G$), and all with the same color as $v$, we recolor each of them with the next possible color. In this way, we can exhaust all the vertices of the tree (which are all the vertices of $G$). Let us check that all colors used couldn't be more than $11$. For the sake of contradiction, assume at least $12$ colors were used. Note that if $v_i$ is colored with color "$i$", then there exist vertices $v_1<v_2<\dots<v_{i-1}<v_i$ (with respect to $T$) , such that each $v_j\,,\,j=1,2,\dots,i-1$ is colored with color $j$ and is connected to $v_i$. It holds since the coloring algorithm guarantees $v_{i}$ was recolored $i-1$ times. We call a sequence of vertices $v_1<v_2<\dots<v_r$ of $T$ a chain, if any of them is connected(in $G$) with the next one, and each $v_i$ have triggered a recoloring of $v_{i+1}$, thus the colors of $v_1,v_2,\dots,v_r$ are increasing. Now, let $v_{k}\,,\,k\leq 12$ is a vertex colored with color "$k$". For any sequence of colors $1\leq k_1<k_2<\dots<k_r=k$ , we will construct a cycle $v_{k_1}\,v_{k_2}\,\dots v_k$ , which is a chain and each vertex $v_{k_i}$ is colored with "$k_i$". First we choose the longest chain (the first vertex is the smallest possible), which ends up with $v_k$. Call this chain $p'= (v'_{k_1} <v'_{k_2}<\dots<v'_{k_s}<v_k)$. We mark all its vertices - it will be our retreating path. We start with $v_k\equiv v_{k_r}$ , it is connected backward with all colors from $k-1$ back to $1$. We count down them, starting from $k-1$, skipping a marked vertex(at most one, if any), till we get to color $k_{r-1}$. Let it be at the vertex $v_{k_{r-1}}$. Then, we proceed with $v_{k_{r-1}}$ the same way an so on till we get to $v_{k_1}$. (a bit more attention is needed in case ${k_1}=1$, but it's ok). Then we go again backward, but along the tree $T$ till we meet a node of the chain $p'$ and then through $p'$ we go forward to the vertex $v_k$, thus closing the cycle. It can be checked it is an injection between all subsets of $\{1,2,\dots,12\}$ and some cycles of $G$. Since the number of those subsets with odd number of elements, but at least $3$, are $2^{11}-11>2015$, we get a contradiction. It means the vertices of $T$ (that's of $G$) can be colored by the described algorithm with at most $11$ colors.

If I can remove a vertex from G without changing its chromatic number then I do so. Of course, the odd-cyclic subsets do not increase. Hi Demetres, why you have this?consider a k+1 chromatic graph including a triangle[sharing no common vertices]. If we delete one vertex of this triangle then the chromatic number is still k+1 but the number of odd cycle is decreased by 1.

ductiena1k43 wrote: CantonMathGuy wrote: It's been about a month and no one has posted a solution yet, so I'll post the first official solution.

How can I have official solution?? https://imo-official.org/problems.aspx

man this is tough

Plops wrote: Now the questions. When dgrozev says: dgrozev wrote: First, color all vertices with color "$1$". Then, we consider the root and the vertices it is connected to we color with "$2$". are we coloring the root with color $2$ as well? Also, when he says, dgrozev wrote: Next, we go one step up along $T$ and consider a vertex, call it $v$. If there exist upper vertices $v_1,v_2,\dots, v_k$(with respect to $T$), that $v$ is connected to(in $G$), and all with the same color as $v$, we recolor each of them with the next possible color. does he mean if we start from the root of $T$, say $u$, by going a level up, we consider a vertice $v$ of $T$ in level $2$. And, if this is the case, how would there be any vertices connected to $v$ belonging to a higher level than $v$ in $T$ with the same color as $v$ since all vertices in a higher level than $v$ will be colored with color $1$? @Plops: Sorry, didn't see you had asked me. But why did you hide your questions? I mean, the core of your post were your questions about my solution and you hid exactly that part?! Some more explanation about coloring algorithm. Let $v_0$ be the root of the described spanning tree. At the beginning we color all vertices in color "1". Set $v:=v_0$ and do the following procedure: Let $v_1,v_2,\dots, v_k$ be the vertices $v$ is connected with (in $G$) and that are upper than $v$ (with respect to the tree $T$). If some of them are colored in the same color as $v$, we recolor those ones with in the next possible color. Then repeat the above step substituting $v$ with each child of $v$, and so forth, till $T$ is exhausted. Anyway, thanks for the feedback! I redacted slightly my post to avoid some of the ambiguities mentioned.

Solved with Jeffrey Chen and Ryan Yang. We work in the following generality, where a graph is unsociable if its order is odd and it is Hamiltonian. Proposition: Given a graph \(G\) with chromatic number \(n\), there are at least \(2^{n-1}-n\) unsociable subgraphs. To this end, we will induct on \(n\), with base cases easy. Now assume the statement for chromatic number \(n-1\). We will now induct on the number of vertices of \(G\). Our base cases will be graphs with the property that removing any vertex decreases the chromatic number. For the inductive step, if removing some vertex does not decrease the chromatic number, remove it. Now we settle the base case. Arbtrarily choose a vertex \(v\), and let the colors be 0, 1, \(\ldots\), \(n-1\). Claim: There is a coloring of the graph such that \(v\) is the only vertex of color 0. Proof. By assumption, \(G\setminus v\) has a coloring with \(n-1\) colors, so add \(v\) back as its own color. \(\blacksquare\) Claim: For each subset \(T\subseteq\{1,\ldots,n-1\}\) of even size, there is an unsociable group \(H\) such that the set of colors that appear in \(H\) is exactly \(T\cup\{0\}\). Proof. Without loss of generality let \(T=\{1,\ldots,2k\}\). Define a sequence \((a_i)\) by \[ a_i=\begin{cases} i&\text{if }i\le2k\\ 1&\text{if }i>2k\text{ odd}\\ 2&\text{if }i>2k\text{ even}. \end{cases} \]Now define a sequence of sets of vertices \(S_1\), \(S_2\), \(\ldots\) as follows: let \(S_1\) contain the vertices of color 1 adjacent to \(v\); for \(i\ge2\), let \(S_i\) contain the vertices of color \(a_i\) adjacent to some element of \(S_{i-1}\), that are not in \(S_1\), \ldots, \(S_{i-1}\). I contend there is an index \(t\ge2k\) such that \(v\) is adjacent to an element of \(S_t\). Assume for contradiction \(v\) never appears; let \(i\) be the first index for which \(S_i=\varnothing\) by finiteness. Then considering the following alternate coloring: for each \(j\le i-1\) assign all elements of \(S_j\) the color \(a_{j+1}\); assign vertex \(v\) the color 1. This means the chromatic number of \(G\) is at most \(n-1\), contradiction. Thus if \(v\) is adjacent to something in \(S_t\), then there is a path going through the colors \(0\to a_1\to a_2\to\cdots\to a_t\to0\). Finally \(t\) must be even since \(S_1\) already contains all vertices of color 1 adjacent to \(v\). Thus the claim is proven. \(\blacksquare\) Now there are at least \(2^{n-2}-1\) unsociable groups containing \(v\). By the inductive step there are at least \(2^{n-2}-(n-1)\) unsociable groups not containing \(v\), so the number of unsociable groups is at least \[(2^{n-2}-1)+(2^{n-2}-(n-1))=2^{n-1}-n,\]as desired.

I will prove that if a graph has chromatic number $n$ then there are at least $2^{n-1}-n$ odd cycles. (In fact, equality is achieved with the complete graph on $n$ vertices). This is clearly sufficient as $2^{12-1}-12=2036 > 2015$. First a simple yet crucial claim: Claim: If a graph has chromatic number $n$, with $n > 1$ odd, then there exists an odd cycle containing each color. In the case $n=3$, the graph must not be bipartite, so it must contain on odd cycle. However, an odd cycle can clearly not contain only $2$ colors (as it would only return to the same color after an even number of steps), so it must contain $3$ colors. In the case $n>3$, WLOG we are in the counterexample with the fewest number of edges. Then this means that deleting any edge makes the graph $n-1$ colors. In particular, we may assume that there is some vertex which has a unique color. Let the $n$ partitions of our graph by $A_1, A_2, \ldots, A_n$, with $|A_1|=1$. Let $C_i$ be the odd cycle which contains vertices exactly from the colors $A_1, A_i, A_{i+1}$ for $2 \le i \le n-1$. Then if we combine the cycles from the $C_i$, but remove the edges from $A_1$ to $A_3, A_4, \ldots A_{n-1}$, then we get an odd cycle containing all the colors, except it possibly repeats vertices (but does not repeat edges). Now since this forms a cycle with repeated vertices, we can simply delete edges to get a version without repeated vertices. I also claim that this new cycle has to contain every color. This is because $A_i$ only contains connections to the colors $A_{i-1}$ and $A_{i+1}$, and there are only two edges going out from $A_1$, so after following the first edge from $A_1$ to $A_2$, it is required that we pass through all the other colors to get back. It must also be the case that this cycle has odd length, because every step flips the parity of index of our color, except for the very last step from $A_1$ to $A_n$. Thus the claim is proved. Now a quick computation. By looking at all subsets of the colors featuring an odd number of elements, we get that the total number of odd cycles is at least $\binom{n}{3}+\binom{n}{5} + \cdots=\frac{2^n}{2}-\binom{n}{1}=2^{n-1}-n$.

I don't believe the above proof works because combining $C_i$ doesn't work if they pass through distinct vertices bordering the unique vertex. The solution above above that almost works but $a_i$ has to be define cyclically else if you have a triangle $i-1-2$ then it becomes $1-2-1$ which is bad. We show that if $\chi(G) = n$, then there are at least $2^{n-1} - n$ unsociable sets. Claim: WLOG $G$ is connected and some vertex has one color. Proof. Remove components and vertices until removing any one more vertex decreases the chromatic number. $\blacksquare$ Claim: If a graph has chromatic number $2k+1$, then there exists an odd cycle through all $2k+1$ colors. Proof. Let $t$ be the vertex with the one unique color. Let $1, 2, \dots, 2k$ be the other colors. Now let $A_1$ be the neighbors of $t$ with color $1$. Define $A_{i+1}$ as the neighbors of $A_i$ that are color $i+1 \pmod{2k}$ that aren't in smaller $A_i$. Now consider when the process terminates. We consider recoloring $A_t$ with the color of $A_{t+1}$. Then this preserves coloring between two elements in $A_a, A_b$ which share an edge. By definition, if $u \in A_i$ then all vertices with color one after $u$ appear in some $A_i$. This coloring decreases the chromatic number unless coloring $t$ with color $1$ leads to a contradiction, which then gives us a cycle \[ t \to a_1 \to a_2 \to \dots \to a_{2nk} \to t \]which works. $\blacksquare$ This then gives us $\frac{2^n}{2} - n = 2^{n-1} - n$ unsociable sets as desired.

And with this post, I officially have 1000 posts specifically on HSO forum, it's been a long journey I'm not gonna lie, and it's been really awesome, I meet a lot of nice people on the way (that were with me even after messing up a couple IMOs, yall are awesome :blobheart:), and I'm pretty sure there is much more to go lol, I still remember my first posts on HSO being either nice or unsolvable FEs, my first own geo which I posted and people seemed to like!, and also when I slowly became more known among the AoPS possibly from my extremely inconsistent posts (in terms of difficulty on the problems I was solving, mainly geo lol), I still remember with joy a lot of events that have happend, when the era of mocks was still a thing because of the covid-19 quarantine, Gaussian Curvature folks, the people in OTIS after some friends convinced me to try to apply, everyone with the same target of improving, and yall did great, during these 4.5 years I learned a lot of stuff and I still have much more to go for, If you have seen a lot of my posts you will realise most of them are geos, but hopefully that will change, as I'm trying to become great in other subjects!. Here I shall present you what is an insane problem that made me sweat and tryhard in the end , where after each failure the next step consisted of making improvements to my previous tries, a really insightful problem despite the 2.5 hrs this took me to solve in total. So without further yap, here comes a different style of sharing my solution which will include motivation and the thought process behind it. $\rule{25cm}{0.3pt}$ The beggining: Will I be able to do this?, I have barely any intuition for these at all why am I even trying. First of all, when one comes across this problem, the first thing to do is wonder how relevant are $2015$ and $11$, first of all $2015$ is suspiciously close to $2^{11}=2048$, so a normal thing to do now is try smaller cases keeping in mind the power of two thing, at forst it seems that it could be power of two minus something constant, except that as you want more groups this stops working, so the next thing that could work is power of two minus linear, as there is small values that in fact satisfy that, so by staying principled and trying small cases one eventually comes across with the key claim of the provlem, which if proven obviously finishes: The main claim wrote: On a simple graph $G$ with $\chi(G)=n$, if we say that a subgraph of $G$ is called odd-cycle closed if it has an odd number of vertices and there exists an odd cycle going through all of them, then prove that there is at least $2^{n-1}-n$ odd-cycle closed subgraphs in $G$ $\rule{25cm}{0.3pt}$ Reductions+the Inductive setup: I seem to have a clue on how to start...hopefully Of course there isn't need of handling too much chaos which is why you can perform the optimization of deleting a vertex from $G$ if it doesn't decrease the chromatic number until for any vertex $v \in G$ we have that $\chi(G-v)=n-1$, it's clear that this optimized graph is connected and from now we will assume all of our graphs are optimized. Now these local optimizations followed by induction seem to be really nice when attacking graph problems, it's really nice when they end up working out perfectly, so I decided to give it a shot, so we go by inductive where the base cases $n=1,2$ are trivial, so now assume that it's true for all the graphs with chromatic color $\le k$, then we prove it for all graphs with chromatic color $k+1$. Now it's clear that from the reduction if we isolate vertex $v'$ from the graph $G$ then we consider the $k$-coloring of $G-v'$ and then add the color $k+1$ to it (ah yes, we label the colors as $1,2, \cdots k+1$), now since we can use inductive hypothesis on $G-v'$ it remains to show that there exists at least $2^{k-1}-1$ odd-cycle closed subgraphs of $G$ that go through $v'$, the rest of the proof will be spent on proving this. $\rule{25cm}{0.3pt}$ It's failing time (yay...): Why is this problem not over, every try ends up having something to fix, but somehow everytime it seems to get closer and closer from the solve, maybe if I push this hard enough I'll get it From the coloring mentioned above split in groups $C_1, C_2 \cdots, C_k$ of the colors $1,2, \cdots, k$ respectively, counting the number of even sized subsets of $k$ we know that all we need is to prove that from the set $C_1, C_2 \cdots C_{2\ell}$ we are capable of choosing some $v_i \in C_i$ (at least one from each of the selected colors) for which we end up forcing an odd cycle that goes through $v'$, from here it is no longer needed to push any normal combinatorical techniques as now it's 100% a pure graphs problem, graphs are a nice way of abstracting information which means that now it comes entirely on how I play with what I have. Let $N_i$ be the neighbourhood of $v'$ in $C_i$ (which each is non-empty of else we can just color $v'$ by color $i$ and get a $k$-coloring, of course a contradiction), so after this I thought that perhaps I could simply mess around by first trying $\ell=1$, some observation made me realise that after considering both neighbour hoods, I could have that at least one vertex from each was connected to some vertex of the other color or else I could send all of them to the other color and re-color $v'$ to one of the $k$ colors to get another $k$-coloring, which would of course be a contradiction, so if there was a triangle I would be happy, but if there wasn't any two vertices connected between the two neighbourhoods then after having one from color $1$ connected to $v'$ this would be connected to a vertex of color $2$ which did not belong to the neighbourhood of $v'$, if for none of these paths of lenght $2$ they were connected to a vertex from color $1$ again, then I could simply swap their colors and repeat the process for the other color until I ran out of one neighbourhood which again allows a $k$-coloring, so if you repeated this reasoning over and over you would have that you can force a huge path that behaves like a ping-pong between the two colors and eventually one has to get to the neighbourhood of $v'$ which would give you the odd-cycle. I just had a very little problem....if $\ell=2$ all of this reasoning had too much cases to deal with, however I did not completely discard this ideas as I had faith it just needed to be improved, so I did the analysis, why is this failing, well, first I thought of simply trying induction on this mini-clima, except of course for some large value it would not make sense at all, the main flaw was that I was not capable of finding a way to make this process work for the rest of $\ell$'s greater than $1$ wihout hagint too much cases to explain, also I wasn't using the fact that $2\ell$ was even at all to get the odd-cycles, which meant that at some point I had used it for the case $\ell=1$ without realising, but on what?, what I could've missed?. It turns out that after trying some greedys which failed and didn't give much info, I did realise that to keep order in the paths I wanted to find that connected neighbourhoods of $v'$ and thus created an odd-cycle, while also using $2\ell$ was even to ensure we had the odd-cycle, was to have the path to be $\pmod{2\ell}$, of course now it made much more sense why for $\ell=1$ I had a "ping-pong" like behaviour on the color groups. $\rule{25cm}{0.3pt}$ We are cooking again!, lets gooo: But now after I do this....supricingly things seem manageable now, YAY Define $P_i$ as the subgraph of $C_i$ for which for each $u \in P_i$ there existed a path $v_1 \cdots v_q$ (where $v_q=u$ and $v_1 \in N_1$) in which you have that for each $v_j$ it was true that $v_j \in C_{j'}$ where $j \equiv j' \pmod{2\ell}$, (this is the mod thing I was talking about), now realise that if we prove that $P_{2\ell} \cap N_{2\ell}$ was not empty, we are done because we can just simply use this path and the two neighbours to $v'$ from $C_1,C_{2\ell}$ and because of $\pmod{2\ell}$ we ensure the cycle created is odd. So now suppose FTSOC that $P_{2\ell} \cap N_{2\ell}$ was the empty set, then we prove that we can perform a coloring for which we only use $k$-colors, now similar to the ping-pong idea for the base case $\ell=1$, we are gonna do a giga swap on the $P_i$'s (transfer them to a difference $C_j$, which if you think about it makes a lot of sense since the ping pong idea itself is really informal, so you need a better way to explain and control everything in the problem, and these sets go really well with what we tried to setup). Now consider all indices mod $2\ell$, then define as our alternative coloring $C_{i'}=(C_i-P_i) \cup P_{i-1}$, first to actually make sure this will be our new $k$-coloring we want each to have no edges inside them, but that is rather...easy since we notice that if there was an edge $uv$ from $u \in P_{i-1}$ to $v \in C_i$ then by completing the path we have that $v \in P_i$ which means that $v$ isn't in $C_{i'}$, which means that no two vertices in $C_{i'}$ are connected so that's good, also each of these is disjoint as the process was to take $P_i$ from each and shift by $-1$ so it's like filling a hole with a really alike piece that was taken from the previous one, completing a cycle, now just note that $N_1$ is inside $P_1$ and since we assumed that $P_{2\ell} \cap N_{2\ell}$ is empty there is no vertex connected to $v'$ in $P_{2\ell}$, and since $P_1$ took away all $N_1$ from $C_1$ we have in fact that $v'$ is not connected to $C_{1'}$, so then we put both of the same color and the others with $k-1$ colors, thus having achieved a $k$-coloring, contradiction!. Therefore the intersection is not empty and thus we clearly have our pat and thus our odd cycle, notice that each of the odd cycles is unique as they don't use any other vertex from other colors outside the ones in the subset and there is at least one from each color in the subset, so by doing the counting as mentioned we get the subclaim needed in the induction, thus the induction is complete, therefore our main claim is true, which finishes the problem as if we needed $12$ groups at least then we would have at least $2^{11}-12=2036>2015$ unsociable groups, contradiction one again, therefore it's possible to the $11$ groups partition, thus we are done . $\rule{25cm}{0.3pt}$ Thank you so much for reading all of this huge chunk of text :blobheart:.

Congrats Luis!

aaehabgh

Congratulations for your 1000th post! :p