View source for Subnormal subgroup

In [[mathematics]], a '''dense graph''' is a [[graph (mathematics)|graph]] in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a '''sparse graph'''. The distinction between sparse and dense graphs is rather vague, and depends on the context.

For undirected [[Graph_(mathematics)#Simple_graph | simple graphs]], the '''graph density''' is defined as:
:<math>D = \frac{2|E|}{|V|\,(|V|-1)}</math>
The maximum number of edges is ½ |''V''| (|''V''|−1), so the maximal density is 1 (for [[complete graph]]s) and the minimal density is 0 {{harv|Coleman|Moré|1983}}.

==Upper density==
''Upper density'' is an extension of the concept of graph density defined above from finite graphs to infinite graphs. Intuitively, an infinite graph has arbitrarily large finite subgraphs with any density less than its upper density, and does not have arbitrarily large finite subgraphs with density greater than its upper density. Formally, the upper density of a graph ''G'' is the [[infimum]] of the values α such that the finite subgraphs of ''G'' with density α have a bounded number of vertices. It can be shown using the [[Erdős–Stone theorem]] that the upper density can only be 1 or one of the [[superparticular ratio]]s 0, 1/2, 2/3, 3/4, 4/5, ... ''n''/(''n''&nbsp;+&nbsp;1), ... (see, e.g., Diestel, p.&nbsp;189).

==Sparse and tight graphs==
{{harvtxt|Lee|Streinu|2008}} and {{harvtxt|Streinu|Theran|2009}} define a graph as being (''k'',''l'')-sparse if every nonempty subgraph with ''n'' vertices has at most ''kn''&nbsp;&minus;&nbsp;''l'' edges, and (''k'',''l'')-tight if it is (''k'',''l'')-sparse and has exactly ''kn''&nbsp;&minus;&nbsp;''l'' edges. Thus [[Tree (graph theory)|trees]] are exactly the (1,1)-tight graphs, forests are exactly the (1,1)-sparse graphs, and graphs with [[arboricity]] ''k'' are exactly the (''k'',''k'')-sparse graphs. [[Pseudoforest]]s are exactly the (1,0)-sparse graphs, and the [[Laman graph]]s arising in [[rigidity theory (structural)|rigidity theory]] are exactly the (2,3)-tight graphs.

Other graph families not characterized by their sparsity can also be described in this way. For instance the facts that any [[planar graph]] with ''n'' vertices has at most 3''n'' - 6 edges, and that any subgraph of a planar graph is planar, together imply that the planar graphs are (3,6)-sparse. However, not every (3,6)-sparse graph is planar. Similarly, [[outerplanar graph]]s are (2,3)-sparse and planar [[bipartite graph]]s are (2,4)-sparse.

Streinu and Theran show that testing (''k'',''l'')-sparsity may be performed in polynomial time when ''k'' and ''l'' are integers and 0&nbsp;≤&nbsp;''l''&nbsp;<&nbsp;2''k''.

==Sparse and dense classes of graphs==
{{harvtxt|Ossona de Mendez|Nešetřil|2010}} considered that the sparsity/density dichotomy makes it necessary to consider infinite graph classes instead of single graph instances. They defined ''[[somewhere dense (Graph Theory)|somewhere dense]]'' graph classes has those classes of graphs for which there exists a threshold ''t'' such that every complete graph appears as a ''t''-subdivision in a subgraph of a graph in the class. To the opposite, if such a threshold does not exist, the class is ''[[somewhere dense (Graph Theory)|nowhere dense]]''. Properties of the nowhere dense vs somewhere dense dichotomy are discussed in {{harvtxt|Ossona de Mendez|Nešetřil|2012}}.

==See also==
*[[Dense subgraph]]

==References==
* Paul E. Black, [http://www.nist.gov/dads/HTML/sparsegraph.html Sparse graph], from ''Dictionary of Algorithms and Data Structures,'' Paul E. Black (ed.), [[National Institute of Standards and Technology|NIST]]. Retrieved on 29 September 2005.
* {{citation | first1 = Thomas F. | last1 = Coleman | first2 = Jorge J. | last2 = Moré | year = 1983 | title = Estimation of sparse Jacobian matrices and graph coloring Problems | journal = SIAM Journal on Numerical Analysis | volume = 20 | pages = 187–209 | doi = 10.1137/0720013 | issue = 1 }}. <!-- feel free to replace with a better reference for "graph density" -->
*{{citation|first=Reinhard|last=Diestel|title=Graph Theory|publisher=Springer-Verlag|series=Graduate Texts in Mathematics|year=2005|isbn=3-540-26183-4|oclc=181535575}}.
*{{citation
 | last1 = Lee | first1 = Audrey
 | last2 = Streinu | first2 = Ileana
 | doi = 10.1016/j.disc.2007.07.104
 | issue = 8
 | journal = Discrete Mathematics
 | mr = 2392060
 | pages = 1425–1437
 | title = Pebble game algorithms and sparse graphs
 | volume = 308
 | year = 2008}}.
* {{Citation | last=Preiss|given=first| title=Data Structures and Algorithms with Object-Oriented Design Patterns in C++ | publisher=John Wiley & Sons |year=1998 | isbn=0-471-24134-2}}.
* {{cite conference | first2 = Patrice | last2 = Ossona de Mendez|| authorlink2=Patrice Ossona de Mendez | first1 = Jaroslav | last1 = Nešetřil | authorlink1=Jaroslav  Nešetřil| year = 2010 | title = From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits| booktitle = European Congress of Mathematics| publisher = European Mathematical Society | pages=135–165}}
*{{citation
 | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil
 | last2 = Ossona de Mendez | first2 = Patrice | authorlink2=Patrice Ossona de Mendez
 | doi = 10.1007/978-3-642-27875-4
 | isbn = 978-3-642-27874-7
 | location = Heidelberg
 | mr = 2920058
 | publisher = Springer
 | series = Algorithms and Combinatorics
 | title = Sparsity: Graphs, Structures, and Algorithms
 | volume = 28
 | year = 2012}}.
*{{citation|first1=I.|last1=Streinu|author1-link=Ileana Streinu|first2=L.|last2=Theran|year=2009|title=Sparse hypergraphs and pebble game algorithms|journal=[[European Journal of Combinatorics]]|volume=30|issue=8|pages=1944–1964|doi=10.1016/j.ejc.2008.12.018|arxiv=math/0703921 }}.

[[Category:Graph families]]