We investigate the emergence of swarm intelligence using task allocation in large robot swarms. First, we compare task decomposition graphs of different levels of richness and measure the emergent intelligence arising from self-organized task allocation by deriving STOCH-N1, a stochastic allocation algorithm which contextualizes per-robot task allocation decisions based on a previous task’s neighborhood within the graph. The results are compared to other state of the art algorithms. Second, we derive MAT-OPT: a greedy algorithm that optimally solves the swarm task allocation problem by representing the swarm’s task allocation space as a matroid under some restrictive assumptions. We compare the MAT-OPT allocation method, which disregards task dependencies, with STOCH-N1, which emphasizes collective learning of graph structure (including dependencies). Results from an object gathering task show that swarm emergent intelligence (1) is sensitive to the richness of task decomposition graphs (2) is positively correlated with performance, (3) arises out of learning and exploitation of graph connectivity and structure, rather than graph content.