Structure and stability of triangle-free set systems

We define the notion of stability for a monotone property of set systems. This phenomenon encompasses some classical results in combinatorics, foremost among them the Erdos-Simonovits stability theorem. A triangle is a family of three sets such that , , are each nonempty, and . We prove the following new theorem about the stability of triangle-free set systems.

Fix . For every , there exist and such that the following holds for all : if and is a triangle-free family of -sets of containing at least members, then there exists an -set which contains fewer than members of .

This is one of the first stability theorems for a nontrivial problem in extremal set theory. Indeed, the corresponding extremal result, that for every triangle-free family of -sets of has size at most , was a longstanding conjecture of Erdos (open since 1971) that was only recently settled by Mubayi and Verstraëte (2005) for all .

     

A polynomial space proof of the Graham-Pollak theorem

This note describes a polynomial space proof of the Graham-Pollak theorem.     

A short proof of a theorem of Birkhoff

This paper gives a new proof of a theorem of G. Birkhoff: Every group can be represented as the automorphism group of a distributive lattice D; if is finite, D can be chosen to be finite. The new proof is short, and it is easily visualized. Received November 3, 1995; accepted in final form October 3, 1996.     

A short proof of a theorem of Ruelle

Using the existence of conformal measures in the sense ofSullivan [4] andDenker, Urbaski [2] we give a simple proof of Ruelle's Theorem, that the Hausdorff dimension of a hyperbolic Julia set is the solution of the equationP(R,–tlog|R|)=0.     

A short proof of Fan's theorem

In this note, we give a new short proof of the following theorem: Let G be a 2-connected graph of order n. If for any two vertices u and v with d(u,v)=2,max{d(u),d(v)}?c/2, then the circumference of G is at least c, where 3?c?n and d(u,v) is the distance between u and v in G.     

A short proof of a cross-intersection theorem of Hilton

Families A₁,…,A_k of sets are said to be cross-intersecting if for any A_i∈A_i and A_j∈A_j, i≠j. A nice result of Hilton that generalises the Erd?s-Ko-Rado (EKR) Theorem says that if r≤n/2 and A₁,…,A_k are cross-intersecting sub-families of , then

     

A short proof of a theorem on Hamiltonian graphs

In this note, we give a short proof of a stronger version of the following theorem: Let G be a 2-connected graph of order n such that $ d(u)+d(v)+d(w) \geq n + \mid N(u) \cap N(v) \cap N(w) \mid $ for any independent set {u, v, w}, then G is hamiltonian. © 1996 John Wiley & Sons Inc.     

A short proof for a generalization of Vizing's theorem

For a simple graph of maximum degree Δ, it is always possible to color the edges with Δ + 1 colors (Vizing); furthermore, if the set of vertices of maximum degree is independent, Δ colors suffice (Fournier). In this article, we give a short constructive proof of an extension of these results to multigraphs. Instead of considering several color interchanges along alternating chains (Vizing, Gupta), using counting arguments (Ehrenfeucht, Faber, Kierstead), or improving nonvalid colorings with Fournier's Lemma, the method of proof consists of using one single easy transformation, called “sequential recoloring”, to augment a partial k-coloring of the edges.     

A short proof of the twelve-point theorem

We present a short elementary proof of the following twelve-point theorem. Let M be a convex polygon with vertices at lattice points, containing a single lattice point in its interior. Denote by m (respectively, m*) the number of lattice points in the boundary of M (respectively, in the boundary of the dual polygon). Then m + m* = 12.Translated from Matematicheskie Zametki, vol. 77, no. 1, 2005, pp. 117–120.Original Russian Text Copyright © 2005 by D. Repov, M. Skopenkov, M. Cencelj.This revised version was published online in April 2005 with a corrected issue number.     

A short proof of the Wedderburn-Artin theorem

We give a short proof of the Wedderburn–Artin theorem from the viewpoint of completely reducible modules.     

A short proof of Hara and Nakai's theorem

We give a short proof of the following theorem of Hara and Nakai: for a finitely bordered Riemann surface , one can find an upper bound of the corona constant of that depends only on the genus and the number of boundary components of .

     

A short proof of the twelve-point theorem

We present a short elementary proof of the following twelve-point theorem. Let M be a convex polygon with vertices at lattice points, containing a single lattice point in its interior. Denote by m (respectively, m*) the number of lattice points in the boundary of M (respectively, in the boundary of the dual polygon). Then m + m* = 12.     

A short proof of an index theorem

We give a -theoretical proof of an index theorem for Dirac-Schrödinger operators on a noncompact manifold.

     

A short proof of the Arendt-Chernoff-Kato theorem

We give a short new proof of the Arendt-Chernoff-Kato theorem, which characterizes generators of positive C ₀ semigroups in order unit spaces. The proof avoids half-norms and subdifferentials and is based on a sufficient condition for an operator to have positive inverse, which is new even for matrices.