Planar graphs,Hamilton cycles and extreme independence number

If a graph has too many edges, it must be Hamiltonian. We show how to construct graphs near the threshold: they have as many edges as possible without sacrificing planarity but are not Hamiltonian. We base our construction on the concepts of independent sets and 1-toughness.The work of the author was partially supported by CNPq-Brasil.     

R andRτ ratios at the five-loop level of perturbative QCD

We study perturbative QCD at the five-loop level. In particular we considerR = _tot(e ⁺ e ^– hadrons)/(e ⁺ e ^{– + –}) andR = ( v+hadrons)/( ev). We use our method to estimate the five-loop coefficients. As a result, we obtain _s (M _z ) = 0.1186(11) and _s (34 GeV) = 0.1396(16), which are accurate at the 1% level. We also findR = 3.8350(18), which is consistent withR and is accurate to 0.05%.     

Cutting planes,connectivity, and threshold logic

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP _q ofCP, forq2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP ₂-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE ⁺, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem.Supported in part by NSF grant DMS-9205181 and by US-Czech Science and Technology Grant 93-205Partially supported by NSF grant CCR-9102896 and by US-Czech Science and Technology Grant 93-205     

Aurifeuillian factorizations and the period of the Bell numbers modulo a prime

We show that the minimum period modulo of the Bell exponential integers is for all primes and several larger . Our proof of this result requires the prime factorization of these periods. For some primes the factoring is aided by an algebraic formula called an Aurifeuillian factorization. We explain how the coefficients of the factors in these formulas may be computed.