Interesting families of sparse graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T17:59:09Z http://mathoverflow.net/feeds/question/2093 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs Interesting families of sparse graphs? Rune 2009-10-23T14:30:13Z 2013-01-17T01:52:48Z <p>I'm interested in graph families which are sparse, and by sparse I mean the number of edges is linear in the number of vertices. |E| = O(|V|). Besides non-trivial minor-closed families of graphs (these turn out to be sparse), I don't know any other families. Can anyone suggest any interesting graph families (which are not minor-closed) which are sparse?</p> <p>Please don't suggest the trivial family ("the family of sparse graphs").</p> <p>EDIT: Thanks to the first few people who replied, I realized that bounded degree graphs (max degree &lt; k) also form an interesting and large class of sparse graphs. So perhaps I'll refine my question to exclude those too. Any interesting sparse graph families where the max degree isn't bounded? For example the family of star graphs is sparse and not bounded degree. (But they're minor-closed.)</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2097#2097 Answer by Alon Amit for Interesting families of sparse graphs? Alon Amit 2009-10-23T15:12:29Z 2009-10-23T15:12:29Z <p>Well, for any d, the family of d-regular graphs is sparse in your sense and not minor closed. I don't suppose this is what you're after, so perhaps you can refine the question?</p> <p>EDIT: naturally, there are variations on this theme - graphs of bounded degree, graphs of bounded degree with additional degree restrictions, graphs which cover (in the topological sense) a fixed base graph, ...</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2103#2103 Answer by JSE for Interesting families of sparse graphs? JSE 2009-10-23T15:26:29Z 2009-10-23T15:26:29Z <p>Cayley graphs of groups generated by 2 (or any fixed number) of elements?</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2104#2104 Answer by Sonia Balagopalan for Interesting families of sparse graphs? Sonia Balagopalan 2009-10-23T15:27:17Z 2009-10-23T15:27:17Z <p>Expander graphs are regular, hence sparse, and have a lot of interesting properties and applications. Elementary Number Theory, Group Theory, and Ramanujan Graphs by Davidoff, Sarnak, and Valette is an excellent introduction. A Google search for expander graphs also turns up a lot of material.</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2119#2119 Answer by David Eppstein for Interesting families of sparse graphs? David Eppstein 2009-10-23T17:01:00Z 2009-10-23T17:01:00Z <p>Minimally rigid graphs in d dimensions. For d=2 these are the <a href="http://en.wikipedia.org/wiki/Laman_graph" rel="nofollow">Laman graphs</a> but I don't think any kind of clean combinatorial description of these graphs is known for higher dimensions.</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2186#2186 Answer by Ilya Nikokoshev for Interesting families of sparse graphs? Ilya Nikokoshev 2009-10-23T21:02:19Z 2009-10-23T21:02:19Z <p>You need examples, right? <strong>Internet, local networks, social connections</strong> :)</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2195#2195 Answer by Boris Bukh for Interesting families of sparse graphs? Boris Bukh 2009-10-23T21:37:40Z 2009-10-23T21:37:40Z <p>1) Graphs of degree at most d. There are a myriad results known about them. Among them there are regular graphs (graphs in which every vertex is of degree exactly d).</p> <p>2) Graphs of bounded degeneracy. These are the graphs in which every subgraph has a vertex of degree at most d. For example, stars have unbounded degree, but degeneracy 1. These share some common properties with graphs of bounded degree. For example, there are several results in Ramsey theory that have been extended from graphs of bounded degree to graphs of bounded degeneracy.</p> <p>3) Random graphs of edge density c/n for constant c. Strictly speaking these are not a 'family of graphs', but since for properties of interest a random graph usually either satisfies it with high probability or fails it with high probability, it is fair to add them. There are also various other models of random graph that yield sparse graphs.</p> <p>4) On a lower level, there are particular subfamilies of the above, such as stars, grids, etc. </p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/2233#2233 Answer by Harrison Brown for Interesting families of sparse graphs? Harrison Brown 2009-10-24T02:05:39Z 2009-10-24T02:05:39Z <p>Although they're not as commonly studied, you can define expander families where the max degree isn't bounded.</p> <p>You can also approach expanders from a spectral perspective (expansion properties have to do with how small the second-largest eigenvalue is), and if you do that, then you can also consider graphs with small third-largest eigenvalue, fourth-largest eigenvalue, etc. These aren't nearly as interesting or important as expanders, but they occasionally have their uses.</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/3617#3617 Answer by daysweetener for Interesting families of sparse graphs? daysweetener 2009-10-31T23:15:05Z 2009-10-31T23:15:05Z <p>A topological graph which is k-quasi-planar is a topological graph which does not contain k pairwise crossing edges. It is conjectured that for a fixed k, such a graph is sparse. This conjecture is known to hold if k=2 (in that case the graph is planar) and if k=3,4. The conjecture is open as far as I know for larger k.</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/26051#26051 Answer by Jon Awbrey for Interesting families of sparse graphs? Jon Awbrey 2010-05-26T19:08:24Z 2010-05-26T21:48:24Z <p>One family of graphs that bears unlimited degrees of computational fruit has been dubbed (by me) <em>painted and rooted cacti</em> (PARCs). <em>Painted</em> just means that you can associate any subset of a finite <em>palette</em> $\mathcal{P} = \lbrace p_1, \ldots, p_k \rbrace$ of <em>colors</em> $p_j$ with each node of the underlying rooted cactus.</p> <p>PARCs can be interpreted as propositional calculus formulas in a couple of ways that are logically dual to each other, extending the graphical syntax for propositional logic that C.S. Peirce called his Alpha graphs, with their <em>entitative</em> and <em>existential</em> readings.</p> <p>I'll dig up some links &hellip;</p> <p>I'd completely forgotten &mdash; here's a <a href="http://mathoverflow.net/questions/4930/finding-minimal-or-canonical-expressions-for-boolean-truth-tables/4979#4979" rel="nofollow">sparse exposition of cactus calculus</a> (in the so-called <em>existential interpretation</em>) that I'd already posted on another question.</p> http://mathoverflow.net/questions/2093/interesting-families-of-sparse-graphs/119124#119124 Answer by vb le for Interesting families of sparse graphs? vb le 2013-01-17T00:23:37Z 2013-01-17T00:23:37Z <p>Let me recommend the book <strong>J. Nešetřil and P. Ossona de Mendez,</strong> <a href="http://link.springer.com/book/10.1007/978-3-642-27875-4//page/1" rel="nofollow">Sparsity: Graphs, Structures, and Algorithms</a>, Springer 2012. It is the first systematic study of sparse graphs and related topics.</p>