Find link

language:

Find link is a tool written by Edward Betts.

searching for Constructive proof 59 found (93 total)

Kőnig's theorem (graph theory) (3,433 words) [view diff] exact match in snippet view article

size of a matching equals the smallest size of a vertex cover. The constructive proof described above provides an algorithm for producing a minimum vertex

Carlton E. Lemke (432 words) [view diff] exact match in snippet view article find links to article

{\displaystyle =0} at the optimum. This is the core method for his subsequent constructive proof(1964) that the number of Nash( bimatrix) equilibrium points is odd

Chinese remainder theorem (7,239 words) [view diff] exact match in snippet view article find links to article

large. The third one uses the existence proof given in § Existence (constructive proof). It is the most convenient when the product n 1 ⋯ n k {\displaystyle

Magic hexagon (1,114 words) [view diff] exact match in snippet view article find links to article

solution of order 3 is essentially unique. Meng gives a less intricate constructive proof. The order-3 magic hexagon has been published many times as a 'new'

Square root of 2 (6,115 words) [view diff] no match in snippet view article find links to article

The square root of 2 (approximately 1.4142) is the positive real number that, when multiplied by itself or squared, equals the number 2. It may be written

Bernstein polynomial (4,491 words) [view diff] exact match in snippet view article find links to article

Polynomials in Bernstein form were first used by Bernstein in a constructive proof for the Weierstrass approximation theorem. With the advent of computer

Puiseux series (5,542 words) [view diff] no match in snippet view article find links to article

In mathematics, Puiseux series are a generalization of power series that allow for negative and fractional exponents of the indeterminate. For example

Mohr–Mascheroni theorem (2,920 words) [view diff] no match in snippet view article find links to article

In mathematics, the Mohr–Mascheroni theorem states that any geometric construction that can be performed by a compass and straightedge can be performed

Poncelet–Steiner theorem (12,613 words) [view diff] exact match in snippet view article find links to article

the construction of new circular arcs with a compass. Usability The constructive proof does not merely serve as a proof of the theorem, but also demonstrates

Probability distribution of extreme points of a Wiener stochastic process (3,379 words) [view diff] exact match in snippet view article find links to article

H. J. Kusher (appendix 3, page 106) published in 1964. a detailed constructive proof appears in work of Dario Ballabio in 1978. This result was developed

Lesley Sibner (856 words) [view diff] exact match in snippet view article find links to article

fixed-point theorem. In 1974, Lesley and Robert Sibner produced a constructive proof of the Riemann–Roch theorem. Karen Uhlenbeck suggested that Lesley

Malgrange–Ehrenpreis theorem (833 words) [view diff] exact match in snippet view article find links to article

of the regularity properties of the fundamental solutions. A short constructive proof was presented in (Wagner 2009, Proposition 1, p. 458): E = 1 P m (

Tucker's lemma (869 words) [view diff] exact match in snippet view article find links to article

285–309, MR 0020254 Freund, Robert M.; Todd, Michael J. (1981), "A constructive proof of Tucker's combinatorial lemma", Journal of Combinatorial Theory

Gödel Prize (2,163 words) [view diff] exact match in snippet view article find links to article

ACM. 54 (3): 12–es. doi:10.1145/1236457.1236459. S2CID 53244523. "A constructive proof of the general Lovász Local Lemma". Journal of the ACM. 57 (2). 2010

Entropy compression (1,387 words) [view diff] exact match in snippet view article find links to article

be found in randomized polynomial time. Moser, Robin A. (2009), "A constructive proof of the Lovász local lemma", STOC'09—Proceedings of the 2009 ACM International

Bijective proof (400 words) [view diff] case mismatch in snippet view article find links to article

prescribed vertex degrees" – by Gilles Schaeffer. "Kathy O'Hara's Constructive Proof of the Unimodality of the Gaussian Polynomials" – by Doron Zeilberger

Law of excluded middle (5,615 words) [view diff] no match in snippet view article find links to article

use of proofs designed from "negative" or "non-existence" versus "constructive" proof: According to Brouwer, a statement that an object exists having a

Doron Zeilberger (676 words) [view diff] exact match in snippet view article find links to article

old-time blackboard talk". Zeilberger, Doron (1989). "Kathy O'Hara's constructive proof of the unimodality of the Gaussian polynomials". Amer. Math. Monthly

Mergelyan's theorem (536 words) [view diff] exact match in snippet view article find links to article

suggested by Mergelyan is constructive, and remains the only known constructive proof of the result.[citation needed] Arakelyan's theorem Hartogs–Rosenthal

Jean Écalle (646 words) [view diff] case mismatch in snippet view article find links to article

5802/aif.1287 "Six Lectures on Transseries, Analytical Functions and the Constructive Proof of Dulac's Conjecture", in D. Schlomiuk's Bifurcations and Periodic

Algorithmic Lovász local lemma (2,501 words) [view diff] exact match in snippet view article find links to article

for the sequential case. Moser, Robin A.; Tardos, Gábor (2010). "A constructive proof of the general lovász local lemma". Journal of the ACM. 57 (2): 1

Schur decomposition (1,518 words) [view diff] exact match in snippet view article find links to article

1 {\displaystyle H_{i}=QA_{i}Q^{-1}} is upper quasi-triangular. A constructive proof for the Schur decomposition is as follows: every operator A on a complex

Bounded mean oscillation (3,216 words) [view diff] exact match in snippet view article find links to article

{\displaystyle H^{1}} , in the noted paper Fefferman & Stein 1972: a constructive proof of this result, introducing new methods and starting a further development

Schottky group (1,224 words) [view diff] exact match in snippet view article find links to article

chosen to be circles. Marden (1974, 1977) gave an indirect and non-constructive proof of the existence of non-classical Schottky groups, and Yamamoto (1991)

Errett Bishop (1,639 words) [view diff] exact match in snippet view article find links to article

presents a challenge: to find a constructive version, and to give it a constructive proof." (Bishop 1967, Preface, page x) "Theorem 1 is the famous theorem

Proof assistant (1,206 words) [view diff] exact match in snippet view article find links to article

to find formal proofs, and extracts a certified program from the constructive proof of its formal specification. HOL theorem provers – A family of tools

Heyting arithmetic (6,285 words) [view diff] exact match in snippet view article find links to article

that all Peano arithmetic theorems have a proof that consists of a constructive proof followed by a classical logical rewriting. Roughly, the final step

Erdős–Gallai theorem (1,248 words) [view diff] exact match in snippet view article find links to article

Amitabha; Venugopalan, Sushmita; West, Douglas B. (2010), "A short constructive proof of the Erdős–Gallai characterization of graphic lists", Discrete Mathematics

Vizing's theorem (2,520 words) [view diff] exact match in snippet view article find links to article

1016/j.dam.2010.06.019, MR 2679785. Misra, J.; Gries, David (1992), "A constructive proof of Vizing's Theorem", Information Processing Letters, 41 (3): 131–133

Victoria Powers (754 words) [view diff] exact match in snippet view article find links to article

352, no. 10, 4677-4692. 2000 (with Bruce Reznick) "Notes towards a constructive proof of Hilbert's theorem on ternary quartics", Quadratic forms and their

Borsuk–Ulam theorem (2,497 words) [view diff] exact match in snippet view article find links to article

full exposition.) Freund, Robert M.; Todd, Michael J. (1982). "A constructive proof of Tucker's combinatorial lemma". Journal of Combinatorial Theory

Consensus (computer science) (4,770 words) [view diff] case mismatch in snippet view article

Bisping, Benjamin; et al. (2016), "Mechanical Verification of a Constructive Proof for FLP", in Blanchette, Jasmin Christian; Merz, Stephan (eds.), Interactive

Haar measure (5,375 words) [view diff] exact match in snippet view article find links to article

Sciences de Paris, 211: 759–762 Alfsen, E.M. (1963), "A simplified constructive proof of existence and uniqueness of Haar measure", Math. Scand., 12: 106–116

Knaster–Kuratowski–Mazurkiewicz lemma (2,396 words) [view diff] exact match in snippet view article find links to article

doi:10.1007/BF01769865. S2CID 154888988. Bapat, R. B. (1989). "A constructive proof of a permutation-based generalization of Sperner's lemma". Mathematical

Hall violator (1,129 words) [view diff] exact match in snippet view article find links to article

found, or the matching M saturates all vertices of X. This provides a constructive proof to Hall's theorem. An application of Hall violators in constraint

Stone–Weierstrass theorem (3,234 words) [view diff] exact match in snippet view article find links to article

|f(x) − p(x)| < ε, or equivalently, the supremum norm ‖f − p‖ < ε. A constructive proof of this theorem using Bernstein polynomials is outlined on that page

Eilenberg–MacLane space (3,357 words) [view diff] exact match in snippet view article find links to article

f^{*}u} . This is similar to the Yoneda lemma of category theory. A constructive proof of this theorem can be found here, another making use of the relation

Jakob Stoustrup (1,528 words) [view diff] exact match in snippet view article find links to article

systems provides a positive answer to a previously open problem. By a constructive proof it is established that under mild conditions, a feedback controller

Type theory (8,246 words) [view diff] exact match in snippet view article find links to article

and its proof requires a term of that type. An example of a non-constructive proof is proof by contradiction. The first step is assuming that x {\displaystyle

Kervaire invariant (2,352 words) [view diff] exact match in snippet view article find links to article

with explicit constructions in dimensions 2, 6, 14, 30, and a non-constructive proof in dimension 62, this left open only dimension 126. This dimension

Game theory (15,399 words) [view diff] no match in snippet view article find links to article

numbers, as well as combinatorial and algebraic (and sometimes non-constructive) proof methods to solve games of certain types, including "loopy" games

Dividing a square into similar rectangles (570 words) [view diff] exact match in snippet view article find links to article

conjugates must have a positive real part. However, their proof was not a constructive proof. Numerous participants have attacked the problem of finding individual

Fourier series (11,149 words) [view diff] exact match in snippet view article find links to article

pointwise. The uniform boundedness principle yields a simple non-constructive proof of this fact. In 1922, Andrey Kolmogorov published an article titled

Black hole information paradox (8,927 words) [view diff] exact match in snippet view article find links to article

Masaki; Warner, Nicholas P. (May 2015). "Habemus Superstratum! A constructive proof of the existence of superstrata". Journal of High Energy Physics.

Sperner's lemma (4,087 words) [view diff] exact match in snippet view article find links to article

1016/0097-3165(77)90081-4. ISSN 0097-3165. Bapat, R. B. (1989). "A constructive proof of a permutation-based generalization of Sperner's lemma". Mathematical

Expander graph (5,344 words) [view diff] exact match in snippet view article find links to article

alternative construction of bipartite Ramanujan graphs. The original non-constructive proof was turned into an algorithm by Michael B. Cohen. Later the method

Misra & Gries edge coloring algorithm (1,506 words) [view diff] exact match in snippet view article find links to article

O(|E|+|E||V|)=O(|E||V|)} . Misra, Jayadev; Gries, David (1992). "A constructive proof of Vizing's theorem" (PDF). Information Processing Letters. 41 (3):

Oval (projective plane) (4,186 words) [view diff] exact match in snippet view article

than the group given by Hall. Korchmáros (1978) independently gave a constructive proof of this result and also showed that in Desarguesian planes, the Lunelli-Sce

Edge coloring (8,472 words) [view diff] exact match in snippet view article find links to article

doi:10.1016/0095-8956(73)90016-6. Misra, J.; Gries, David (1992), "A constructive proof of Vizing's Theorem", Information Processing Letters, 41 (3): 131–133

Banach–Alaoglu theorem (8,306 words) [view diff] exact match in snippet view article find links to article

separable case (see above): in this case there actually exists a constructive proof. In the general case of an arbitrary normed space, the ultrafilter

Debreu's representation theorems (2,667 words) [view diff] exact match in snippet view article find links to article

unique up to an increasing linear transformation. For an intuitive constructive proof, see Ordinal utility - Additivity with three or more goods. Theorem

Resolution of singularities (5,480 words) [view diff] exact match in snippet view article find links to article

S2CID 122056627 Bierstone, Edward; Milman, Pierre D. (1991), "A simple constructive proof of Canonical Resolution of Singularities", in Mora, T.; Traverso,

Subcountability (3,589 words) [view diff] exact match in snippet view article find links to article

detachable from N {\displaystyle {\mathbb {N} }} may be permitted. A constructive proof is also classically valid. If a set is proven uncountable constructively

Polynomial interpolation (9,027 words) [view diff] exact match in snippet view article find links to article

value p(a) with complexity O(n2). The Bernstein form was used in a constructive proof of the Weierstrass approximation theorem by Bernstein and has gained

Minimal logic (4,334 words) [view diff] exact match in snippet view article find links to article

((A\lor B)\land \neg A)\to B.} This can be read as follows: Given a constructive proof of A ∨ B {\displaystyle A\lor B} and constructive rejection of A {\displaystyle

Kolmogorov–Arnold representation theorem (3,963 words) [view diff] exact match in snippet view article find links to article

Problem, in Full Colour". Braun, Jürgen; Griebel, Michael (2009). "On a constructive proof of Kolmogorov's superposition theorem". Constructive Approximation

Constructive set theory (35,221 words) [view diff] exact match in snippet view article find links to article

form A ∪ { x ∣ x ∉ A } {\displaystyle A\cup \{x\mid x\notin A\}} . A constructive proof that it is in that class contains information. Now if A {\displaystyle

Incompressibility method (3,534 words) [view diff] exact match in snippet view article find links to article

birthday). North-Holland. pp. 609–627. R. A. Moser, G. Tardos, "A constructive proof of the general lovász local lemma", Journal of the ACM (JACM), 2:57(2010)

List of women in mathematics (23,258 words) [view diff] exact match in snippet view article find links to article

(1934–2013), American differential geometer and Hodge theorist, produced a constructive proof of the Riemann–Roch theorem Martha Siegel, American probability theorist