On the functional equationS(m,n)F[n/(m,n)] =F(n)h[n/(m,n)]

In this paper, we discuss the pairs (f, h) of arithmetical functions satisfying the functional equation in the title, whereF is the product off andh under the Dirichlet convolution; that is,F(n) = Σ _d|n ?(d)h(n/d) andS(m n) = Σd|(m, n) ?(d)h(n/d). The well-known Hölder's identity is a special case of this functional equation (?(n) =n, h(n) = μ(n)). We also generalize the functional equation in the title to any arbitrary regular arithmetical convolution and discuss the pairs of solutions (f, h) of the generalized functional equation and pose some problems relating to the characterization of all pairs of solutions.     

General decomposition theorems form-convex sets in the plane

A setS inR ^dis said to bem-convex,m≧2, if and only if for everym distinct points inS, at least one of the line segments determined by these points lies inS. Clearly any union ofm?1 convex sets ism-convex, yet the converse is false and has inspired some interesting mathematical questions: Under what conditions will anm-convex set be decomposable intom?1 convex sets? And for everym≧2, does there exist aσ(m) such that everym-convex set is a union ofσ(m) convex sets? Pathological examples convince the reader to restrict his attention to closed sets of dimension≦3, and this paper provides answers to the questions above for closed subsets of the plane. IfS is a closedm-convex set in the plane,m ≧ 2, the first question may be answered in one way by the following result: If there is some lineH supportingS at a pointp in the kernel ofS, thenS is a union ofm ? 1 convex sets. Using this result, it is possible to prove several decomposition theorems forS under varying conditions. Finally, an answer to the second question is given: Ifm≧3, thenS is a union of (m?1)³2 ^m?3 or fewer convex sets.     

The smallestn-uniform hypergraph with positive discrepancy

A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erd?s and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc ₁ andc ₂ such that $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ where snd(x) is the least positive integer that does not dividex.     

Dynamic point location in arrangements of hyperplanes

We present algorithms for maintaining data structures supporting fast (polylogarithmic) point-location and ray-shooting queries in arrangements of hyperplanes. This data structure allows for deletion and insertion of hyperplanes. Our algorithms use random bits in the construction of the data structure but do not make any assumptions about the update sequence or the hyperplanes in the input. The query bound for our data structure isÕ(polylog(n)), wheren is the number of hyperplanes at any given time, and theÕ notation indicates that the bound holds with high probability, where the probability is solely with respect to randomization in the data structure. By high probability we mean that the probability of error is inversely proportional to a large degree polynomial inn. The space requirement isÕ(n ^d). The cost of update isÕ(n ^d?1 logn. The expected cost of update isO(n ^d?1); the expectation is again solely with respect to randomization in the data structure. Our algorithm is extremely simple. We also give a related algorithm with optimalÕ(logn) query time, expectedO(n ^d) space requirement, and amortizedO(n ^d?1) expected cost of update. Moreover, our approach has a versatile quality which is likely to have further applications to other dynamic algorithms. Ford=2, 3 we also show how to obtain polylogarithmic update time in the CRCW PRAM model so that the processor-time product matches (within a polylogarithmic factor) the sequential update time.     

Large tactical configurations

It is shown that if r = 2, then for all m, n, h ≥ 3 and all “large enough” R, W such that mR = nW, there is a tactical configuration of rank 2 girth g = 2h, and degrees m and n on sets of cardinalities R and W. We also show that if r ≥ 3 then for all h and all compatible degree sets N = {n(i, j)≥3} and all large enough numbers R(1), R(2),…, R(r) satisfying R(i)n(i, j) = R(j)n(j, i) there is a tactical configuration of rank r, girth h, and degrees N on set with cardinalities R(1), R(2),…, R(r).     

A test for identities satisfied in lattices of submodules

SupposeR is ring with 1, andH?(R) denotes the variety of modular lattices generated by the class of lattices of submodules of allR-modules. An algorithm using Mal'cev conditions is given for constructing integersm≧0 andn≧1 from any given lattice polynomial inclusion formulad∈e. The main result is thatd∈e is satisfied in every lattice inH?(R) if and only if there existsx inR such that (m·1)x=n·1 inR, where 0·1=0 andk·1=1+1...+1 (k times) fork≧1. For example, this “divisibility” condition holds form=2 andn=1 if and only if 1+1 is an invertible element ofR, and it holds form=0 andn=12 if and only if the characteristic ofR divides 12. This result leads to a complete classification of the lattice varietiesH?(R),R a ring with 1. A set of representative rings is constructed, such that for each ringR there is a unique representative ringS satisfyingH?(R)=H?(R). There is exactly one representative ring with characteristick for eachk≧1, and there are continuously many representative rings with characteristic zero. IfR has nonzero characteristic, then all free lattices inH?(R) have recursively solvable word problems. A necessary and sufficient condition onR is given for all free lattices inH?(R) to have recursively solvable word problems, ifR is a ring with characteristic zero. All lattice varieties of the formH?(R) are self-dual. A varietyH?(R) is a congruence variety, that is, it is generated by the class of congruence lattices of all members of some variety of algebras. A family of continuously many congruence varieties related to the varietiesH?(R) is constructed.     

On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series

For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write ${\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}}For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write \frach(t)(1 - t)^{d + 1}=?_{m 3 0} g(m)  t^m{\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}} , for some polynomial g(m) with rational coefficients, then \fracU_nh(t)(1- t)^d+1 = ?_{m 3 0}g(nm)  t^m{\frac{{\rm{U}}_{n}h(t)}{(1- t)^{d+1}} = \sum_{m \geq 0}g(nm) \, t^{m}} . We show that there exists a positive integer n _d , depending only on d, such that if h(t) is a polynomial of degree at most d with nonnegative integer coefficients and h(0) = 1, then for n ≥ n _d , U _n h(t) has simple, real, negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart δ-polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen–Macauley graded rings.     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

ɛ-nets and simplex range queries

We demonstrate the existence of data structures for half-space and simplex range queries on finite point sets ind-dimensional space,d≥2, with linear storage andO(n ^α ) query time, $$\alpha = \frac{{d(d - 1)}}{{d(d - 1) + 1}} + \gamma for all \gamma > 0$$ . These bounds are better than those previously published for alld≥2. Based on ideas due to Vapnik and Chervonenkis, we introduce the concept of an ?-net of a set of points for an abstract set of ranges and give sufficient conditions that a random sample is an ?-net with any desired probability. Using these results, we demonstrate how random samples can be used to build a partition-tree structure that achieves the above query time.     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

On van der Waerden's theorem and the theorem of Paris and Harrington

A 2-coloring of the non-negative integers and a function h are given such that if P is any monochromatic arithmetic progression with first term a and common difference d then 6P6 ? h(a) and 6P6 ? h(d). In contrast to this the following result is noted. For any k, f there is n = n(k, f) such that whenever n is k-colored there is a monochromatic subset A of n with 6A6 > f(d), where d is the maximum of the differences between consecutive elements of A.     

On edges crossing few other edges in simple topological complete graphs

We study the existence of edges having few crossings with the other edges in drawings of the complete graph (more precisely, in simple topological complete graphs). A topological graphT=(V,E) is a graph drawn in the plane with vertices represented by distinct points and edges represented by Jordan curves connecting the corresponding pairs of points (vertices), passing through no other vertices, and having the property that any intersection point of two edges is either a common end-point or a point where the two edges properly cross. A topological graph is simple if any two edges meet in at most one common point.Let h=h(n) be the smallest integer such that every simple topological complete graph on n vertices contains an edge crossing at most h other edges. We show that Ω(n^3/2)≤h(n)≤O(n²/log^1/4n). We also show that the analogous function on other surfaces (torus, Klein bottle) grows as cn².     

Some intersection theorems

LetL(A) be the set of submatrices of anm×n matrixA. ThenL(A) is a ranked poset with respect to the inclusion, and the poset rank of a submatrix is the sum of the number of rows and columns minus 1, the rank of the empty matrix is zero. We attack the question: What is the maximum number of submatrices such that any two of them have intersection of rank at leastt? We have a solution fort=1,2 using the followoing theorem of independent interest. Letm(n,i,j,k) = max(|F|;|G|), where maximum is taken for all possible pairs of families of subsets of ann-element set such thatF isi-intersecting,G isj-intersecting andF ansd,G are cross-k-intersecting. Then fori≤j≤k, m(n,i,j,k) is attained ifF is a maximali-intersecting family containing subsets of size at leastn/2, andG is a maximal2k?i-intersecting family. Furthermore, we discuss and Erd?s-Ko-Rado-type question forL(A), as well.     

Stability theorems for projections of convex sets

LetH ^n?1 denote the set of all (n ? 1)-dimensional linear subspaces of euclideann-dimensional spaceE ⁿ (n≧3), and letJ andK be two compact convex subsets ofE ⁿ. It is well-known thatJ andK are translation equivalent (or homothetic) if for allH ∈H ^n?1 the respective orthogonal projections, sayJ _H, K_H, are translation equivalent (or homothetic). This fact gives rise to the following stability problem: Ifε≧0 is given, and if for everyH ∈H ^n?1 a translate (or homothetic copy) ofK _H is within Hausdorff distanceε ofJ _H, how close isJ to a nearest translate (or homothetic copy) ofK? In the case of translations it is shown that under the above assumptions there is always a translate ofK within Hausdorff distance (1 + 2√2)ε ofJ. Similar results for homothetic transformations are proved and applications regarding the stability of characterizations of centrally symmetric sets and spheres are given. Furthermore, it is shown that these results hold even ifH ^n?1 is replaced by a rather small (but explicitly specified) subset ofH ^n?1.     

Empty Monochromatic Simplices

Let S be a k-colored (finite) set of n points in $\mathbb{R}^{d}$ , d≥3, in general position, that is, no (d+1) points of S lie in a common (d?1)-dimensional hyperplane. We count the number of empty monochromatic d-simplices determined by S, that is, simplices which have only points from one color class of S as vertices and no points of S in their interior. For 3≤k≤d we provide a lower bound of $\varOmega(n^{d-k+1+2^{-d}})$ and strengthen this to Ω(n ^d?2/3) for k=2. On the way we provide various results on triangulations of point sets in  $\mathbb{R}^{d}$ . In particular, for any constant dimension d≥3, we prove that every set of n points (n sufficiently large), in general position in $\mathbb{R}^{d}$ , admits a triangulation with at least dn+Ω(logn) simplices.     

A family of examples showing that no Krasnosel’skii number exists for orthogonal polygons starshaped via staircase n-paths

Let S be a simply connected orthogonal polygon in the plane. A family of examples will establish the following result. For every n ≥ 2, there exists no Krasnosel’skii number h(n) which satisfies this property: If every h(n) points of S are visible via staircase n-paths from a common point, then S is starshaped via staircase n-paths.     

Boundary Multifractal Behaviour for Harmonic Functions in the Ball

It is well known that if h is a nonnegative harmonic function in the ball of $\mathbb R^{d+1}$ or if h is harmonic in the ball with integrable boundary values, then the radial limit of h exists at almost every point of the boundary. In this paper, we are interested in the exceptional set of points of divergence and in the speed of divergence at these points. In particular, we prove that for generic harmonic functions and for any β?∈?[0,d], the Hausdorff dimension of the set of points ξ on the sphere such that h(rξ) looks like (1???r)^???β is equal to d???β.     

Distances realized by sets covering the plane

A proof is given of the (known) result that, if real n-dimensional Euclidean space Rⁿ is covered by any n + 1 sets, then at least one of these sets is such that each distance d(0 < d < ∞) is realized as the distance between two points of the set. In particular, this result holds if the plane is covered by three sets; but it does not necessarily hold if the plane is covered by six sets. If each set in a covering of the plane fails to realize the same distance d, say d = 1, and if the sets are either closed or simultaneously divisible into region (in a sense to be made precise), then at least six sets are needed and seven suffice, and the number of closed sets needed is at least as great as the number simultaneously divisible into regions.     

On a generalized Minkowski inequality and its relation to dominates for t-norms

Leth:?⁺ → ?⁺ be a continuous strictly increasing function withh(0) = 0. Such functionsh give rise to a generalization of the Minkowski inequality; namely, (1) $$h^{ - 1} (h(a + b) + h(c + d)) \leqq h^{ - 1} (h(a + c) + h(b + d))$$ wherea, b, c, andd are arbitrary non-negative real numbers. Theorem 1 shows that, ifh and logh′ (e ^x ) are both convex functions, thenh satisfies (1). Theorem 2, the major result, demonstrates that, if bothh ₁ andh ₂ satisfy the hypotheses of Theorem 1, then the composition ofh ₁ withh ₂ also satisfies the hypotheses of Theorem 1 and hence the inequality (1). The remainder of the paper shows how (1) and Theorems 1 and 2 impinge on the dominates relation for strict t-norms. In particular, Theorem 3 shows how (1) can be interpreted as equivalent to the dominates relation for two strict t-norms. Theorem 4 shows how to use Theorems 1 and 3 to construct a strict t-norm which dominates a given strict t-norm. And, Theorem 5 shows how Theorem 2 can be used to give a qualified answer of yes to the open question of whether or not the dominates relation is a transitive relation.