Symmetrische Permutationsmengen

A permutation set (M, I) consisting of a setM and a set of permutations ofM, is calledsymmetric, if for any two permutations, the existence of anx M with (x) (x) and ^–1 (x) = ^–1 (x) implies ^–1 = ^–1 , andsharply 3-transitive, if for any two triples (x ₁,x ₂,x ₃), (y ₁,y ₂,y ₃) M ³ with|{x ₁,x ₂,x ₃ }| = |{y ₁,y ₂,y ₃ }| = 3 there is exactly one permutation with(x ₁) =y ₁,(x ₂) =y ₂,(x ₃) =y ₃. The following theorem will be proved.THEOREM.Let (M, ) be a sharply 3-transitive symmetric permutation set with |M|3, such that contains the identity. Then is a group and there is a commutative field K such that and the projective linear group PGL(2, K) are isomorphic.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

Maximal order for quadratures usingn evaluations

The problem is to find approximationsI (f; h) to the integralI(f; h)= ₀ ^h f. Such an approximation has local orderp ifI(f; h)–I (f; h)=O(h ^p ) ash0. Let(n) denote the maximal local order possible for a method usingn evaluations of a function or its derivatives. We show that (n)=2n+1 if the information used is Hermitian. This is conjectured to be true in general. The conjecture is established for all methods using three or fewer evaluations.This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370, NR 044-422. Numerical results reported in this paper were obtained through the computing facilities of the University of Maryland.     

The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

On the divisibility of homogeneous hypergraphs

We denote byK _k ,k, 2, the set of allk-uniform hypergraphsK which have the property that every element subset of the base ofK is a subset of one of the hyperedges ofK. So, the only element inK ₂ ² are the complete graphs. If is a subset ofK _k then there is exactly one homogeneous hypergraphH whose age is the set of all finite hypergraphs which do not embed any element of . We callH -free homogeneous graphsH _n have been shown to be indivisible, that is, for any partition ofH _n into two classes, oue of the classes embeds an isomorphic copy ofH _n . [5]. Here we will investigate this question of indivisibility in the more general context of-free homogeneous hypergraphs. We will derive a general necessary condition for a homogeneous structure to be indivisible and prove that all-free hypergraphs for K _k with 3 are indivisible. The-free hypergraphs with K _k ² satisfy a weaker form of indivisibility which was first shown by Henson [2] to hold forH _n . The general necessary condition for homogeneous structures to be indivisible will then be used to show that not all-free homogeneous hypergraphs are indivisible.This research has been supported by NSERC grant 69–1325.     

Limits of balayage measures

LetA be a subset of a balayage space (X,W) and a measure onX. It is shown that for every sequence _n of measures such that lim_nn and lim_{n n} ^A = the limit measure is of the formf+[(1-f)]^A for some (unique) Borel function 0f1_Cb(A). Furthermore, conditions are given such that any such functionf occurs.     

On depth first search strees inm-out digraphs

We consider depth first search (DFS for short) trees in a class of random digraphs: am-out model. Let _i be thei ^th vertex encountered by DFS andL(i, m, n) be the height of _i in the corresponding DFS tree. We show that ifi/n asn, then there exists a constanta(,m), to be defined later, such thatL(i, m, n)/n converges in probability toa(,m) asn. We also obtain results concerning the number of vertices and the number of leaves in a DFS tree.     

On ηα-groups and fields

Let :=. The following are known: two -sets of power are isomorphic. Let >0. Two ordered divisible Abelian groups that are -sets of power are isomorphic, two real closed fields that are -sets of power are isomorphic. The following is shown: (1) there exist 2 nonisomorphic ordered Abelian groups (respectively ordered fields) that are -sets of power ; (2) there exist 2 nonisomorphic ordered divisible Abelian groups (respectively real closed fields) of power all having the same order type; (3) there exist 2 nonisomorphic ordered divisible Abelian groups (respectively real closed fields) that are -sets having the same order type.     

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.     

Harmonic analysis on tori

We consider measurable subsets {ofR}ⁿ with 0<m()<, and we assume that has a spectral set . (In the special case when is also assumed open, may be obtained as the joint spectrum of a family of commuting self-adjoint operators {H _k: 1kn} in L ² () such that each H _k is an extension of i(/x _k) on C _c (), k=1, ..., n.)It is known that is a fundamental domain for a lattice if is itself a lattice. In this paper, we consider a class of examples where is not assumed to be a lattice. Instead is assumed to have a certain inhomogeneous form, and we prove a necessary and sufficient condition for to be a fundamental domain for some lattice in {ofR}ⁿ. We are thus able to decide the question, fundamental domain or not, by considering only properties of the spectrum . Our criterion is obtained as a corollary to a theorem concerning partitions of sets which have a spectrum of inhomogeneous form.Work supported in part by the NSF.Work supported in part by the NSRC, Denmark.     

Packing directed circuits fractionally

LetG be a digraph, and letk1, such that no fractional packing of directed circuits ofG has value >k, when every vertex is given capacity 1. We prove there is a set ofO (k logk logk) vertices meeting all directed circuits ofG.     

On graphs that can be oriented as diagrams of ordered sets

We study some equivalent and necessary conditions for a finite graph to be the covering graph of a (partially) ordered set. For each 1, M. Aigner and G. Prins have introduced a notion of a vertex colouring, here called -good colouring, such that a 1-good colouring is the usual concept and graphs that have a 2-good colouring are precisely covering graphs. We present some inequalities for the corresponding chromatic numbers , especially for x ₂. There exist graphs that satisfy these inequalities for =2 but are not covering graphs. We show also that x ₂ cannot be bounded by a function of x=x ₁. A construction of Neetil and Rödl is used to show that x ₂ is not bounded by a function of the girth.     

Differentiability properties of the minimal average action

Given aZ ⁿ⁺¹-periodic variational principle onR ⁿ⁺¹ we look for solutionsu:R ⁿ R minimizing the variational integral with respect to compactly supported variations. To every vector R ⁿ we consider a subset of solutions which have an average slope when averaging overR ⁿ. The minimal average action A() is defined by the average value of the variational integral given by a solution with average slope . Our main result is:A is differentiable at if and only if the set is totally ordered (in the natural sense). In case that is not totally ordered,A is differentiable at in some direction R ⁿ{0} if and only if is orthogonal to the subspace defined by the rational dependency of . Assuming that the i^th component of is rational with denominator sⁱ N in lowest terms, we show: The difference of right- and left-sided derivative in the i^th standard unit direction is bounded by const · .     

Packing circuits in eulerian digraphs

LetG be an eulerian digraph; let (G) be the maximum number of pairwise edge-disjoint directed circuits ofG, and (G) the smallest size of a set of edges that meets all directed circuits ofG. Borobia, Nutov and Penn showed that (G) need not be equal to (G). We show that (G)=(G) provided thatG has a linkless embedding in 3-space, or equivalently, if no minor ofG can be converted toK ₆ by –Y andY– operations.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

On the stochastic independence properties of hard-core distributions

A probability measurep on the set of matchings in a graph (or, more generally 2-bounded hypergraph) ishard-core if for some : [0,), the probabilityp(M) ofM is proportional to . We show that such distributions enjoy substantial approximate stochastic independence properties. This is based on showing that, withM chosen according to the hard-core distributionp, MP () the matching polytope of , and >0, if the vector ofmarginals, (Pr(AM):A an edge of ), is in (1–) MP (), then the weights (A) are bounded by someA(). This eventually implies, for example, that under the same assumption, with fixed, as the distance betweenA, B tends to infinity.Thought to be of independent interest, our results have already been applied in the resolutions of several questions involving asymptotic behaviour of graphs and hypergraphs (see [14, 16], [11]–[13]).Supported in part by NSFThis work forms part of the author's doctoral dissertation [16]; see also [17]. The author gratefully acknowledges NSERC for partial support in the form of a 1967 Science and Engineering Scholarship.     

Local Recognition Of Non-Incident Point-Hyperplane Graphs

Let be a projective space. By H() we denote the graph whose vertices are the non-incident point-hyperplane pairs of , two vertices (p,H) and (q,I) being adjacent if and only if p I and q H. In this paper we give a characterization of the graph H() (as well as of some related graphs) by its local structure. We apply this result by two characterizations of groups G with PSL _n ( )GPGL _n ( ), by properties of centralizers of some (generalized) reflections. Here is the (skew) field of coordinates of .     

On an isomorphism problem on the closed-set lattice of a graph

Let (G) and V(G) be, respectively, the closed-set lattice and the vertex set of a graph G. Any lattice isomorphism : V(G)(G) induces a bijection : V(G)V(G) such that for each x in V(G), (x)=x' in V(G') iff ({x})={x'}. A graph G is strongly sensitive if for any graph G' and any lattice isomorphism : (G)(G), the bijection induced by is a graph isomorphism of G onto G'. In this paper we present some sufficient conditions for graphs to be strongly sensitive and prove in particular that all C ₄-free graphs and all covering graphs of finite lattices are strongly sensitive.     

An extension of the Erdős-Stone theorem

LetK _p(u₁, ..., u_p) be the completep-partite graph whoseith vertex class hasu _i vertices (lip). We show that the theorem of Erds and Stone can be extended as follows. There is an absolute constant >0 such that, for allr1, 0<1 and=">1/r, every graphG=G ⁿ of sufficiently large order |G|=n with at least

Asymptotics of polynomials orthogonal with respect to varying measures

Letd be a finite positive Borel measure on the interval [0, 2] such that >0 almost everywhere; andW _n be a sequence of polynomials, degW _n =n, whose zeros (w _n ,1,,w _n,n lie in [|z|1]. Let d _n <> for each_nN, whered _n =d/|W _n (e ⁱ )|². We consider the table of polynomials _n,m such that for each fixednN the system _n,m,mN, is orthonormal with respect tod _n . If