How long does it take for all users in a social network to choose their communities?

We consider a community formation problem in social networks, where the users are either friends or enemies. The users are partitioned into conflict-free groups (, independent sets in the that represents the enmities between users). The dynamics goes on as long as there exists any set of at most users, being any fixed parameter, that can change their current groups in the partition , in such a way that they all strictly increase their utilities (number of friends , the cardinality of their respective groups minus one). Previously, the best-known upper-bounds on the maximum time of convergence were for and for , with being the independence number of . Our first contribution in this paper consists in reinterpreting the initial problem as the study of a dominance ordering over the vectors of integer partitions. With this approach, we obtain for the tight upper-bound and, when is the empty graph, the exact value of order . The time of convergence, for any fixed , was conjectured to be polynomial (Escoffier et al., 2012; Kleinberg and Ligett, 2013). In this paper we disprove this. Specifically, we prove that for any , the maximum time of convergence is in .