On Lower Bounds for the Chromatic Number of Spheres

Mathematical Notes - Estimates of the chromatic numbers of spheres are studied. The optimality of the choice of the parameters of the linear-algebraic method used to obtain these estimates is...     

r-一致超图Ramsey函数的渐近下界(英文)

本文利用Lovasz局部引理的Spencer形式和对称形式给出r-一致超图Ramsey函数的渐近下界.证明了:对于任意取定的正整数f0,使得当n→∞时,有R~((r))(m~l,n~(k-l))≥(c-o(1))(n~(r-1)/logn)~■.特别地,R~((r))_k(n)≥(1-o(1))n/e k~■(n→∞).对于任意取定的正整数s≥r+1和常数δ>0,α≥0,如果F表示阶为s的r-一致超图,■表示阶为t的r-一致超图,且■的边数满足m(■)≥(δ-o(1))t~r/(logt)α(t→∞),则存在c=c(s,δ,α)>0,使得R~((r))(F,■)≥(c-o(1))(t~(r-1)/(logt)~l+(r-l)α)~(m(F)-l/s-r).     

Bounds on the Generalised Acyclic Chromatic Numbers of Bounded Degree Graphs

We give upper bounds for the generalised acyclic chromatic number and generalised acyclic edge chromatic number of graphs with maximum degree d, as a function of d. We also produce examples of graphs where these bounds are of the correct order. Part of this work supported by an Australian Research Council Postdoctoral Fellowship     

Upper Bounds for the Chromatic Numbers of Euclidean Spaces with Forbidden Ramsey Sets

Mathematical Notes - The chromatic number of a Euclidean space ? n with a forbidden finite set C of points is the least number of colors required to color the points of this space so that no...     

Ramsey数的几个新下界公式

本文通过构造循环图,得到并证明了公式:r(3,q)≥5(q-3)+2,r(3,q)≥7(q-5)+2,(q为奇数),又由所给引理:若r(l_1,k_1)>t_1,r(l_2,k_2)>t_2,则r(l_1-1·l_2-1+1,k_1-1·k_2-1+1)>t_1t_2,归纳出又一公式:r(3~n+1,3~n+1)≥17~n+1     

含双参数的Ramsey数新上、下界公式

本文得到了含双参数x,y的Ramsey数的新上、下界公式,且初步研究了它的应用,证明了R（K6-e,K6）≤116和R（K6-e,K7）≤202.     

Lower Bounds on the Transversal Numbers of d -Intervals

Let l ₁ ,l ₂ ,ldots,l _d be disjoint parallel lines in the plane. A d-interval is a subset of their union that intersects each l _i in a closed interval. Kaiser [4] showed that any system of d -intervals containing no subsystem of k+1 pairwise disjoint d -intervals can be pierced by at most (d ² -d)k points. We show that this bound is close to being optimal, by proving a lower bound of const(d ² /log ² d)k . The construction involves an extension of a construction due to Sgall [8] of certain systems of set pairs. Received April 4, 2000, and in revised form January 4, 2001. Online publication August 28, 2001.     

Lower Bounds for Shellsort

We show lower bounds on the worst-case complexity of Shellsort. In particular, we give a fairly simple proof of an Ω(n (lg² n)/(lg lg n)²) lower bound for the size of Shellsort sorting networks for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence.     

Refinement of Lower Bounds of the Chromatic Number of a Space with Forbidden One-Color Triangles

Mathematical Notes - The present paper deals with estimates of the chromatic number of a space with forbidden one-color triangles. New lower bounds for the quantity under study, which are sharper...     

Lower Bounds for Catalan's Equation

This paper begins with a short historical survey on Catalan's equation, namely x^p-y^q=1, where p andq are prime numbers and x, y are non-zero rational integers. It is conjectured that the only solution is the trivial solution 3²-2³=1. We prove that there is no non-trivial solution with p orq smaller than 30000. The tools to reach such a result are presented. A crucial role is played by a recent estimate of linear forms in two logarithms obtained by Laurent, Mignotte and Nestrenko. The criteria used are also quite recent. We give information on the enormous amount of computation needed for the verification.     

Lower Bounds for Covering Problems

In this paper we present an (nlogn) lower bound proof for several covering problems including the optimal line bipartition problem, min-max covering by two axis parallel rectangles, discrete and continuous two-center problems, two-line center problem, etc. Our proofs are based on using the rotational reduce technique and well-known lower bound for the maximal gap problem.     

Lower Bounds for Transversal Covers

A transversal cover is a set of gk points in k disjoint groups of size g and a collection of b transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. A central question is to determine, for given g, the minimum possible b for fixed k, or, alternatively, the maximum k for fixed b. The case g=2 was investigated and completely solved by Sperner sperner:28, Rényi renyi:71, Katona katona:73, and Kleitman and Spencer kleitman:73. For arbitrary g, asymptotic results are known but little is understood for small values of k. Constructions exist but these only produce upper bounds on b. The present article is concerned with lower bounds on b. We develop three general lower bounds on b for fixedg and k. The first one is proved using one of the principal constructions brett:97a, the second comes from the study of intersecting set-systems, and the third is shown by a set packing argument. In addition, we investigate upper bounds on k for small fixed b. This proves useful to reduce or eliminate the gap between lower and upper bounds on b for some transversal covers with small k.     

关于反平均数的2个上界

对于整数k,θ≥3,β≥1,称k个元素集合S为（k;β,θ）⁰自由集,如果S的最小元素为0且它没有互不相同的元素a_ij∈S(1≤j≤θ使得∑_j=1^θ-1a_ij=βa_iθ成立,S的最大元素记为max（S）.反平均数定义为λ（k;β,θ）=min{max（S）:S是（k;β,θ）⁰自由集}.给出反平均数λ（k;β,θ）的2个界.     

Lower Bounds for Cubical Pseudomanifolds

It is verified that the number of vertices in a d-dimensional cubical pseudomanifold is at least 2 ^d+1. Using Adin’s cubical h-vector, the generalized lower bound conjecture is established for all cubical 4-spheres, as well as for some special classes of cubical spheres in higher dimensions.     

伪Smarandache函数的上下界

对于正整数n,设Z(n)=min{m|m∈N,1/2m(m+1)≡0(modn)},称为n的伪Smarandache函数.设r是正整数.根据广义Ramanujan-Nagell方程的结果,运用初等数论方法证明了下列结果:i)1/2(-1+(8n+1)≤Z(n)≤2n-1.ii)当r≠1,2,3或5时,Z(2~r+1)≥1/2(-1+(2~(r+3)·5+41)).iii)当r≠1,2,3,4或12时,Z(2~r-1)≥1/2(-1+(2~(r+3)·3-23).     

乘积图的全色数

本文得到了有关乘积图的全色数的一些结果,并利用这些结果证明了Mesh图和Tours-图均满足全色数猜想．特别,几乎所有的Mesh-图都是第一类图．     

Chromatic Numbers of Some Distance Graphs

Mathematical Notes - For positive integers n > r > s, G(n, r, s) is the graph whose vertices are the r-element subsets of an n-element set, two subsets being adjacent if their...