Isometric approximation

Suppose thatA ⊂R ⁿ is a bounded set of diameter 1 and that:f:A →l ₂ is a map satisfying the nearisometry condition |x−y|−ɛ≤|fx−fy|≤|x−y|+ɛ withɛ≤1. Then there is an isometryS:A →l ₂ such that |Sx−fx|≤c _n √ɛ for allx inA. IfA satisfies a thickness condition and iff:A →R ⁿ , then there is an isometryS:R ⁿ →R ⁿ with |Sx−fx|≤c _nɛ/q, whereq is a thickness parameter.     

On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M₁ and M₂ be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M₁ and M₂ intersect at most |M₁|+|M₂|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. Supported by PAPIIT(UNAM) of México, Proyecto IN110802 Supported by FAI-UASLP and by CONACYT of México, Proyecto 32168-E Supported by CONACYT of México, Proyecto 37540-A     

Lower bound on the profile of degree pairs in cross-intersecting set systems

We raise the following problem. For natural numbers m, n ≥ 2, determine pairs d′, d″ (both depending on m and n only) with the property that in every pair of set systems A, B with |A| ≤ m, |B| ≤ n, and A ∩ B ≠ 0 for all A ∈ A, B ∈ B, there exists an element contained in at least d′ |A| members of A and d″ |B| members of B. Generalizing a previous result of Kyureghyan, we prove that all the extremal pairs of (d′, d″) lie on or above the line (n − 1) x + (m − 1) y = 1. Constructions show that the pair (1 + ɛ / 2n − 2, 1 + ɛ / 2m − 2) is infeasible in general, for all m, n ≥ 2 and all ɛ > 0. Moreover, for m = 2, the pair (d′, d″) = (1 / n, 1 / 2) is feasible if and only if 2 ≤ n ≤ 4. The problem originates from Razborov and Vereshchagin’s work on decision tree complexity. Research supported in part by the Hungarian Research Fund under grant OTKA T-032969.     

Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs

The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 (2006)] have proved that Bn is edge-bipancyclic for n ≥ 5 and Bn-F is bipancyclic when n ≥ 4 and |F | ≤ n-3. In this paper, we improve this result by showing that for any edge set F of Bn with |F | ≤ n-3, every edge of Bn F lies on a cycle of every even length from 6 to n! for n ≥ 5 and every edge of Bn F lies on a cycle of every even length from 8 to n! for n = 4.     

A characterization of the<Emphasis Type="Italic">MM</Emphasis>*-position of a convex body in terms of covariance matrices

We characterize the position of a convex bodyK such that it minimizesM(TK)M*(TK) (theMM*-position) in terms of properties of the measures ‖ · ‖ _K d σ(·) and ‖ · ‖ _K °d σ(·), answering a question posed by A. Giannopoulos and V. Milman. The techniques used allow us to study other extremal problems in the context of dual Brunn-Minkowski theory. Partially supported by MCYT Grant (Spain) BFM2001-1793 and FEDER funds from UE. Partially supported by MCYT Grant (Spain) BFM2001-1793 and FEDER funds from UE.     

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.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

A Hyperplane Inequality for Measures of Convex Bodies in ? n , n≤4

Let 2≤n≤4. We show that for an arbitrary measure μ with even continuous density in ℝ ⁿ and any origin-symmetric convex body K in ℝ ⁿ ,

Elliptic equation with singular potential

We consider the following problem of finding a nonnegative function u(x) in a ball B = B(O, R) ⊂ R ⁿ , n ≥ 3:

Hyperplane projections of the unit ball of ℓ p n

Let B _p ⁿ ={x∈\R ⁿ ;\; \sum _i=1 ⁿ |x _i | ^p ≤ 1} , 1≤ p\le+∈fty . We study the extreme values of the volume of the orthogonal projection of B _p ⁿ onto hyperplanes H\subset \R ⁿ . For a fixed H , we prove that the ratio vol(P _H B _p ⁿ )/ vol(B _p ^n-1 ) is non-decreasing in p∈[1,+∈fty] . Received May 21, 2001, and in revised form September 2, 2001. Online publication December 17, 2001.     

The Besov and Triebel-Lizorkin spaces with high order on the Lipschitz curves

The Besov spacesB _p ^α,μ (Γ) and Triebel-Lizorkin spacesF _p ^α,μ (Γ) with high order α∈R on a Lipschitz curve Γ are defined. when 1≤p≤∞, 1≤q≤∞. To compare to the classical case a difference characterization of such spaces in the case |α|<1 is given also. The author is supported in part by the Foundation of Zhongshan University Advanced Research Centre and NSF of China.     

Strikte Konvexität für Variationsprobleme auf demn-dimensionalen Torus

We consider a variational problem with an integrandF:R ⁿ ×R×R ⁿ →R that isZ-periodic in the firstn+1 variables and satisfies certain growth-conditions. By a recent result of Moser, there exist for every α∈R ⁿ minimal solutionsu:R ⁿ →R minimising ƒF(x, u(x), u _x (x)) dx with respect to compactly supported variations ofu and such that sup |u(x)-αx|<∞. Given such a minimal solutionu we define the average action (whereB _r is ther-ball around 0∈R ⁿ ) and show thatM(α) is indeed independent of the minimal solutionu satisfying sup |u(x)-αx|<∞. We prove that this average actionM(α) is strictly convex in α.      

Table algebras with multiple P-polynomial structures

Using covering numbers we prove that a standard real integral table algebra (A, B) with |B| ≥ 6 has a P-polynomial structure with respect to every b ≠ 1 in B if and only if 2|B|-1 is prime and (A, B) is exactly isomorphic to the Bose-Mesner algebra of the association scheme of the ordinary (2|B|-1)-gon. Then we present an example showing that this result is not true if |B| ≤ 5.     

On completely reducible solvable subgroups of GL(n, Δ)

Let Δ be a finite field and denote by GL(n, Δ) the group ofn×n nonsingular matrices defined over Δ. LetR⊆GL(n, Δ) be a solvable, completely reducible subgroup of maximal order. For |Δ|≧2, |Δ|≠3 we give bounds for |R| which improve previous ones. Moreover for |Δ|=3 or |Δ|>13 we determine the structure ofR, in particular we show thatR is unique, up to conjugacy. This work is part of a Ph.D. thesis done at the Hebrew University under the supervision of Professor A. Mann.     

Algebras whose equivalence relations are congruences

It is proved that all the equivalence relations of a universal algebra A are its congruences if and only if either |A| ≤ 2 or every operation f of the signature is a constant (i.e., f(a ₁ , . . . , a _n ) = c for some c ∈ A and all the a ₁ , . . . , a _n ∈ A) or a projection (i.e., f(a ₁ , . . . , a _n ) = a _i for some i and all the a ₁ , . . . , a _n ∈ A). All the equivalence relations of a groupoid G are its right congruences if and only if either |G| ≤ 2 or every element a ∈ G is a right unit or a generalized right zero (i.e., x _a  = y _a for all x, y ∈ G). All the equivalence relations of a semigroup S are right congruences if and only if either |S| ≤ 2 or S can be represented as S = A∪B, where A is an inflation of a right zero semigroup, and B is the empty set or a left zero semigroup, and ab = a, ba = a ² for a ∈ A, b ∈ B. If G is a groupoid of 4 or more elements and all the equivalence relations of it are right or left congruences, then either all the equivalence relations of the groupoid G are left congruences, or all of them are right congruences. A similar assertion for semigroups is valid without the restriction on the number of elements.     

Generalized Ham-Sandwich Cuts

Bárány, Hubard, and Jerónimo recently showed that for given well-separated convex bodies S ₁,…,S _d in R ^d and constants β _i ∈[0,1], there exists a unique hyperplane h with the property that Vol (h ⁺∩S _i )=β _i ⋅Vol (S _i ); h ⁺ is the closed positive transversal halfspace of h, and h is a “generalized ham-sandwich cut.” We give a discrete analogue for a set S of n points in R ^d which are partitioned into a family S=P ₁∪⋅⋅⋅∪P _d of well-separated sets and are in weak general position. The combinatorial proof inspires an O(n(log n) ^d−3) algorithm which, given positive integers a _i ≤|P _i |, finds the unique hyperplane h incident with a point in each P _i and having |h ⁺∩P _i |=a _i . Finally we show two other consequences of the direct combinatorial proof: the first is a stronger result, namely that in the discrete case, the conditions assuring existence and uniqueness of generalized cuts are also necessary; the second is an alternative and simpler proof of the theorem in Bárány et al., and in addition, we strengthen the result via a partial converse.     

Optimizing Area and Perimeter of Convex Sets for Fixed Circumradius and Inradius

 In this paper two problems posed by Santaló are solved: we determine the planar convex sets which have maximum and minimum area or perimeter when the circumradius and the inradius are given, obtaining complete systems of inequalities for the cases (A, R, r) and (p, R, r). This work is supported in part by Dirección General de Investigación (MCYT) BFM2001-2871, and by OTKA grants No 31984 and 30012 Received October 15, 2001; revised January 29, 2002     

A Neighborhood Condition for Graphs to Have [a, b]-Factors II

 Let a, b, m, and t be integers such that 1≤a<b and 1≤t≤⌉(b−m+1)/a⌉. Suppose that G is a graph of order |G| and H is any subgraph of G with the size |E(H)|=m. Then we prove that G has an [a,b]-factor containing all the edges of H if the minimum degree is at least a, |G|>((a+b)(t(a+b−1)−1)+2m)/b, and |N _G (x ₁)∪⋯ ∪N _G (x _t )|≥(a|G|+2m)/(a+b) for every independent set {x ₁,…,x _t }⊆V(G). This result is best possible in some sense and it is an extension of the result of H. Matsuda (A neighborhood condition for graphs to have [a,b]-factors, Discrete Mathematics 224 (2000) 289–292). Received: October, 2001 Final version received: September 17, 2002 RID="*" ID="*" This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Encouragement of Young Scientists, 13740084, 2001     

Lower bounds at infinity of solutions of partial differential equations in the exterior of a proper cone

An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed convex proper cone inR ⁿ and −Γ′ be the antipodes of the dual cone of Γ. Let be a partial differential operator with constant coefficients inR ⁿ, whereQ(ζ)≠0 onR ⁿ−iΓ′ andP _i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R ⁿ−iΓ′;P _j(ζ)=0, gradP _j(ζ)≠0} contains some real point on which gradP _j≠0 and gradP _j∉Γ∪(−Γ). LetC be an open cone inR ⁿ−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in {ξ∈R ⁿ;P(ξ)=0}. Ifu∈ℒ′∩L _loc ² (R ⁿ−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition implies that the support ofu is contained in Γ.     

A uniqueness theorem and the myrberg phenomenon for a Zalcman domain

LetR=Δ₀\∪_nΔ_n be a Zalcman domain (or L-domain), where Δ₀ : 0<|z| <1, Δ_n : |z-c _n|≤r _n,c_n ↘0, Δ_n ⊂ Δ₀ and Δ_n ∩ Δ_m= φ(n≠m). 0217 0115 V 3 For an unlimited two-sheeted covering with the branch points {φ^-1(c _n)}, set . In the casec _n=2⁻ⁿ , it was proved that if a uniqueness theorem is valid forH ^∞ (R) atz=0, then the Myrberg phenomenon occurs. One might suspect that the converse also holds. In this paper, contrary to this intuition, we show that the converse of this previous result is not true. In addition, we generalize the previous result for more general sequences {c _n}. By this generalization we can even partly simplify the previous proof. To complete the present work the first and second (third, resp.) named authors were supported in part by Grant-in-Aid for Scientific Research, No. 10304010 (10640190, 11640187, resp.), Japanese Ministry of Education, Science and Culture.