✦ LIBER ✦

On existence theorems

✍ Scribed by Svatopluk Poljak

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 849 KB
Volume: 111
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90180-2

No coin nor oath required. For personal study only.

✦ Synopsis

We discuss the question of constructive proofs, or polynomial-time algorithms, for theorems which were proved earlier nonconstructively.

We present a forma1 model for such statements and give a collection of examples. In a greater detail, we deal with the problem of finding another Hamiltonian cycle in a cubic graph provided that one cycle is already known. A relation to combinatorial optimization is also considered.

📜 SIMILAR VOLUMES

A General Theorem on Existence Theorems

✍ Martin Stein 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 821 KB

On the existence of Borsuk-Ulam theorems

✍ Thomas Bartsch 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 944 KB

On fixed point theorems obtained from ex

On fixed point theorems obtained from existence theorems for differential equations

✍ Simeon Reich 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 575 KB

Existence theorems in micropolar elastos

Existence theorems in micropolar elastostatics

✍ D. Ieşan 📂 Article 📅 1971 🏛 Elsevier Science 🌐 English ⚖ 967 KB

Comparison theorems and existence theore

Comparison theorems and existence theorems for ordinary differential equations

✍ Allan C Peterson 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 507 KB

Some existence theorems for t-designs

✍ Tran van Trung 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 640 KB

We generalize some existence theorems for t- (u,k,l) designs. In fact, we prove that if certain inequality holds involving parameters of some simple r-designs, then new simple t-designs can be constructed. Using these results we discover first examples of infinite families of 5-designs in which blo