Bichromatic and Equichromatic Lines in ℂ2 and ℝ2

Let G and R each be a finite set of green and red points, respectively, such that |G|=n, |R|=n−k, G∩R=∅, and the points of G∪R are not all collinear. Let t be the total number of lines determined by G∪R. The number of equichromatic lines (a subset of bichromatic) is at least (t+2n+3−k(k+1))/4. A slightly weaker lower bound exists for bichromatic lines determined by points in ℂ². For sufficiently large point sets, a proof of a conjecture by Kleitman and Pinchasi is provided. A lower bound of (2t+14n−k(3k+7))/14 is demonstrated for bichromatic lines passing through at most six points. Lower bounds are also established for equichromatic lines passing through at most four, five, or six points.     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

The riesz turndown collar theorem giving an asymptotic estimate of the powers of an operator under the ritt condition

For Banach space operatorsT satisfying the Tadmor-Ritt condition ‖(zI−T)⁻¹‖≤C|z−1|⁻¹, |z|>1, we show how to use the Riesz turndown collar theorem to estimate sup _n≥0‖T ⁿ‖. A similar estimate is shown for lim sup _n ‖T ⁿ‖ in terms of the Ritt constantM=lim sup _z→1‖(1−z)(zI−T)⁻¹‖. We also obtain an estimate of the functional calculus for these operators proving, in particular, that ‖f(T)‖≤C _q‖f‖ _Mult , where ‖·‖ _Mult stands for the multiplier norm of the Cauchy-Stieltjes integrals over a Lusin type cone domain depending onC and a parameterq, 0<q<1. Notation.D denotes the open unit disc of the complex plane,D={z∈ℂ:|z|<1}, andT={z∈ℂ:|z|=1} is the unit circle.H ^∞ is the Banach algebra of bounded analytic functions onD equipped with the supremum norm ‖.‖_∞.     

Bounds on the Total Restrained Domination Number of a Graph

Let G = (V, E) be a graph. A set S í V{S \subseteq V} is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the smallest cardinality of a total restrained dominating set of G. We show that if δ ≥ 3, then γ _tr (G) ≤ n − δ − 2 provided G is not one of several forbidden graphs. Furthermore, we show that if G is r − regular, where 4 ≤ r ≤ n − 3, then γ _tr (G) ≤ n − diam(G) − r + 1.     

On the Minimum Length of some Linear Codes of Dimension 5

In this paper, we shall prove that the minimum length n_q(5,d) is equal to g_q(5,d) +1 for q⁴−2q²−2q+1≤ d≤ q⁴ − 2q² − q and 2q⁴ − 2q³ − q² − 2q+1 ≤ d ≤ 2q⁴−2q³−q²−q, where g_q(5,d) means the Griesmer bound . Communicated by: J.D. Key     

A class of optimal linear codes of length one above the Griesmer bound

In this paper, we determine the smallest lengths of linear codes with some minimum distances. We construct a [g _q (k, d) + 1, k, d] _q code for sq ^k-1 − sq ^k-2 − q ^s  − q ² + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s with 3 ≤ s ≤ k − 2 and q ≥ s + 1. Then we get n _q (k, d) = g _q (k, d) + 1 for (k − 2)q ^k-1 − (k − 1)q ^k-2 − q ² + 1 ≤ d ≤ (k − 2)q ^k-1 − (k − 1)q ^k-2, k ≥ 6, q ≥ 2k − 3; and sq ^k-1 − sq ^k-2 − q ^s  − q + 1 ≤ d ≤ sq ^k-1 − sq ^k-2 − q ^s , s ≥ 2, k ≥ 2s + 1 and q ≥ 2s − 1. This work was partially supported by the Com²MaC-SRC/ERC program of MOST/KOSEF (grant ^# R11-1999-054) and was partially supported by the Korea Research Foundation Grant funded by the Korean Government(MOEHRD)(KRF-2005-214-C00175).     

On Intersection Problem for Perfect Binary Codes

The main result is that to any even integer q in the interval 0 ≤ q ≤ 2^{n+1-2log(n+1)}, there are two perfect codes C₁ and C₂ of length n = 2^m − 1, m ≥ 4, such that |C₁ ∩ C₂| = q.     

The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.     

Minimal full polarized embeddings of dual polar spaces

Let Δ be a thick dual polar space of rank n ≥ 2 admitting a full polarized embedding e in a finite-dimensional projective space Σ, i.e., for every point x of Δ, e maps the set of points of Δ at non-maximal distance from x into a hyperplane e∗(x) of Σ. Using a result of Kasikova and Shult [11], we are able the show that there exists up to isomorphisms a unique full polarized embedding of Δ of minimal dimension. We also show that e∗ realizes a full polarized embedding of Δ into a subspace of the dual of Σ, and that e∗ is isomorphic to the minimal full polarized embedding of Δ. In the final section, we will determine the minimal full polarized embeddings of the finite dual polar spaces DQ(2n,q), DQ ⁻(2n+1,q), DH(2n−1,q ²) and DW(2n−1,q) (q odd), but the latter only for n≤ 5. We shall prove that the minimal full polarized embeddings of DQ(2n,q), DQ ⁻(2n+1,q) and DH(2n−1,q ²) are the `natural' ones, whereas this is not always the case for DW(2n−1, q).B. De Bruyn: Postdoctoral Fellow of the Research Foundation - Flanders.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Kernels of Toeplitz operators,smooth functions,and Bernstein type inequalities

Let ϕ be a unimodular function on the unit circle and let K_p(ϕ) denote the kernel of the Toeplitz operator T_ϕ in the Hardy space H^p, p≥1; . Suppose K_p(ϕ)≠{0}. The problem is to find out how the smoothness of the symbol ϕ influences the boundary smoothness of functions in K_p(ϕ). One of the main results is as follows. Theorem 1 Let 1<p, q<+∞, 1<r≤+∞, q⁻¹=p⁻¹+r⁻¹. Suppose |ϕ|≡1 on and ϕ∈W _r ¹ (i.e., ). Then K_p(ϕ)⊂W _q ¹ . Moreover, for any f∈K_p(ϕ) we have ‖f′‖_q≤c(p, r)‖ϕ′‖_r ‖f‖. Bibliography: 19 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 201, 1992, pp. 5–21. Translated by K. M. D'yakonov.     

An elementary approach to gap theorems

Using elementary comparison geometry, we prove: Let (M, g) be a simply-connected complete Riemannian manifold of dimension ≥ 3. Suppose that the sectional curvature K satisfies −1 − s(r) ≤ K ≤ −1, where r denotes distance to a fixed point in M. If lim _{r → ∞} e^2r s(r) = 0, then (M, g) has to be isometric to ℍ ⁿ . The same proof also yields that if K satisfies −s(r) ≤ K ≤ 0 where lim _{r → ∞} r ² s(r) = 0, then (M, g) is isometric to ℝ ⁿ , a result due to Greene and Wu. Our second result is a local one: Let (M, g) be any Riemannian manifold. For a ∈ ℝ, if K ≤ a on a geodesic ball B _p (R) in M and K = a on ∂B _p (R), then K = a on B _p (R).     

On Some Three-Color Ramsey Numbers

 In this paper we study three-color Ramsey numbers. Let K _i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G ₁, G ₂ and G ₃, if r(G ₁, G ₂)≥s(G ₃), then r(G ₁, G ₂, G ₃)≥(r(G ₁, G ₂)−1)(χ(G ₃)−1)+s(G ₃), where s(G ₃) is the chromatic surplus of G ₃; (ii) (k+m−2)(n−1)+1≤r(K _1,k , K _1,m , K _n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m≥k≥2, there is a constant c such that r(K _k,m , K _k,m , K _n )≤c(n/logn), and r(C _2m , C _2m , K _n )≤c(n/logn) ^m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55     

Compositions of isometric immersions¶in higher codimension

Given a submanifold M ⁿ of Euclidean space ℝ ^{n + p} with codimension p≤6, under generic conditions on its second fundamental form, we show that any other isometric immersion of M ⁿ into ℝ ^{n + p + q} , 0≤q≤n− 2p−1 and 2q≤n+ 1 if q≥ 5, must be locally a composition of isometric immersions. This generalizes several previous results on rigidity and compositions of submanifolds. We also provide conditions under which our result is global. 14 March 2001     

How many s-subspaces must miss a point set in PG(d, q)

The following result is well-known for finite projective spaces. The smallest cardinality of a set of points of PG(n, q) with the property that every s-subspace has a point in the set is (q ^n+1-s - 1)/(q - 1). We solve in finite projective spaces PG(n, q) the following problem. Given integers s and b with 0 ≤ s ≤ n - 1 and 1 ≤ b ≤ (q ^n+1-s - 1)/(q - 1), what is the smallest number of s-subspaces that must miss a set of b points. If d is the smallest integer such that b ≤ (q ^d+1 - 1)/(q - 1), then we shall see that the smallest number is obtained only when the b points generate a subspace of dimension d. We then also determine the smallest number of s-subspaces that must miss a set of b points of PG(n, q) which do not lie together in a subspace of dimension d. The results are obtained by geometrical and combinatorial arguments that rely on a strong algebraic result for projective planes by T. Szőnyi and Z. Weiner.     

A Higman inequality for regular near polygons

The inequality of Higman for generalized quadrangles of order (s,t) with s>1 states that t≤s ². We generalize this by proving that the intersection number c _i of a regular near 2d-gon of order (s,t) with s>1 satisfies the tight bound c _i ≤(s ²ⁱ −1)/(s ²−1), and we give properties in case of equality. It is known that hemisystems in generalized quadrangles meeting the Higman bound induce strongly regular subgraphs. We also generalize this by proving that a similar subset in regular near 2d-gons meeting the bounds would induce a distance-regular graph with classical parameters (d,b,α,β)=(d,−q,−(q+1)/2,−((−q) ^d +1)/2) with q an odd prime power.     

Counting the number of twin Niven numbers

Given an integer q≥2, we say that a positive integer is a q-Niven number if it is divisible by the sum of its digits in base q. Given an arbitrary integer r∈[2,2q], we say that (n,n+1,…,n+r−1) is a q-Niven r -tuple if each number n+i, for i=0,1,…,r−1, is a q-Niven number. We show that there exists a positive constant c=c(q,r) such that the number of q-Niven r-tuples whose leading component is <x is asymptotic to cx/(log x) ^r as x→∞. Research of J.M. De Koninck supported in part by a grant from NSERC. Research of I. Kátai supported by the Applied Number Theory Research Group of the Hungarian Academy of Science and by a grant from OTKA.     

BOUNDEDNESS OF VECTOR-VALUED CALDERON-ZYGMUND OPERATORS ON HERZ SPACES WITH NON-DOUBLING MEASURES

In the paper we obtain vector-valued inequalities for Calderon-Zygmund operator,simply CZO On Herz space and weak Herz space.In particular,we obtain vector-valued inequalities for CZO on Lq(Rd,│x│αdμ)space,with 1＜q＜∞,-n＜α＜n(q-1),and on L1,∞(Rd,│x│αdμ)space,with -n＜α＜0.     

Gaussian partitions

Let V=V(n,q) denote the finite vector space of dimension n over the finite field with q elements. A subspace partition of V is a collection Π of subspaces of V such that each 1-dimensional subspace of V is in exactly one subspace of Π. In a recent paper, we proved some strong connections between the lattice of the subspace partitions of V and the lattice of the set partitions of n={1,…,n}. We now define a Gaussian partition of [n] _q =(q ⁿ −1)/(q−1) to be a nonincreasing sequence of positive integers formed by ordering all elements of some multiset {dim(W):W∈Π}, where Π is a subspace partition of V. The Gaussian partition function gp(n,q) is then the number of all Gaussian partitions of [n] _q , and is naturally analogous to the classical partition function p(n). In this paper, we initiate the study of gp(n,q) by exhibiting all Gaussian partitions for small n. In particular, we determine gp(n,q) as a polynomial in q for n≤5, and find a lower bound for gp(6,q).     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.