The study of structures in large random graphs has been a central direction in probabilistic combinatorics. In this talk, I will survey several recent developments in this front with interesting connections. Certain important aspects in the study of structures in random graphs can be phrased in terms of thresholds — the density locations at which a structure emerges. In joint work with Jinyoung Park, building on connections to our resolution of a conjecture of Talagrand on the behavior of random linear programs under combinatorial constraints, we prove the long-standing Kahn-Kalai conjecture, that thresholds of general monotone properties are closely predicted by expectation obstructions. The Kahn-Kalai conjecture is a beautiful milestone towards the understanding of emergence of general structures, and yet to complete the quest, it remains to study these expectation obstructions. This latter task can prove to be highly challenging in several cases and bring in interesting connections to structural results. As an illustration, I will discuss joint work with Ashwin Sah, Mehtaab Sawhney and Michael Simkin on enumerating and determining the threshold of clique factors and bounded degree spanning trees in random subgraphs of graphs with high minimum degree. Our proof crucially builds on the regularity method and embedding techniques, which are seminal cornerstones of modern combinatorics. Switching from independent Erdos-Renyi random graphs to structured ensembles with dependency introduces significant challenges. I will discuss this challenge in the context of random Cayley subgraphs of general groups. Given a fixed finite group, random Cayley graphs are constructed by choosing the generating set at random. These graphs thus reflect interesting symmetries and properties of the group, at the cost of inducing complex dependencies. I will discuss results on clique and independence numbers in random Cayley graphs of general groups, as well as progress towards a conjecture of Alon on Cayley graphs with small clique and independence number. These questions are naturally connected with some fundamental problems in additive combinatorics, which we address using both group theoretic and purely combinatorial perspectives. This is based on joint work with David Conlon, Jacob Fox and Liana Yepremyan.