Functional inequality characterizing nonnegative concave functions in (0, ∞) k

Summary In the present note we prove that every functionf: (0, ) [0, ) satisfying the inequalityaf(s) + bf(t) f(as + bt), s, t > 0, for somea andb such that 0 <a < 1 <a + b must be of the formf(t) = f(1)t, (t > 0). This improves our recent result in [2], where the inequality is assumed to hold for alls, t 0, and gives a positive answer to the question raised there.An analogue for functions of several real variables of the above result characterizes concave functions. Conjugate functions and some relations to Hölder's and Minkowski's inequalities are mentioned.     

Extending partial isomorphisms of graphs

Theorem Let X be a finite graph. Then there exists a finite graph Z containing X as an induced subgraphs, such that every isomorphism between induced subgraphs of X extends to an automorphism of Z.The graphZ may be required to be edge-transitive. The result implies that for anyn, there exists a notion of a genericn-tuple of automorphism of the Rado graphR (the random countable graph): for almost all automorphism ₁,..., _n and ₁ ofR (in the sense of Baire category), (R,₁,..., _n ), (R,₁,..., _n ). The problem arose in a recent paper of Hodges, Hodgkinson, Lascar and Shelah, where the theorem is used to prove the small index property forR.Work supported by a Sloan Fellowship and by NSF grant DMS-8903378.     

The number of edges of many faces in a line segment arrangement

We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m ^2/3 n ^2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is (m ^2/3 n ^2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m ^2/3 t ^1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m ^2/3 t ^1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences.     

Small transversals in hypergraphs

For each positive integerk, we consider the setA _k of all ordered pairs [a, b] such that in everyk-graph withn vertices andm edges some set of at mostam+bn vertices meets all the edges. We show that eachA _k withk2 has infinitely many extreme points and conjecture that, for every positive , it has only finitely many extreme points [a, b] witha. With the extreme points ordered by the first coordinate, we identify the last two extreme points of everyA _k , identify the last three extreme points ofA ₃, and describeA ₂ completely. A by-product of our arguments is a new algorithmic proof of Turán's theorem.     

On a problem of Erdős and Lovász: Random lines in a projective plane

Letn(k) be the least size of an intersecting family ofk-sets with cover numberk, and let _k denote any projective plane of orderk–1.Theorem There is a constant A such that ifH is a random set ofm Aklogk lines from _k then P_r(H<)0(k).Corollary If there exists a _k thenn(k)=O(klogk). These statements were conjectured by P. Erds and L. Lovász in 1973.Supported in part by NSF-DMS87-83558 and AFOSR grants 89-0066, 89-0512 and 90-0008     

Toeplitz and Hankel type operators on the upper half-plane

An orthogonal decomposition of admissible wavelets is constructed via the Laguerre polynomials, it turns to give a complete decomposition of the space of square integrable functions on the upper half-plane with the measurey dxdy. The first subspace is just the weighted Bergman (or Dzhrbashyan) space. Three types of Ha-plitz operators are defined, they are the generalization of classical Toeplitz, small and big Hankel operators respectively. Their boundedness, compactness and Schatten-von Neumann properties are studied.Research was supported by the National Natural Science Foundation of China.     

Designs as maximum codes in polynomial metric spaces

Finite and infinite metric spaces % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] that are polynomial with respect to a monotone substitution of variable t(d) are considered. A finite subset (code) W % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!36D8!\[ \subseteq \] % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] is characterized by the minimal distance d(W) between its distinct elements, by the number l(W) of distances between its distinct elements and by the maximal strength (W) of the design generated by the code W. A code W % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!36D8!\[ \subseteq \] % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] is called a maximum one if it has the greatest cardinality among subsets of % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] with minimal distance at least d(W), and diametrical if the diameter of W is equal to the diameter of the whole space % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\]. Delsarte codes are codes W % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!36D8!\[ \subseteq \] % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] with (W)2l(W)–1 or (W)=2l(W)–2>0 and W is a diametrical code. It is shown that all parameters of Delsarte codes W) % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!36D8!\[ \subseteq \] % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] are uniquely determined by their cardinality |W| or minimal distance d(W) and that the minimal polynomials of the Delsarte codes W % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!36D8!\[ \subseteq \] % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] are expansible with positive coefficients in an orthogonal system of polynomials {Q _i(t)} corresponding to % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\]. The main results of the present paper consist in a proof of maximality of all Delsarte codes provided that the system {Q _i)} satisfies some condition and of a new proof confirming in this case the validity of all the results on the upper bounds for the maximum cardinality of codes W % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOHI0maaa!36D8!\[ \subseteq \]% MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgzgj% xyRrxDYbqeguuDJXwAKbIrYf2A0vNCaGqbaiab-Xa8nbaa!427C!\[\mathfrak{M}\] with a given minimal distance, announced by the author in 1978. Moreover, it appeared that this condition is satisfied for all infinite polynomial metric spaces as well as for distance-regular graphs, decomposable in a sense defined below. It is also proved that with one exception all classical distance-regular graphs are decomposable. In addition for decomposable distance-regular graphs an improvement of the absolute Delsarte bound for diametrical codes is obtained. For the Hamming and Johnson spaces, Euclidean sphere, real and complex projective spaces, tables containing parameters of known Delsarte codes are presented. Moreover, for each of the above-mentioned infinite spaces infinite sequences (of maximum) Delsarte codes not belonging to tight designs are indicated.     

Some properties of the riesz charge associated with a δ-subharmonic function

The first property is a refinement of earlier results of Ch. de la Vallée Poussin, M. Brelot, and A. F. Grishin. Let w=u–v with u, v superharmonic on a suitable harmonic space (for example an open subset of R ⁿ ), and let [w]=[u]–[v] denote the associated Riesz charge. If w0, and if E denotes the set of those points of at which the lim inf of w in thefine topology is 0, then the restriction of [w] to E is 0. Another property states that, if e denotes a polar subset of such that the fine lim inf of |w| at each point of e is finite, then the restriction of [w] to e is 0.     

Dirichlet norms,capacities and generalized isoperimetric inequalities for Markov operators

We define the notion of p-capacity for a reversible Markov operator on a general measure space and prove that uniform estimates for the ratio of capacity and measure are equivalent to certain imbedding theorems for the Orlicz and Dirichlet norms. As a corollary we get results on connections between embedding theorems and isoperimetric properties for general Markov operators and, particularly, a generalization of the Kesten theorem on the spectral radius of random walks on amenable groups for the case of arbitrary graphs with non-finitely supported transition probabilities.     

On the topology of compact smooth three-dimensional Levi-flat hypersurfaces

We study topological conditions that must be satisfied by a compactC ^∞ Levi-flat hypersurface in a two-dimensional complex manifold, as well as related questions about the holonomy of Levi-flat hypersurfaces. As a consequence of our work, we show that no two-dimensional complex manifold admits a subdomain Ω with compact nonemptyC ^∞ boundary such that Ω ? ?².