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} ...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
- 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
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) - 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
- 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
- ...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) - 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
- 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
- '''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) - 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 ...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 ...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) - 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
- === 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
- 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