Die gruppentheoretischen Zetafunktionen und der Satz von Hajós

Ohne Zusammenfassung     

Über eine Vermutung von G. Hajós

Ohne Zusammenfassung Vorgelegt von G. Hajós     

Komlós Theorem for Unbounded Random Sets

We present the Komlós theorem for multivalued functions whose values are closed (possibly unbounded) convex subsets of a separable Banach space. Komlós theorem can be seen as a generalization of the SLLN for it deals with a sequence of integrable multivalued functions that do not have to be identically distributed nor independent. The Artstein–Hart SLLN for random sets with values in Euclidean spaces is derived from the main result. Finally, since the main theorem concerns multifunctions whose values are allowed to be unbounded, we can restate it in terms of normal integrands (random lower semicontinuous functions).     

An Analogue of Hajós' Theorem for the Circular Chromatic Number (II)

This paper designs a set of graph operations, and proves that for 2k/d<3, starting from K_k/_d, by repeatedly applying these operations, one can construct all graphs G with _c(G)k/d. Together with the result proved in [20], where a set of graph operations were designed to construct graphs G with _c(G)k/d for k/d3, we have a complete analogue of Hajós' Theorem for the circular chromatic number. This research was partially supported by the National Science Council under grant NSC 89-2115-M-110-003     

Erds-Ko-Rado Theorem for Ladder Graphs

For a graph G and an integer r≥1,G is r-EKR if no intersecting family of independent r-sets of G is larger than the largest star(a family of independent r-sets containing some fixed vertex in G),and G is strictly r-EKR if every extremal intersecting family of independent r-sets is a star.Recently,Hurlbert and Kamat gave a preliminary result about EKR property of ladder graphs.They showed that a ladder graph with n rungs is 3-EKR for all n≥3.The present paper proves that this graph is r-EKR for all 1≤r≤n,and strictly r-EKR except for r=n-1.     

A Scoring Criterion For Learning Chain Graphs

A chain graph allows both directed and undirected edges, and contains the underlying mathematical properties of the two. An important method of learning graphical models is to use scoring criteria to measure how well the graph structures fit the data. In this paper, we present a scoring criterion for learning chain graphs based on the Kullback Leibler distance. It is score equivalent, that is, equivalent chain graphs obtain the same score, so it can be used to perform model selection and model averaging.     

Plans’ Periodicity Theorem for Jacobian of Circulant Graphs

Doklady Mathematics - Plans’ theorem states that, for odd n, the first homology group of the n-fold cyclic covering of the three-dimensional sphere branched over a knot is the direct product...     

A-Browder＇s Theorem and Generalized a-Weyl＇s Theorem

Two variants of the essential approximate point spectrum are discussed. We find for example that if one of them coincides with the left Drazin spectrum then the generalized a-Weyl＇s theorem holds, and conversely for a-isoloid operators. We also study the generalized a-Weyl＇s theorem for Class A operators.     

An Extension Of The Ruzsa-Szemerédi Theorem

  We let G ^(r)(n,m) denote the set of r-uniform hypergraphs with n vertices and m edges, and f ^(r)(n,p,s) is the smallest m such that every member of G ^(r)(n,m) contains amember of G ^(r)(p,s). In this paper we are interested in fixed values r,p and s for which f ^(r)(n,p,s) grows quadratically with n. A probabilistic construction of Brown, Erds and T. Sós ([2]) implies that f ^(r)(n,s(r-2)+2,s)=(n ²). In the other direction the most interesting question they could not settle was whether f ⁽³⁾(n,6, 3) = o(n ²). This was proved by Ruzsa and Szemerédi [11]. Then Erds, Frankl and Rödl [6] extended this result to any r: f ^(r)(n, 3(r-2)+3, 3)=o(n ²), and they conjectured ([4], [6]) that the Brown, Erds and T. Sós bound is best possible in the sense that f ^(r)(n,s(r-2)+3,s)=o(n ²).In this paper by giving an extension of the Erds, Frankl, Rödl Theorem (and thus the Ruzsa–Szemerédi Theorem) we show that indeed the Brown, Erds, T. Sós Theorem is not far from being best possible. Our main result is

Note On The Utility Of A Theorem Of Leindler–Meir–Totik

Our purpose is to generalize and to extend a theorem of S. Sharma and S. K. Varma [15] concerning the order of approximation by Abel means in the Lipschitz norm. The proof is basically based on a simple extension of a general theorem of L. Leindler, A. Meir and V. Totik [6] related to approximation by finite summability methods.     

On An Extremal Hypergraph Problem Of Brown, Erdős And Sós

Let f_r(n,v,e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi and of Erdős, Frankl and R?dl, we partially resolve a problem raised by Brown, Erdős and Sós in 1973, by showing that for any fixed 2≤k<r, we have

A Generalization Of Reifenberg’s Theorem In {\mathbb{R}}^3

In 1960 Reifenberg proved the topological disc property. He showed that a subset of which is well approximated by m-dimensional affine spaces at each point and at each (small) scale is locally a bi-H?lder image of the unit ball in . In this paper we prove that a subset of which is well approximated in the Hausdorff distance sense by one of the three standard area-minimizing cones at each point and at each (small) scale is locally a bi-H?lder deformation of a minimal cone. We also prove an analogous result for more general cones in . Received: July 2006, Revised: August 2007, Accepted: January 2008     

A 3-color Theorem on Plane Graphs without 5-circuits

In this paper, we prove that every plane graph without 5-circuits and without triangles of distance less than 3 is 3-colorable. This improves the main result of Borodin and Raspaud [Borodin, O. V., Raspaud, A.： A sufficient condition for planar graphs to be 3-colorable. Journal of Combinatorial Theory, Ser. B, 88, 17-27 （2003）], and provides a new upper bound to their conjecture.     

Nordhaus–Gaddum-Type Theorem for Rainbow Connection Number of Graphs

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc(G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus–Gaddum-type result for the rainbow connection number. We prove that if G and ${\overline{G}}$ are both connected, then ${4\leq rc(G)+rc(\overline{G})\leq n+2}$ . Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively.     

The Erdős–Pósa Property For Long Circuits

We show that, for every l, the family of circuits of length at least l satisfies the Erdős–Pósa property, with f(k)=13l(k−1)(k−2)+(2l+3)(k−1), thereby sharpening a result of C. Thomassen. We obtain as a corollary that graphs without k disjoint circuits of length l or more have tree-width O(lk²).     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

Ramanujan’s Master Theorem

S. Ramanujan introduced a technique, known as Ramanujan??s Master Theorem, which provides an explicit expression for the Mellin transform of a function in terms of the analytic continuation of its Taylor coefficients. The history and proof of this result are reviewed, and a variety of applications is presented. Finally, a multi-dimensional extension of Ramanujan??s Master Theorem is discussed.