Other Proofs of Old Results

We transform the proof of the second incompleteness theorem given in [3] to a proof-theoretic version, avoiding the use of the arithmetized completeness theorem. We give also new proofs of old results: The Arithmetical Hierarchy Theorem and Tarski's Theorem on undefinability of truth; the proofs in which the construction of a sentence by means of diagonalization lemma is not needed.     

Generalized Kneser coloring theorems with combinatorial proofs

The Kneser conjecture (1955) was proved by Lovász (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matoušek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization by (hyper)graph coloring theorems of Dol’nikov, Alon-Frankl-Lovász, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver’s theorem. Oblatum 17-IV-2001 & 12-IX-2001?Published online: 19 November 2001 An erratum to this article is available at .     

A note on a Brooks' type theorem for DP-coloring

Dvořák and Postle introduced DP-coloring of simple graphs as a generalization of list-coloring. They proved a Brooks' type theorem for DP-coloring; and Bernshteyn, Kostochka, and Pron extended it to DP-coloring of multigraphs. However, detailed structure, when a multigraph does not admit DP-coloring, was not specified. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs.     

The chords theorem recalled to life at the turn of the eighteenth century

This paper is a historical account of the chords theorem, for conic sections from Apollonius to Boscovich. We comment the most significant proofs and applications, focusing on Newton's solution of the Pappus four lines problem. Newton's geometrical achievements drew L'Hospital's attention to the chords theorem as a fundamental one, and led him to search for a simple and direct proof, that he finally obtained by the method of projection. Stirling gave a very elegant algebraic proof; then Boscovich succeeded in finding an almost immediate geometrical proof, and showed how to develop the elements of conic sections starting from this theorem.     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002     

Brooks' Theorem and Beyond

We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon–Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin–Kostochka Conjecture and Reed's Conjecture.     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

List multicolorings of graphs with measurable sets

In an ordinary list multicoloring of a graph, the vertices are “colored” with subsets of pre‐assigned finite sets (called “lists”) in such a way that adjacent vertices are colored with disjoint sets. Here we consider the analog of such colorings in which the lists are measurable sets from an arbitrary atomless, semifinite measure space, and the color sets are to have prescribed measures rather than prescribed cardinalities. We adapt a proof technique of Bollobás and Varopoulos to prove an analog of one of the major theorems about ordinary list multicolorings, a generalization and extension of Hall's marriage theorem, due to Cropper, Gyárfás, and Lehel. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 179–193, 2007     

Existence and Numerical Solutions of Nonlinear Quadratic Integral Equations Defined on Unbounded Intervals

The first goal of this article is to discuss the existence of solutions of nonlinear quadratic integral equations. These equations are considered in the Banach space L ^p (?₊). The arguments used in the existence proofs are based on Schauder's and Darbo's fixed point theorems. In particular, to apply Schauder's fixed point theorem based method, a special care is devoted to the proof of the L ^p -compactness of the operators associated with our nonlinear quadratic integral equations. The second goal of this work is to study a numerical method for solving nonlinear Volterra integral equations of a fairly general type. Finally, we provide the reader with some examples that illustrate the different results of this work.     

Some examples of application of the metric entropy method

We show how the metric entropy method can be substituted for the dyadic chaining, to prove in a unified setting several classical results. Among them are Stechkin's theorem, Gál--Koksma theorems and quantitative Borel--Cantelli lemmas. We give simpler proofs and improve some of these results. Two classes of examples are given: firstly stationary Gaussian sequences with applications to upper and lower classes and the law of the iterated logarithm for subsequences, and secondly in Diophantine approximation relatively to Gál and Schmidt's theorems.     

EXISTENCE OF PERIODIC SOLUTIONS OF A CLASS OF SECOND-ORDER NON-AUTONOMOUS SYSTEMS

In this paper, we are concerned with the existence of periodic solutions of second-order non-autonomous systems. By applying the Schauder''s fixed point theorem and Miranda''s theorem, a new existence result of periodic solutions is established.     

Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs

For a given graph F we consider the family of (finite) graphs G with the Ramsey property for F, that is the set of such graphs G with the property that every two‐coloring of the edges of G yields a monochromatic copy of F. For F being a triangle Friedgut, Rödl, Ruciński, and Tetali (2004) established the sharp threshold for the Ramsey property in random graphs. We present a simpler proof of this result which extends to a more general class of graphs F including all cycles. The proof is based on Friedgut's criteria (1999) for sharp thresholds and on the recently developed container method for independent sets in hypergraphs by Saxton and Thomason and by Balogh, Morris and Samotij. The proof builds on some recent work of Friedgut et al. who established a similar result for van der Waerden's theorem.     

Sharp Dirac's theorem for DP‐critical graphs

Correspondence coloring, or DP‐coloring, is a generalization of list coloring introduced recently by Dvořák and Postle [11]. In this article, we establish a version of Dirac's theorem on the minimum number of edges in critical graphs [9] in the framework of DP‐colorings. A corollary of our main result answers a question posed by Kostochka and Stiebitz [15] on classifying list‐critical graphs that satisfy Dirac's bound with equality.     

Edge list multicoloring trees: An extension of Hall's theorem

We prove a necessary and sufficient condition for the existence of edge list multicoloring of trees. The result extends the Halmos–Vaughan generalization of Hall's theorem on the existence of distinct representatives of sets. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 246–255, 2003     

An alternative proof of Pellet’s theorem for matrix polynomials

We propose an alternative proof of Pellet’s theorem for matrix polynomials that, unlike existing proofs, does not rely on Rouché’s theorem. A similar proof is provided for the generalization to matrix polynomials of a result by Cauchy that can be considered as a limit case of Pellet’s theorem.     

A Generalization of a Theorem of Birch

We generalize a theorem of Birch on solving systems of homogeneous equations of odd degree to the case of solving systems of homogeneous equations of degree not divisible by a fixed integer s ≥ 2. Birch's theorem is the case s = 2. In addition, we give a new exposition of the proof of Brauer's theorem on solving systems of homogeneous equations.     

The classical version of Stokes' theorem revisited

Using only fairly simple and elementary considerations–essentially from first year undergraduate mathematics–we show how the classical Stokes' theorem for any given surface and vector field in ?³ follows from an application of Gauss' divergence theorem to a suitable modification of the vector field in a tubular shell around the given surface. The two stated classical theorems are (like the fundamental theorem of calculus) nothing but shadows of the general version of Stokes' theorem for differential forms on manifolds. However, the main point in the present article is first, that this latter fact usually does not get within reach for students in first year calculus courses and second, that calculus textbooks in general only just hint at the correspondence alluded to above. Our proof that Stokes' theorem follows from Gauss' divergence theorem goes via a well-known and often used exercise, which simply relates the concepts of divergence and curl on the local differential level. The rest of this article uses only integration in 1, 2 and 3 variables together with a ‘fattening’ technique for surfaces and the inverse function theorem.     

Lucas' theorem and numerical range

The Lucas' theorem is generalized to the numerical ranges of some 3?×?3 companion matrices. We determine monic polynomials of degree 3 which assert the generalization. Examples are provided to show the generalization is restricted which gives a negative answer to the question raised by Zemanek [J. Zemanek, The derivative and linear algebra, Kolo Mlodych Matematykow, Ogolnopolskie Warsztaty, dla Mlodych Matematykow, Krakow, 2003, pp. 207–212.].     

Vectorial Ekeland's Variational Principle with a W-Distance and its Equivalent Theorems

By using the properties of w-distances and Gerstewitz's functions, we first give a vectorial Takahashi's nonconvex minimization theorem with a w-distance. From this, we deduce a general vectorial Ekeland's variational principle, where the objective function is from a complete metric space into a pre-ordered topological vector space and the perturbation contains a w-distance and a non-decreasing function of the objective function value. From the general vectorial variational principle, we deduce a vectorial Caristi's fixed point theorem with a w-distance. Finally we show that the above three theorems are equivalent to each other. The related known results are generalized and improved. In particular, some conditions in the theorems of [Y. Araya, Ekeland's variational principle and its equivalent theorems in vector optimization, J. Math. Anal. Appl. 346(2008), 9–16[ are weakened or even completely relieved.     

The Additivity Theorem in K-Theory

We present a method for converting Theorem B style proofs in algebraic K-theory to Theorem A style proofs and apply it to the additivity theorem.