In Steven Boyd’s Convex Optimization lecture 1 at the 39 minute mark he states that “A lot of combinatorial problems appear non convex but a lot of them are convex…If you let the variables vary between 0 and 1 you can prove there is a solution on the vertices”.
Does anyone know of any examples combinatorial optimization problems that are convex and can be solved using CVX? Are there any examples of such problems in Stephen Boyd’s “Complex Optimization” book?
The field of compressive sampling (or compressed sensing) is built on the premise that certain minimum-cardinality problems—which are normally combinatorial—can, under certain conditions, be solved exactly using convex optimization.
A technical but accessible article discussing compressive sampling is “An Introduction to Compressive Sampling” by Emmanuel J. Candès and Michael B. Wakin, from the March 2008 issue of IEEE Signal Processing Magazine. A PDF of this article can be found here.
To be perfectly honest, CVX is not the most efficient way to solve the problems that arise in compressive sampling. For large-scale problems, there is specialized software that is much more efficient. But CVX is quite useful for studying the field and for playing with various formulations. Many people who study the field use CVX extensively, including me of course 
I came across this book entitled Semidefinite Programming for Combinatorial Optimization.
http://www.gerad.ca/aide/sites/default/files/Helmberg%20-%20Notes%20on%20SDP_0.pdf
Chapter 3 covers semidefinite relaxations of combinatorial optimization problems.