Thed-step conjecture for polyhedra of dimensiond<6

Two functions Δ and Δ _b , of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ(d, n) is the maximum diameter of convex polyhedra of dimensiond withn faces of dimensiond−1; similarly, Δ _b (d,n) is the maximum diameter of bounded polyhedra of dimensiond withn faces of dimensiond−1. The diameter of a polyhedronP is the smallest integerl such that any two vertices ofP can be joined by a path ofl or fewer edges ofP. It is shown that the boundedd-step conjecture, i.e. Δ _b (d,2d)=d, is true ford≤5. It is also shown that the generald-step conjecture, i.e. Δ(d, 2d)≤d, of significance in linear programming, is false ford≥4. A number of other specific values and bounds for Δ and Δ _b are presented. This revised version was published online in November 2006 with corrections to the Cover Date.     

Computation of betti numbers of monomial ideals associated with stacked polytopes

LetP(v, d) be a stackedd-polytope withv vertices, δ(P(v, d)) the boundary complex ofP(v, d), andk[Δ(P(v, d))] =A/I _Δ(P(v,d)) the Stanley-Reisner ring of Δ(P(v,d)) over a fieldk. We compute the Betti numbers which appear in a minimal free resolution ofk[Δ(P(v,d))] overA, and show that every Betti number depends only onv andd and is independent of the base fieldk. We also show that the Betti number sequences above are unimodal.     

On second order degree of graphs

Given a vertex v of a graph G the second order degree of v denoted as d 2(v) is defined as the number of vertices at distance 2 from v.In this paper we address the following question:What are the sufficient conditions for a graph to have a vertex v such that d2(v) ≥ d(v),where d(v) denotes the degree of v? Among other results,every graph of minimum degree exactly 2,except four graphs,is shown to have a vertex of second order degree as large as its own degree.Moreover,every K-4-free graph or every maximal planar graph is shown to have a vertex v such that d2(v) ≥ d(v).Other sufficient conditions on graphs for guaranteeing this property are also proved.     

Some upper bounds for the diameters of convex polytopes

Δ(d, n) is defined to be the maximum diameter of ad-polytope withn-facets. The main results of the work are an evaluation of Δ(4, 10) and Δ(5, 11). Also, improved upper bounds are found for Δ(6, 13) and Δ(7,14).     

A sufficient degree condition for a graph to contain all trees of size <Emphasis Type="Italic">k</Emphasis>

The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d _G (x) + d _G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d _G (u) ≥ k.     

On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

An Ore-type analogue of the Sauer-Spencer Theorem

Two graphs G₁ and G₂ of order n pack if there exist injective mappings of their vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer proved that if Δ (G₁) Δ (G₂) < 0.5n, then G₁ and G₂ pack. In this note, we study an Ore-type analogue of the Sauer–Spencer Theorem. Let θ(G) = max{d(u) + d(v): uv∈E(G)}. We show that if θ(G₁)Δ(G₂) < n, then G₁ and G₂ pack. We also characterize the pairs (G₁,G₂) of n-vertex graphs satisfying θ(G₁)Δ(G₂) = n that do not pack. This work was supported in part by NSF grant DMS-0400498. The work of the first author was also partly supported by grant 05-01-00816 of the Russian Foundation for Basic Research.     

Upper and lower bounds of the valence-functional

For the non-negative integerg let (M, g) denote the closed orientable 2-dimensional manifold of genusg. K-realizationsP of (M, g) are geometric cell-complexes inP with convex facets such that set (P) is homeomorphic toM. ForK-realizationsP of (M, g) and verticesv ofP, val (v,P) denotes the number of edges ofP incident withv and the weighted vertex-number Σ(val(v, P)-3) taken over all vertices ofP is called valence-valuev (P) ofP. The valence-functionalV, which is important for the determination of all possiblef-vectors ofK-realisations of (M, g), in connection with Eberhard's problem etc., is defined byV(g):=min[v(P)|P is aK-realization of (M,g)]. The aim of the note is to prove the inequality 2g+1≦V(g)≦3g+3 for every positive integerg.     

Voronoi diagrams of random lines and flats

It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝ^d is Ξ(n ^d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝ^d     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

The linear arboricity of graphs

Alinear forest is a forest in which each connected component is a path. Thelinear arboricity la(G) of a graphG is the minimum number of linear forests whose union is the set of all edges ofG. Thelinear arboricity conjecture asserts that for every simple graphG with maximum degree Δ=Δ(G), . Although this conjecture received a considerable amount of attention, it has been proved only for Δ≦6, Δ=8 and Δ=10, and the best known general upper bound for la(G) is la(G)≦⌈3Δ/5⌉ for even Δ and la(G)≦⌈(3Δ+2)/5⌉ for odd Δ. Here we prove that for everyɛ>0 there is a Δ₀=Δ₀(ɛ) so that la(G)≦(1/2+ɛ)Δ for everyG with maximum degree Δ≧Δ₀. To do this, we first prove the conjecture for everyG with an even maximum degree Δ and withgirth g≧50Δ. Research supported in part by Allon Fellowship, by a Bat Sheva de Rothschild grant, by the Fund for Basic Research administered by the Israel Academy of Sciences and by a B.S.F. Bergmann Memorial grant.     

Trace formulas for a class of Toeplitz-like operators

LetP _T denote projection onto the space of entire functions of exponential type ≦T which are square summable on the line relative to a measuredΔ and letG denote multiplication by a suitably restricted complex valued function,g. For a reasonably large class of measuresdΔ, which includes Lebesgue measuredγ, it is shown that trace {(P _TGP_T)ⁿ−P_TGⁿP_T} tends boundedly to a limit asT↑∞ and that the limit isindependent of the choice ofdΔ within the permitted class. This extends the range of validity of a formula due to Mark Kac who evaluated this limit in the special casedΔ=dγ using a different formalism.     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

The distance between certainn-dimensional Banach spaces

IfE andF aren-dimensional Banach spaces, ifE has cotype 2, and if the ball ofF* has a small number of extreme points, then the Banach-Mazur distanced(E, F)≦C √nlogn. The techniques lead to the formally stronger result: IfE andF* have type 2 constantsa andb, respectively, thend(E, F)≦√n(a+b). IfE isn-dimensional, the identity map onE, when restricted to a large subspace ofE, factors through with normC √n. The authors’ work was supported in part, respectively, by NSF grant numbers MCS 78-02194, MCS 79-02489, and MCS 77-04174.     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d _G (u) + d _G (v) ⩾ n − 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d _G (u) + d _G (v) ⩾ n − 2g + 3 (resp. d _G (u) + d _G (v) ⩾ n − 2g −5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight. This work was supported by National Natural Science Foundation of China (Grant No. 10571013)     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

Sulla funzione di Hilbert di un sottoschema zero-dimensionale diP 3

Riassunto In questo lavoro diamo una caratterizzazione aritmetica della differenza prima ΔH(X,−) della funzione di Hilbert di un sottoschema chiuso 0-dimensionaleX diP ³. Il risultato principale viene applicato per dimostrare che seX è contenuto in una completa intersezione di tipo(a, b, c), a≦b≦c allora ΔH(X, n) è decrescente pern≧a+c−2.

---

Summary In this paper we give an aritmetical characterization of the first difference ΔH(X,−) of the Hilbert function of a closed 0-dimensional subschemeX ofP ³. The main result is then applied to prove that ifX is contained in a complete intersection of type(a, b, c), a≦b≦c then ΔH(X, n) is decreasing forn≧a+c−2.

---

---

Lavoro svolto con finanziamento MPI.     

Reduced bodies in normed planes

We say that a convex body R of a d-dimensional real normed linear space M ^d is reduced, if Δ(P) < Δ(R) for every convex body P ⊂ R different from R. The symbol Δ(C) stands here for the thickness (in the sense of the norm) of a convex body C ⊂ M ^d . We establish a number of properties of reduced bodies in M ². They are consequences of our basic Theorem which describes the situation when the width (in the sense of the norm) of a reduced body R ⊂ M ² is larger than Δ(R) for all directions strictly between two fixed directions and equals Δ(R) for these two directions.     

<Emphasis Type="Italic">f</Emphasis>-Colorings of some graphs of <Emphasis Type="Italic">f</Emphasis>-class 1

An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.