On the products of cross-ratios on diagonals of polygons

The purpose of this paper is to establish a conjecture of B. Grünbaum, which states that in every n-polygon P in the plane, n 5, some diagonals intersect in a pattern that defines a new n-polygon (P), such that the product of the cross-rations on the diagonals of P is equal to the product of the corresponding cross-ratios on the diagonals of (P).     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

Norm-graphs and bipartite turán numbers

For everyt>1 and positiven we construct explicit examples of graphsG with |V (G)|=n, |E(G)|c _t ·n ^2–1/t which do not contain a complete bipartite graghK _t,t !+1 This establishes the exact order of magnitude of the Turán numbers ex (n, K _t,s ) for any fixedt and allst!+1, improving over the previous probabilistic lower bounds for such pairs (t, s). The construction relies on elementary facts from commutative algebra.Research supported in part by NSF Grants DMS-8707320 and DMS-9102866.Research supported in part by Hungarian National Foundation for Scientific Research Grant     

Zero cycles on conic fibrations and a conjecture of Bloch

Let X be a smooth projective surface over a number field k. Let (CH₀(X)) denote the Chow group of zero-cyles modulo rational equivalence on X. Let CH₀(X) be the subgroup of CH ₀(X) consisting of classes which vanish when going over to an arbitrary completion of k. Bloch put forward a conjecture asserting that this group is isomorphic to the Tate-Shafarevich group of a certain Galois module atttached to X. In this paper, we disprove this general conjecture. We produce a conic bundle X over an elliptic curve, for which the group (CH₀(X) is not zero, but the Galois-theoretic Tate-Shafarevich group vanishes.     

The algebra of differential operators on the circle and W KP (q)

Radul has recently introduced a map from the Lie algebra of differential operators on the circle of W _n . In this Letter, we extend this map to W _KP ^(q) , a recently introduced one-parameter deformation of W_KP - the second Hamiltonian structure of the KP hierarchy. We use this to give a short proof that W is the algebra of additional symmetries of the KP equation.     

TheS=1/2 Heisenberg antiferromagnet on the triangular lattice: Exact results and spin-wave theory for finite cells

We study the ground state properties of theS=1/2 Heisenberg antiferromagnet (HAF) on the triangular lattice with nearest-neighbour (J) and next-nearest neighbour (J) couplings. Classically, this system is known to be ordered in a 120° Néel type state for values-<1/8 of the ratio of these couplings and in a collinear state for 1/8<<1. The order parameter and the helicity /gC of the 120° structure are obtained by numerical diagonalisation of finite periodic systems of up toN=30 sites and by applying the spin-wave (SW) approximation to the same finite systems. We find a surprisingly good agreement between the exact and the SW results in the entire region-<<1/8. It appears that the SW theory is still valid for the simple triangular HAF (=0) although the sublattice magnetisation is substantially reduced from its classical value by quantum fluctuations. Our numerical results for the order parameterM of the collinear order support the previous conjecture of a first order transition between the 120° and the collinear order at 1/8.     

14N遥测核四极共振中的偏离共振效应

本文对遥测NQR谱中的偏离共振效应作了较详细地研究,发现¹⁴N谱线的强度随偏离共振效应而变化。当偏离共振强度与射频场强度接近时,测得的谱线强度最大。该效应可用来增强¹⁴N遥测NQR谱仪的灵敏度。上述实验现象在理论上采用脉冲的激发带宽方法作了解释和讨论。     

A θ-stable approximations of abstract Cauchy problems

Summary We study the approximation of linear parabolic Cauchy problems by means of Galerkin methods in space andA -stable multistep schemes of arbitrary order in time. The error is evaluated in the norm ofL _t ² (H _x ¹ ) L _t (L _x ² ).     

Cyclic actions on some Klein bottle bundles over S1

Leth be a cyclic action of periodn onM, whereM is eitherS ¹×K, K is the Klein bottle or on , the twisted Klein bottle bundle overS ¹, such that there is a fiberingq:MS ¹ with fiber a Klein bottleK or a torusT with respect to which the action is fiber preserving. We classify all such actions and show that they might be distinguished by their fixed points or by their orbit spaces.