Maximal Local Time of a <Emphasis Type="Italic">d</Emphasis>-dimensional Simple Random Walk on Subsets

Strong theorems are given for the maximal local time on balls and subspaces for the d-dimensional simple symmetric random walk.Endre Csáki - Research supported by the Hungarian National Foundation for Scientific Research, Grant No. T 037886 and T 043037.Pál Révész - Research supported by a PSC CUNY Grant, No. 65685-0034.     

On the possible number of elements of given order in a finite group

The main motivation of this paper is to introduce a problem of some combinatorial flavor about finite groups which seems to be new in the literature. Letk>1 be a fixed positive integer and denote byf(k, G) the number of elements of orderk in the groupG. We examine the setF(k)={f(k, G)| G a finite group}/{0}. We give a complete characterization ofF(k) if 4|k ork=6 and show some modest partial results for certain other values ofk. It seems to us that the question is surprisingly difficult even in such simple cases ask=3, which we investigate in detail. Research (partially) supported by Hungarian National Foundation for Scientific Research (OTKA), Grant No. 1901. Research (partially) supported by Hungarian National Foundation for Scientific Research (OTKA), Grant No. 1903.     

Lebesgue function type sums of Hermite interpolations

Research supported by Hungarian National Foundation for Scientific Research Grant No. 1910.     

Short notes on quasi-uniform spaces II. Doubly uniformly strict extensions

Research supported by Hungarian National Foundation for Scientific Research, Grant No. 2114.     

Lacunary sequences and conditional independence

Research supported by Hungarian National Foundation for Scientific Research, Grant No. 1905.     

Product sets in the plane,sets of the formA+B on the real line and Hausdorff measures

Research supported by the Hungarian National Foundation for Scientific Research Grant No. 2114.     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

On the characterization of additive functions with quadratic arguments

Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901.     

Additive completion and disjoint translations

Supported by Hungarian National Foundation for Scientific Research, Grant No. 1901.     

Aronszajn null and Gaussian null sets coincide

We prove that in every separable Banach space the σ ideals of Aronszajn null sets, Gaussian null sets and cube null sets coincide. Research supported by the Hungarian National Foundation for Scientific Research Grant No. T019476 and FKFP Grant 0189/1997.     

A consistency result concerning set mappings

Research supported by Hungarian National Science Foundation Grant No. 1908 and 2117.     

Distributed computing viewed as a team problem with constraints

The optimal distribution of the workload in a system of interconnected computer units is considered. Formulated as a team decision problem with a singular cost criterion and with equality and inequality constraints, it is shown that the problem admits always a unique piecewise linear strategy which is globally optimal. Some interesting particular cases are studied.The research reported in this paper was made possible through support from the Office of Naval Research under the Joint Services Electronics Program by Contract No. N00014-75-C-0648 and Contract No. N00014-77-C-0531 and by the National Science Foundation, Grant No. ENG-76-11824.     

Fundamental domains for planar discontinuous groups and uniform tilings

In this paper, we classify combinatorially different fundamental domains for any given planar discontinuous group and we give an algorithm for the complete enumeration of uniform tilings of any complete, simply connected, two-dimensional Riemannian manifold of constant curvature.Supported by Hungarian National Foundation for Scientific Research, Grant No. 1238/86.     

Mean convergence of hermite interpolation revisited

The first author is supported by the Hungarian National Foundation for Scientific Research Grant No. 1910 and No. T7570, and the second author is supported by the National Science Foundation Grant No. 9302721. The work was done during the first author's visit in Eugene, Oregon in 1993, and was completed during the second author's visit to the Mathematisches Institut, University of Erlange-Nürnberg, supported by the Alexander von Humboldt Foundation.     

Unconstrained multilayer switchbox routing

Consider the gradually more and more complexproblems of single row routing, channel routing and switchbox routing on the one hand, and the gradually less and less restrictivemodels (1-layer, Manhattan, unconstrained 2-layer, multilayer) on the other hand. The single row routing problems can always be solved in the Manhattan model, and the channel routing problem can always be solved in the unconstrained 2-layer model, in fact, both in linear time. In this paper, we show that the switchbox routing problem is solvable in the multilayer model, also in linear time.Supported in part by the Office of Naval Research (Grants N0001492J1375 and N0001492J4083) and by the Air Force Office of Scientific Research (Grants 89-0512B and F49620-93-1-0041).Research partially supported by the Hungarian National Foundation for Scientific Research (Grant No. OTKA 2118, 2505), and by the EC Cooperative Action IC 1000, Algorithms for Future Technologies (ALTEC).     

Groups with super-exponential subgroup growth

We show that, if the subgroup growth of a finitely generated (abstract or profinite) groupG is super-exponential, then every finite group occurs as a quotient of a finite index subgroup ofG. The proof involves techniques from finite permutation groups, and depends on the Classification of Finite Simple Groups.The first author was partially supported by the Hungarian National Foundation for Scientific Research, Grant No. T7441. The second author was partially supported by the Israeli National Science Foundation.     

On the pseudolinearity of quadratic fractional functions

The main result is a new characterization of the pseudolinearity of quadratic fractional functions. This research was supported in part by the Hungarian Scientific Research Fund, Grant No. OTKA-T043276 and OTKA-K60480.     

A converse result for approximation by a weighted Szász-Mirakyan operator

We prove that the weighted error of approximation by the Szász-Mirakyan-type operator introduced in [1] is equivalent to the modulus of smoothness of the function. This result is analogous to previous results for Bernstein-type operators obtained by Ditzian-Ivanov and Szabados. Research supported by Hungarian Scientific Research Fund (OTKA), Grant No. T-049196.     

Sufficient Optimality Criterion for Linearly Constrained,Separable Concave Minimization Problems

A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimality criterion is based on the sensitivity analysis of the relaxed linear programming problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive.In the Phillips and Rosen paper (Ref. 1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimality of the current basic solution.The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithms developed for linearly-constrained concave minimization problems.This research was supported by a Bolyai János Research Fellowship BO/00334/00 of the Hungarian Academy of Science and by the Hungarian Scientific Research Foundation, Grant OTKA T038027.