Search results
Jump to navigation
Jump to search
Page title matches
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 06:10, 22 November 2017
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 05:55, 12 November 2019
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 08:55, 4 May 2023
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...21 KB (3,922 words) - 01:04, 3 November 2011
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...21 KB (3,922 words) - 08:56, 20 May 2013
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...21 KB (3,922 words) - 10:31, 16 April 2014
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...19 KB (3,541 words) - 07:47, 25 December 2015
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 05:10, 9 November 2016
Page text matches
- #REDIRECT [[组合数学 (Fall 2011)/Extremal graph theory]] ...60 bytes (5 words) - 02:58, 17 August 2011
- [[File:London Underground Zone 2.png|thumb|Real-world example of a graph: The central part of the [[London Underground]] map.]] ...rection are called ''undirected'', and the graph is called an ''undirected graph''. If two vertices are connected by an edge, they are called ''adjacent''. ...3 KB (488 words) - 18:43, 22 August 2017
- * Diestel. G''raph Theory, <font color=red>3rd edition or later</font>.'' Springer-Verlag. (If you on ...vits, and Szemerédi. '''The Regularity Lemma and Its Applications in Graph Theory.''' ''Theoretical Aspects of Computer Science'', 2002. [[media:Regularity.a ...887 bytes (120 words) - 10:20, 4 January 2011
- * 概率论（Probability Theory） # [[组合数学 (Spring 2016)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]]（ [http://tcs.nju.edu.cn/slides/comb2016/Polya.pdf ...6 KB (479 words) - 10:20, 12 September 2017
- * 概率论（Probability Theory） # [[组合数学 (Spring 2014)/Pólya's theory of counting|Pólya's theory of counting]] ...9 KB (998 words) - 05:12, 11 June 2014
- * 概率论（Probability Theory） # [[组合数学 (Fall 2011)/Pólya's theory of counting|Pólya's theory of counting]] ...13 KB (1,447 words) - 12:47, 15 September 2017
- * 概率论（Probability Theory） # [[组合数学 (Spring 2013)/Pólya's theory of counting|Pólya's theory of counting]] | [http://tcs.nju.edu.cn/slides/comb2013/comb6.pdf slides1] | ...11 KB (1,243 words) - 12:46, 15 September 2017
- * 概率论（Probability Theory） # [[组合数学 (Spring 2015)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]]（ [http://tcs.nju.edu.cn/slides/comb2015/PolyaTheor ...11 KB (1,070 words) - 12:46, 15 September 2017
- * 概率论（Probability Theory） # [[组合数学 (Fall 2017)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] （ [http://tcs.nju.edu.cn/slides/comb2017/Polya.pdf ...11 KB (1,223 words) - 07:38, 2 January 2018
- [[File:Fixed point example.svg|thumb|A graph of a function with three fixed points]] [[Category:Systems theory]] ...528 bytes (80 words) - 09:20, 13 July 2013
- * 概率论（Probability Theory） # [[Combinatorics (Fall 2010)/Extremal set theory|Extremal set theory]] | [http://lamda.nju.edu.cn/yinyt/notes/comb2010/comb8.pdf slides] ...12 KB (1,494 words) - 14:27, 3 September 2011
- * 概率论（Probability Theory） # [[组合数学 (Fall 2019)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] （ [http://tcs.nju.edu.cn/slides/comb2019/Polya.pdf ...12 KB (1,290 words) - 06:43, 27 December 2019
- ...dges, and girth at least <math> k </math>. (Hint: Try to generate a random graph with <math> n </math> vertices and then fix things up!) Let <math>G = (V, E)</math> be an undirected graph and suppose each <math>v \in V</math> is ...3 KB (522 words) - 11:43, 16 May 2023
- * 概率论（Probability Theory） # [[组合数学 (Fall 2023)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2023/Polya.pdf ...14 KB (1,438 words) - 18:58, 9 April 2024
- ...search problems in graphs, and has theoretical significance in complexity theory. The problem can be solved deterministically by traversing the graph <math>G(V,E)</math>, which takes <math>\Omega(n)</math> extra space to keep ...3 KB (468 words) - 10:48, 29 December 2011
- ...been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikip Consider an undirected (multi-)graph <math>G(V,E)</math>, where the parallel edges between two vertices are allo ...8 KB (1,407 words) - 02:23, 25 July 2011
- == Problem 3 (Probability meets graph theory) == ...math>1</math> (as <math>n</math> tends to infinity) the Erdős–Rényi random graph <math>\mathbf{G}(n,p)</math> has the property that every pair of its vertic ...7 KB (1,107 words) - 07:46, 25 April 2023
- Consider a graph <math>G(V,E)</math> which is randomly generated as: Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi ...11 KB (2,031 words) - 01:33, 24 July 2011
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 05:10, 9 November 2016
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 05:55, 12 November 2019
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 08:55, 4 May 2023
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...18 KB (3,527 words) - 06:10, 22 November 2017
- ...llest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''. Prove that: Suppose that <math>M,M'</math> are matchings in a bipartite graph <math>G</math> with bipartition <math>A,B</math>. Suppose that all the vert ...2 KB (461 words) - 02:48, 10 June 2023
- == Extremal Graph Theory == Extremal grap theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" ...21 KB (3,921 words) - 08:23, 13 November 2010
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...19 KB (3,541 words) - 07:47, 25 December 2015
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...21 KB (3,922 words) - 01:04, 3 November 2011
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...21 KB (3,922 words) - 08:56, 20 May 2013
- Extremal graph theory studies the problems like "how many edges that a graph <math>G</math> can have, if <math>G</math> has some property?" :Suppose <math>G(V,E)</math> is graph on <math>n</math> vertice without triangles. Then <math>|E|\le\frac{n^2}{4} ...21 KB (3,922 words) - 10:31, 16 April 2014
- == Graph Expansion == ...been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikip ...15 KB (2,745 words) - 10:19, 4 January 2011
- #* [[随机算法 (Fall 2011)/Graph Connectivity|Graph Connectivity]] #* [[随机算法 (Fall 2011)/Graph Coloring|Graph Coloring]] ...12 KB (1,037 words) - 12:45, 15 September 2017
- == Problem 5 (Probability meets graph theory) == <li>[<strong>Erdős–Rényi random graph</strong>] ...14 KB (2,403 words) - 10:41, 7 April 2023
- Consider a graph <math>G(V,E)</math> which is randomly generated as: Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi ...23 KB (4,153 words) - 08:30, 12 October 2010
- Consider a graph <math>G(V,E)</math> which is randomly generated as: Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi ...23 KB (4,153 words) - 08:18, 16 August 2011
- ...results in spectral graph theory is the following theorem which relate the graph expansion to the spectral gap. :Let <math>G</math> be a <math>d</math>-regular graph with spectrum <math>\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n</math>. Then ...14 KB (2,683 words) - 15:16, 13 December 2011
- * 概率论（Probability Theory） # [[组合数学 (Fall 2024)/Pólya's theory of counting|Pólya's theory of counting | Pólya计数法]] ([http://tcs.nju.edu.cn/slides/comb2024/Polya.pdf ...9 KB (950 words) - 18:42, 29 April 2024
- ...he problem and an output is called a '''solution''' to that instance. The theory of complexity deals almost exclusively with [http://en.wikipedia.org/wiki/D ...itself is a certificate. And for the later one, a Hamiltonian cycle in the graph is a certificate (given a cycle, it is easy to verify whether it is Hamilto ...11 KB (1,828 words) - 06:00, 27 August 2011
- ...h> and <math>W</math> denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions <math>m</math> is <m :In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with <math>\ti ...16 KB (900 words) - 04:52, 13 November 2020
- ...h> and <math>W</math> denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions <math>m</math> is <m :In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with <math>\ti ...16 KB (900 words) - 04:54, 13 November 2020
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...19 KB (3,610 words) - 08:59, 28 May 2014
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...19 KB (3,610 words) - 14:17, 19 June 2013
- #* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrá # Spectral graph theory and Cheeger's inequality ([[Media:L8 spectral-graph-theory.pdf|slides]]) ...13 KB (1,427 words) - 15:57, 9 January 2024
- ...[[Abstract algebra]] || [[Linear algebra]] || [[Order theory]] || [[Graph theory]] ...l equation]]s || [[Dynamical systems theory|Dynamical systems]] || [[Chaos theory]] ...9 KB (1,088 words) - 18:04, 22 August 2017
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 03:49, 24 October 2016
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 09:24, 19 April 2013
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 09:36, 2 April 2014
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 09:37, 9 November 2015
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 08:14, 16 October 2019
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 12:56, 18 April 2023
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 02:36, 31 October 2017
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...14 KB (2,455 words) - 13:27, 9 April 2024
- '''Probability Theory''' <br> & '''Mathematical Statistics'''</font> This is the webpage for the ''Probability Theory and Mathematical Statistics'' (概率论与数理统计) class of Spring 2024. Students who ...15 KB (1,465 words) - 13:36, 30 April 2024
- == Problem 5 (Probability meets graph theory) == Let <math>G = (V, E)</math> be a <strong>fixed</strong> undirected graph without isolating vertex. ...14 KB (2,465 words) - 19:27, 13 April 2024
- * a directed graph <math>G(V,E)</math>; A fundamental fact in flow theory is that cuts always upper bound flows. ...15 KB (3,049 words) - 03:53, 17 August 2011
- ...h> and <math>W</math> denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions <math>m</math> is <m :In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with <math>\ti ...20 KB (1,328 words) - 14:52, 20 November 2020
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...17 KB (3,025 words) - 11:53, 21 November 2011
- [[File:Hyperbola E.svg|thumb|The area shown in blue (under the graph of the equation y=1/x) stretching from 1 to e is exactly 1.]] [[Category:Number theory]] ...3 KB (351 words) - 09:48, 24 June 2017
- * [http://theory.stanford.edu/~yuhch123/ Huacheng Yu] (Harvard) |align="center"|[http://theory.stanford.edu/~yuhch123/ Huacheng Yu] (俞华程)<br> ...14 KB (1,850 words) - 01:51, 7 May 2018
- ...been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikip Consider an undirected (multi-)graph <math>G(V,E)</math>, where the parallel edges between two vertices are allo ...34 KB (6,244 words) - 15:28, 8 June 2013
- Consider a graph <math>G(V,E)</math> which is randomly generated as: Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi ...21 KB (3,837 words) - 09:44, 1 April 2013
- ...article. The number following the name of the group is the [[order (group theory)|order]] of the group. | [[File:Complete graph K5.svg|105px]] ...8 KB (1,007 words) - 05:56, 15 September 2016
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...33 KB (6,636 words) - 05:50, 13 June 2023
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...33 KB (6,643 words) - 07:40, 18 December 2017
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...33 KB (6,643 words) - 10:48, 4 December 2016
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...33 KB (6,643 words) - 11:00, 20 December 2019
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...33 KB (6,643 words) - 03:26, 22 December 2015
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...23 KB (4,382 words) - 05:07, 5 November 2010
- ...s usually stated as a theorem for the existence of matching in a bipartite graph. In a graph <math>G(V,E)</math>, a '''matching''' <math>M\subseteq E</math> is an indep ...23 KB (4,382 words) - 02:41, 17 August 2011
- ...been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikip Consider an undirected (multi-)graph <math>G(V,E)</math>, where the parallel edges between two vertices are allo ...37 KB (6,824 words) - 02:20, 29 December 2015
- == Graph Expansion == ...been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikip ...35 KB (6,195 words) - 08:39, 7 June 2010
- ...r function''' is a [[Function (mathematics)|function]] whose [[:wikt:graph|graph]] is a [[Line|straight line]] in 2-dimensions (see images).<ref>{{cite book ...a linear function is a function ''f''(''x''):'''R'''→'''R''' such that the graph of ''f'' is a line. This means the [[function (mathematics)|domain]] or inp ...14 KB (2,194 words) - 00:02, 2 January 2015
- ...been used in proofs of many important results in computational complexity theory, such as [http://en.wikipedia.org/wiki/SL_(complexity) SL]=[http://en.wikip Consider an undirected (multi-)graph <math>G(V,E)</math>, where the parallel edges between two vertices are allo ...41 KB (7,547 words) - 09:24, 22 May 2023
- In probability theory, the word "condition" is a verb. "Conditioning on the event ..." means that = Min-Cut in a Graph = ...22 KB (4,084 words) - 10:22, 6 March 2013
- ...l type of equation is called the function. This is often used in making [[graph]]s. ...mber or numbers into and get a certain number out. When using functions, [[graph]]s can be powerful tools in helping us to study the solutions to equations. ...13 KB (2,204 words) - 07:13, 30 July 2017
- ...ing a leaf (along with the edge adjacent to it) from a tree, the resulting graph is still a tree. :let <math>T</math> be empty graph, and <math>v_{n-1}=n</math>; ...21 KB (3,832 words) - 15:23, 7 October 2011
- '''Probability Theory''' <br> & '''Mathematical Statistics'''</font> This is the webpage for the ''Probability Theory and Mathematical Statistics'' (概率论与数理统计) class of Spring 2023. Students who ...21 KB (2,167 words) - 07:44, 27 February 2024
- Consider a graph <math>G(V,E)</math> which is randomly generated as: Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi ...22 KB (3,809 words) - 05:34, 19 March 2014
- * a directed graph <math>G(V,E)</math>; A fundamental fact in flow theory is that cuts always upper bound flows. ...21 KB (4,167 words) - 09:57, 4 January 2011
- In probability theory, the word "condition" is a verb. "Conditioning on the event ..." means that = Min-Cut in a Graph = ...26 KB (4,800 words) - 06:38, 3 March 2014
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...16 KB (2,818 words) - 01:52, 4 December 2016
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...16 KB (2,818 words) - 11:51, 5 June 2013
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...16 KB (2,818 words) - 07:52, 21 May 2014
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...16 KB (2,818 words) - 05:42, 11 December 2019
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...16 KB (2,818 words) - 12:03, 15 December 2015
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...16 KB (2,818 words) - 11:41, 10 December 2017
- Consider a graph <math>G(V,E)</math> which is randomly generated as: Such graph is denoted as '''<math>G(n,p)</math>'''. This is called the '''Erdős–Rényi ...29 KB (5,238 words) - 05:34, 13 November 2015
- <li>[<strong>Chernoff bound meets graph theory</strong>] ...pproaching 1 (as <math>n</math> tends to infinity), the Erdős–Rényi random graph <math>\textbf{G}(n,1/2)</math> has the property that the maximum degree is ...13 KB (2,150 words) - 08:49, 7 June 2023
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...>v</math> shakes hand. The handshaking lemma states that in any undirected graph, the number of vertices whose degrees are odd is even. It is sufficient to ...26 KB (4,583 words) - 04:53, 7 October 2010
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...23 KB (4,275 words) - 12:28, 1 December 2010
- ==== Transition graph ==== ...eighted directed graph <math>G(V,E,w)</math> is said to be a '''transition graph''' of a finite Markov chain with transition matrix <math>P</math> if: ...37 KB (6,516 words) - 08:40, 7 June 2010
- == Transition graph == ...eighted directed graph <math>G(V,E,w)</math> is said to be a '''transition graph''' of a finite Markov chain with transition matrix <math>P</math> if: ...40 KB (7,046 words) - 10:00, 13 December 2015
- == Transition graph == ...eighted directed graph <math>G(V,E,w)</math> is said to be a '''transition graph''' of a finite Markov chain with transition matrix <math>P</math> if: ...40 KB (7,046 words) - 08:04, 2 June 2014
- == Transition graph == ...eighted directed graph <math>G(V,E,w)</math> is said to be a '''transition graph''' of a finite Markov chain with transition matrix <math>P</math> if: ...40 KB (7,049 words) - 15:11, 8 June 2013
- In probability theory, the '''total variation distance''' measures the difference between two pro Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing ...27 KB (4,881 words) - 07:04, 2 June 2014
- In probability theory, the '''total variation distance''' measures the difference between two pro Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing ...27 KB (4,881 words) - 13:52, 31 July 2013
- ...The function ''f'' is a surjection if every horizontal line intersects the graph of ''f'' in at least one point. ...,''y'')):ℝ²→ℝ defined by ''z''=''y'' is a surjection. Its graph is a plane in 3-dimensional space. The pre-image of ''z''<sub>o</sub> is t ...10 KB (1,438 words) - 06:38, 8 October 2016
- ...re the challenges that arise at the interface of machine learning and game theory: selfish agents may interact with machine learning algorithms strategically ...on of "fairness" in real-world applications and how to model "fairness" in theory. Then I will present several recent progress in designing algorithms that m ...12 KB (1,731 words) - 06:09, 29 April 2019
- *[[set theory]] *[[Banach space]] theory ...16 KB (2,241 words) - 05:01, 18 January 2017
- ...he problem and an output is called a '''solution''' to that instance. The theory of complexity deals almost exclusively with [http://en.wikipedia.org/wiki/D ...itself is a certificate. And for the later one, a Hamiltonian cycle in the graph is a certificate (given a cycle, it is easy to verify whether it is Hamilto ...25 KB (4,263 words) - 08:43, 7 June 2010
- ...om walk on an undirected graph is determined by the expansion ratio of the graph. We now consider the random walks in a more general setting, and study the ...the transition matrix <math>P</math> instead of the adjacency matrix of a graph. With the same argument as the spectrum of graphs, we can show that <math>\ ...27 KB (4,860 words) - 03:17, 22 March 2011
- ...The function ''f'' is a bijection if every horizontal line intersects the graph of ''f'' in '''exactly''' one point. ...very horizontal line (in the codomain) intersects exactly one point of the graph. ...11 KB (1,621 words) - 07:51, 17 July 2016
- .../Expander Graphs and Mixing|Expander Graphs and Mixing]]: expander graphs, graph spectrum, spectral gap, Cheeger's inequality, rapid mixing of expander walk = The Probability Theory Toolkit = ...9 KB (893 words) - 12:43, 15 September 2017
- * a directed graph <math>G(V,E)</math>; A fundamental fact in flow theory is that cuts always upper bound flows. ...30 KB (5,740 words) - 05:12, 11 June 2014
- * a directed graph <math>G(V,E)</math>; A fundamental fact in flow theory is that cuts always upper bound flows. ...30 KB (5,740 words) - 14:29, 19 June 2013
- .../Expander Graphs and Mixing|Expander Graphs and Mixing]]: expander graphs, graph spectrum, spectral gap, Cheeger's inequality, rapid mixing of expander walk = The Probability Theory Toolkit = ...9 KB (846 words) - 07:34, 2 June 2014
- = Graph Coloring = A '''coloring''' of a graph <math>G(V,E)</math> is a mapping <math>\sigma:V\rightarrow[q]</math> for so ...29 KB (4,994 words) - 01:21, 29 August 2011
- .../Expander Graphs and Mixing|Expander Graphs and Mixing]]: expander graphs, graph spectrum, spectral gap, Cheeger's inequality, rapid mixing of expander walk = The Probability Theory Toolkit = ...10 KB (1,029 words) - 12:44, 15 September 2017
- ...nt is adjacent to the events which are dependent with it in the dependency graph. |Definition (dependency graph)| ...31 KB (5,614 words) - 12:29, 8 December 2015
- Formally, a boolean circuit is a directed acyclic graph. Nodes with indegree zero are input nodes, labeled <math>x_1, x_2, \ldots , ...ns that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a t ...33 KB (6,039 words) - 08:41, 7 June 2010
- == Principles in probability theory == * '''Basics of probability theory''': probability space, events, the union bound, independence, conditional p ...22 KB (3,591 words) - 10:45, 4 March 2013
- == Principles in probability theory == * '''Basics of probability theory''': probability space, events, the union bound, independence, conditional p ...22 KB (3,591 words) - 03:54, 17 February 2014
- === Ramsey's theorem for graph === {{Theorem|Ramsey's Theorem (graph, multicolor)| ...25 KB (4,530 words) - 12:14, 26 May 2023
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...33 KB (6,227 words) - 06:15, 30 September 2019
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...33 KB (6,227 words) - 12:45, 16 March 2023
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...33 KB (6,227 words) - 11:45, 15 October 2017
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...33 KB (6,227 words) - 09:51, 19 March 2024
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...33 KB (6,227 words) - 07:00, 29 September 2016
- ...s]] (like [[light]]) work. It is also called "quantum physics" or "quantum theory". ...e to explain the light that comes from glowing [[hydrogen]]. The quantum [[theory]] of the [[atom]] also had to explain why the [[electron]] stays in its [[o ...36 KB (5,991 words) - 08:00, 24 August 2017
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...19 KB (3,458 words) - 07:33, 12 March 2014
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...19 KB (3,458 words) - 06:51, 12 October 2015
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...19 KB (3,458 words) - 06:18, 20 March 2013
- ;edge exposure in a random graph ...osure of a random graph, as we "exposing" the edges one by one in a random graph. ...50 KB (9,096 words) - 06:09, 8 December 2015
- ...ynchronized''', such that for each '''round''', every link (an edge of the graph) can forward at most one packet. ..., such that the number of edges is significantly smaller than the complete graph, yet the distance between any pair of vertices is small, so that the packet ...31 KB (5,481 words) - 03:52, 9 November 2010
- Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing ...-dimensional [http://en.wikipedia.org/wiki/Hypercube '''hypercube'''] is a graph on vertex set <math>\{0,1\}^n</math>. For any <math>x,y\in\{0,1\}^n</math>, ...13 KB (2,540 words) - 13:57, 10 August 2011
- In probability theory, the '''total variation distance''' measures the difference between two pro Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing ...23 KB (4,166 words) - 05:41, 22 December 2015
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...33 KB (6,205 words) - 01:11, 22 September 2011
- ...icted number (with the distance measured in standard deviations), then the theory being tested may not be right. See [[prediction interval]]. ...l curve''' because the numbers spread out to make the shape of a bell on a graph. ...12 KB (1,881 words) - 09:42, 29 May 2017
- We introduce a general theory of counting permutations with restricted positions. In the derangement prob ...permutation <math>\pi</math> of <math>\{1,\ldots,n\}</math>, define the '''graph''' <math>G_\pi(V,E)</math> as ...29 KB (5,077 words) - 04:54, 7 October 2010
- ...ie, Leipzig: Hirzel English translation The Physical Principles of Quantum Theory. Chicago: University of Chicago Press, 1930.</ref> ...f a reed) and there was an [[wikt:emit|emitted]] wave that could be [[wikt:graph|graphed]] as a [[wikt:sine|sine]] wave. Much of what had earlier been figur ...42 KB (7,065 words) - 02:42, 24 August 2017
- * Each instance is a (nonnegatively)weighted directed graph <math>G(V,E,w)</math> along with two distinct vertices <math>s,t\in V</math ...duling is a class of problems. We consider a central problem in scheduling theory: the '''minimum makespan scheduling'''. ...20 KB (3,484 words) - 05:14, 11 June 2010