A topological approach to evasiveness

The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the graph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity Ω(v ²) wherev is the number of vertices. Karp conjectured that every such property is evasive, i.e., requires that every entry of the incidence matrix be examined. In this paper the truth of Karp’s conjecture is shown to follow from another conjecture concerning group actions on topological spaces. A special case of the conjecture is proved which is applied to prove Karp’s conjecture for the case of properties of graphs on a prime power number of vertices. Supported in part by an NSF postdoctoral fellowship Supported in part by NSF under grant No. MCS-8102248     

An Ω(n 5/4) lower bound on the randomized complexity of graph properties

A decision tree algorithm determines whether an input graph withn nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for somes but not all graphs) have been shown to require (n ²) queries in the worst case.In this paper, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next entry to be examined. The complexity of a randomized algorithm is the expected number of entries that are examined in the worst case. The randomized complexity of a property is the minimum complexity of any randomized decision tree algorithm which computes the property. We improve Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from (n log^1/12 n) to (n ^5/4).     

Small topological complete subgraphs of “dense” graphs

A graph ofn vertices and edges contains aTK _t on at most 7t ² logt/ vertices. This answers a question of P. Erds.     

Asymptotic limit law for the close approach of two trajectories in expanding maps of the circle

Summary Given two pointsx, yS ¹ randomly chosen independently by a mixing absolutely continuous invariant measure of a piecewise expanding and smooth mapf of the circle, we consider for each >0 the point process obtained by recording the timesn>0 such that |f ⁿ (x)–f ⁿ (y)|. With the further assumption that the density of is bounded away from zero, we show that when tends to zero the above point process scaled by –1 converges in law to a marked Poisson point process with constant parameter measure. This parameter measure is given explicity by an average on the rate of expansion off.Partially supported by FAPESP grant number 90/3918-5     

A remark on generalized iterates

Letf be an invertible function on the real lineR, and letZ denote the set of integers. For eachx Z, letf ^|n| denote then'th iterate off. Clearlyf ^|m|(f ^|n|(x))=f ^|m+n|(x) for allm,nZ and allxR. LetG be any group of orderc, the cardinality of the continuum, which contains (an isomorphic copy of)Z as a normal subgroup. If for eachxR, the iteration trajectory (orbit) ofx is non-periodic, then there exists a set of invertible functionsF={F ^||:G} on the real line with the properties (i)F ^||(F ^||(x))=F ^|+| (x) for allxR and (ii)F ^|n|(x)=f ^|n|(x) for allnZ andxR. That is,f can be embedded in a set ofG-generalized iterates. In particular,f can be embedded in a set of complex generalized iterates.Dedicated to Professor Janos Aczél on his 60th birthday     

Some Ramsey-Turán type results for hypergraphs

To everyk-graphG let(G) be the minimal real number such that for every>0 andn>n ₀(,G) everyk-graphH withn vertices and more than (+) ( ) edges contains a copy ofG. The real number (G) is defined in the same way adding the constraint that all independent sets of vertices inH have sizeo(n). Answering a problem of Erds and Sós it is shown that there exist infinitely manyk-graphs with 0<(G)<(G) for everyk3. It is worth noting that we were unable to find a singleG with the above property.This paper was written while the authors were visiting AT&T Bell Laboratories, Murray Hill, NJ 07974.     

ε-Enlargements of Maximal Monotone Operators in Banach Spaces

Given a maximal monotone operator T in a Banach space, we consider an enlargement T, in which monotonicity is lost up to , in a very similar way to the -subdifferential of a convex function. We establish in this general framework some theoretical properties of T, like a transportation formula, local Lipschitz continuity, local boundedness, and a Brøndsted–Rockafellar property.     

Über die Normalteiler scharf zweifach und scharf dreifach transitiver Permutationsgruppen

A sharply 2-transitive (3-transitive) groupT can be described by means of a neardomainF (a KT-field(F,)). We show, thatT has a least nontrivial normal subgroupA (S(F,)), ifF is a nearfield or if CharF 2. In this case the nontrivial normal subgroups ofT correspond bijectively with all normal subgroupsF ^* (the multiplicative group ofF) containing a setD (D(Q)). IfF is a nearfield or ifF has a suitable central element, then the group S(F,) is simple.

---

---

Herrn Prof. Dr. Dr. h. c. Helmut Karzel zum 70. Geburtstag gewidmet     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

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.     

An approximation for the zeros of Bessel functions

Summary LetC _vk be thekth positive zero of the cylinder functionC _v(x)=cosJ _v(x)–sinY _v(x), whereJ _v(x),Y _v(x) are the Bessel functions of first kind and second kind, resp., andv>0, 0<. Definej _vk byj _vk=C _vk with . Using the notation 1/K=, we derive the first two terms of the asymptotic expansion ofj _vk in terms of the powers of at the expense of solving a transcendental equation. Numerical examples are given to show the accuracy of this approximation.Dedicated to the memory of Professor Lothar CollatzThis work has been supported by the Hungarian Scientific Grant No. 6032/6319     

Optimization of adaptive algorithms for the renewal of monotone functions from the classHω

A problem of renewal of monotone functionsf(t) H [a, b] with fixed values at the ends of an interval is studied by using adaptive algorithms for calculating the values off(t) at certain points. Asymptotically exact estimates unimprovable on the entire set of adaptive algorithms are obtained for the least possible numberN() of steps providing the uniform-error. For moduli of continuity of type , 0<<1, the valueN() has a higher order as0 than in the nonadaptive case for the same amount of information.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 45, No. 12, pp. 1627–1634, December, 1993.The work was supported by the Foundation for Fundamental Studies of Ukrainian State Committee for Science and Technology.     

The picture of a specific maximal monotone set

Let E be a nontrivial Banach space. The concept of picture has been used to provide a new proof of the surjectivity of S+J, for E reflexive and S: E2 ^{E *} maximal monotone. It is known that if E is reflexive, then the picture of a maximal monotone subset of E×E ^* is a singleton. We calculate an example showing that in the nonreflexive case, the picture of a maximal monotone subset can be quite substantial.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

On nonnegative solvability of linear operator equations

LetE be a Banach lattice having order continuous norm. Suppose, moreover,T is a nonnegative reducible operator having a compact iterate and which mapsE into itself. The purpose of this work is to extend the previous results of the authors, concerning nonnegative solvability of (kernel) operator equations on generalL ^p-spaces. In particular, we provide necessary and sufficient conditions for the operator equation x=T x+y to possess a nonnegative solutionxE wherey is a given nonnegative and nontrivial element ofE and is any given positive parameter.     

For Which Densities are Random Triangle-Free Graphs Almost Surely Bipartite?

Denote by the class of all triangle-free graphs on n vertices and m edges. Our main result is the following sharp threshold, which answers the question for which densities a typical triangle-free graph is bipartite. Fix > 0 and let . If n/2 m (1 – ) t ₃, then almost all graphs in are not bipartite, whereas if m (1 + )t ₃, then almost all of them are bipartite. For m (1 + )t ₃, this allows us to determine asymptotically the number of graphs in . We also obtain corresponding results for C -free graphs, for any cycle C of fixed odd length. Forschergruppe Algorithmen, Struktur, Zufall supported by Deutsche Forschungsgemeinschaft grant FOR 413/1-1     

The scaling limit for a stochastic PDE and the separation of phases

Summary We investigate the problem of singular perturbation for a reaction-diffusion equation with additive noise (or a stochastic partial differential equation of Ginzburg-Landau type) under the situation that the reaction term is determined by a potential with double-wells of equal depth. As the parameter (the temperature of the system) tends to 0, the solution converges to one of the two stable phases and consequently the phase separation is formed in the limit. We derive a stochastic differential equation which describes the random movement of the phase separation point. The proof consists of two main steps. We show that the solution stays near a manifoldM of minimal energy configurations based on a Lyapunov type argument. Then, the limit equation is identified by introducing a nice coordinate system in a neighborhood ofM .Research partially supported by Japan Society for the Promotion of Science     

Characterization of complete exterior sets of conics

Let be a set of exterior points of a nondegenerate conic inPG(2,q) with the property that the line joining any 2 points in misses the conic. Ifq1 (mod 4) then consists of the exterior points on a passant, ifq3 (mod 4) then other examples exist (at least forq=7, 11, ..., 31).Support from the Dutch organization for scientific Research (NWO) is gratefully acknowledged     

Rational congruence for uniform multiplicative designs

A multiplicative design is a family ofn subsets of ann-set whose incidence matrixA satisfiesA ^T A=D+ ^T where is a positive real vector andD is a positive diagonal matrix. This is a generalization of-designs where is a constant vector and of (v, k, )-designs whereD is additionally required to be scalar. In a uniform design we only require thatD be scalar, so the equation isA ^T A=dI+ ^T .One of the basic results on (v, k, )-designs is the Bruck-Ryser-Chowla Theorem which says thatk– must be a square ifv is even and thatz ²=(k–)x ²+y ²(–1)^(v–1)/2 must have a nontrivial integral solution ifv is odd. This can be proved with or without reference to the theory of rational congruences.The purpose of this paper is to investigate the implications of the theory of rational congruences for the existence of uniform multiplicative designs. The Hass-Minkowski Theorem provides the main line of attack. The main result gives a finite set of equations, suitable for programming on a computer, which must be satisfied if there is a rational matrix satisfying the equationA ^T A=dI+ ^T for a uniform design.     

Approximation Schemes for Scheduling Jobs with Common Due Date on Parallel Machines to Minimize Total Tardiness

The problem of scheduling n nonpreemptive jobs having a common due date d on m, m 2, parallel identical machines to minimize total tardiness is studied. Approximability issues are discussed and two families of algorithms {A } and {B } are presented such that (T ⁰ – T*)/(T* + d) holds for any problem instance and any given > 0, where T* is the optimal solution value and T ⁰ is the value of the solution delivered by A or B . Algorithms A and B run in O(n ^2m / ^m–1) and O(n ^m+1/ ^m ) time, respectively, if m is a constant. For m = 2, algorithm A can be improved to run in O(n ³/) time.