en>Bender2k14: /* Generalizations */ improved wording

2014-05-19T18:38:33Z

Generalizations: improved wording

en>Dricherby: /* History */ "Temperley-Fisher" → "Temperley and Fisher" – it's two people, not a double-barrelled surname.

2013-08-06T16:03:29Z

History: "Temperley-Fisher" → "Temperley and Fisher" – it's two people, not a double-barrelled surname.

← Older revision		Revision as of 18:03, 6 August 2013
Line 1:		Line 1:
	~~Hello~~, I'~~m Micaela~~, a ~~17 year old from Brafferton~~, ~~United Kingdom~~.<br>~~My hobbies include~~ (~~but~~ are ~~not limited~~ to) ~~Programming~~, ~~Cheerleading~~ and ~~watching Grey~~'s ~~Anatomy.~~<br><br>~~Feel free~~ to ~~visit my webpage~~ [http://www.~~pcs~~-~~systems~~.co.uk/~~Images~~/~~celinebag~~.~~aspx Cheap Celine Bags~~]		The '''Erdős–Gallai theorem''' is a result in [[graph theory]], a branch of [[combinatorics]], that gives a necessary and sufficient condition for a [[finite sequence]] of [[natural number]]s to be the [[Degree (graph theory)#Degree sequence\|degree sequence]] of a [[simple graph]]; a sequence obeying these conditions is called "graphic". The theorem was published in 1960 by [[Paul Erdős]] and [[Tibor Gallai]], after whom it is named.

			==Theorem statement==
			A sequence of non-negative [[integer]]s <math>d_1\geq\cdots\geq d_n</math> can be represented as the degree sequence of a finite [[simple graph]] on ''n'' vertices if and only if <math>d_1+\cdots+d_n</math> is even and

			: <math>
			\sum^{k}_{i=1}d_i\leq k(k-1)+ \sum^n_{i=k+1} \min(d_i,k)
			</math>

			holds for <math>1\leq k\leq n</math>.

			==Proofs==
			It is not difficult to show that the conditions of the Erdős–Gallai theorem are necessary for a sequence of numbers to be graphic. The requirement that the sum of the degrees be even is the [[handshaking lemma]], already used by Euler in his 1736 paper on the [[bridges of Königsberg]]. The inequality between the sum of the <math>k</math> largest degrees and the sum of the remaining degrees can be established by [[double counting (proof technique)\|double counting]]: the left side gives the numbers of edge-vertex adjacencies among the <math>k</math> highest-degree vertices, each such adjacency must either be on an edge with one or two high-degree endpoints, the <math>k(k-1)</math> term on the right gives the maximum possible number of edge-vertex adjacencies in which both endpoints have high degree, and the remaining term on the right upper bounds the number of edges that have exactly one high degree endpoint. Thus, the more difficult part of the proof is to show that, for any sequence of numbers obeying these conditions, there exists a graph for which it is the degree sequence.

			The original proof of {{harvtxt\|Erdős\|Gallai\|1960}} was long and involved. {{harvtxt\|Choudom\|1986}} cites a shorter proof by [[Claude Berge]], based on ideas of [[flow network\|network flow]]. Choudom instead provides a proof by [[mathematical induction]] on the sum of the degrees: he lets <math>t</math> be the first index of a number in the sequence for which <math>d_t > d_{t+1}</math> (or the penultimate number if all are equal), uses a case analysis to show that the sequence formed by subtracting one from <math>d_t</math> and from the last number in the sequence (and removing the last number if this subtraction causes it to become zero) is again graphic, and forms a graph representing the original sequence by adding an edge between the two positions from which one was subtracted.

			{{harvtxt\|Tripathi\|Venugopalan\|West\|2010}} consider a sequence of "subrealizations", graphs whose degrees are upper bounded by the given degree sequence. They show that, if ''G'' is a subrealization, and ''i'' is the smallest index of a vertex in ''G'' whose degree is not equal to ''d<sub>i</sub>'', then ''G'' may be modified in a way that produces another subrealization, increasing the degree of vertex ''i'' without changing the degrees of the earlier vertices in the sequence. Repeated steps of this kind must eventually reach a realization of the given sequence, proving the theorem.

			==Relation to integer partitions==
			{{harvtxt\|Aigner\|Triesch\|1994}} describe close connections between the Erdős–Gallai theorem and the theory of [[Partition (number theory)\|integer partitions]].
			Let <math>m=\sum d_i</math>; then the sorted integer sequences summing to <math>m</math> may be interpreted as the partitions of <math>m</math>. Under [[majorization]] of their [[prefix sum]]s, the partitions form a [[Lattice (order)\|lattice]], in which the minimal change between an individual partition and another partition lower in the partition order is to subtract one from one of the numbers <math>d_i</math> and add it to a number <math>d_{i+1}</math> that is smaller by at least two. As Aigner and Triesch show, this operation preserves the property of being graphic, so to prove the Erdős–Gallai theorem it suffices to characterize the graphic sequences that are maximal in this majorization order. They provide such a characterization, in terms of the [[Ferrers diagram]]s of the corresponding partitions, and show that it is equivalent to the Erdős–Gallai theorem.

			==References==
			*{{citation
			\| last1 = Aigner \| first1 = Martin
			\| last2 = Triesch \| first2 = Eberhard
			\| doi = 10.1016/0012-365X(94)00104-Q
			\| issue = 1-3
			\| journal = Discrete Mathematics
			\| mr = 1313278
			\| pages = 3–20
			\| title = Realizability and uniqueness in graphs
			\| volume = 136
			\| year = 1994}}.
			*{{citation
			\| last = Choudum \| first = S. A. \| author-link = S. A. Choudum
			\| doi = 10.1017/S0004972700002872
			\| issue = 1
			\| journal = Bulletin of the Australian Mathematical Society
			\| mr = 823853
			\| pages = 67–70
			\| title = A simple proof of the Erdős-Gallai theorem on graph sequences
			\| volume = 33
			\| year = 1986}}.
			*{{citation
			\| last1 = Erdős \| first1 = P. \| author1-link = Paul Erdős
			\| last2 = Gallai \| first2 = T. \| author2-link = Tibor Gallai
			\| journal = Matematikai Lapok
			\| pages = 264–274
			\| title = Gráfok előírt fokszámú pontokkal
			\| url = http://www.renyi.hu/~p_erdos/1961-05.pdf
			\| volume = 11
			\| year = 1960}}.
			*{{citation
			\| last1 = Tripathi \| first1 = Amitabha
			\| last2 = Venugopalan \| first2 = Sushmita
			\| last3 = West \| first3 = Douglas B. \| author3-link = Douglas West (mathematician)
			\| doi = 10.1016/j.disc.2009.09.023
			\| issue = 4
			\| journal = Discrete Mathematics
			\| mr = 2574834
			\| pages = 843–844
			\| title = A short constructive proof of the Erdős-Gallai characterization of graphic lists
			\| url = http://www.math.uiuc.edu/~west/pubs/tripathi.ps
			\| volume = 310
			\| year = 2010}}

			{{DEFAULTSORT:Erdos-Gallai theorem}}
			[[Category:Paul Erdős]]
			[[Category:Theorems in graph theory]]

en>Bender2k14: Intro: added a wiki-link

2012-08-31T17:22:07Z

Intro: added a wiki-link

New page

Hello, I'm Micaela, a 17 year old from Brafferton, United Kingdom.<br>My hobbies include (but are not limited to) Programming, Cheerleading and watching Grey's Anatomy.<br><br>Feel free to visit my webpage [http://www.pcs-systems.co.uk/Images/celinebag.aspx Cheap Celine Bags]

FKT algorithm - Revision history

en>Bender2k14: /* Generalizations */ improved wording

en>Dricherby: /* History */ "Temperley-Fisher" → "Temperley and Fisher" – it's two people, not a double-barrelled surname.

en>Bender2k14: Intro: added a wiki-link