On the dimension to represent a graph by a unit distance graph

It is proved that if a graphG has maximum degreed, then its vertices can be represented by distinct unit vectors inR ^2d so that two vectors are orthogonal if and only if the corresponding vertices are adjacent. As a corollary it follows that if a graph has maximum degreed, then it is isomorphic to a unit distance graph inR ^2d.     

Integer points on hypersurfaces

Very general hypersurfaces in ⁴ contain r ^2+(4/9) integer points in any ball of radiusr>1. As a consequence, an irreducible algebraic hypersurface in ⁿ (wheren4) which is not a cylinder and is of degreed, contains c(d, n)r ^{n–1–(5/9)} integer points in a ball of radiusr. This improves on the known boundc(d, n)r ^n–(3/2).Meinem verehrten Lehrer Professor E. Hlawka zum siebzigsten Geburtstag gewidmetWritten with partial support from NSF-MCS-8211461.     

On the information rate of perfect secret sharing schemes

In this paper, information rates of perfect secret sharing schemes are studied, in particular schemes based on connected graphs on six vertices. We discuss a method to derive information-theoretical upper bounds on the optimal information rate and the optimal average information rate. Stinson [19] proved the general result that, for any graphG having maximum degreed, there exists a perfect secret sharing scheme realizingG with (average) information rate at least 2/(d+1). For alld3 and >0, we construct graphs having maximum degreed such that the optimal (average) information rate is at most 2/(d+1–).     

Flex Curves and their Applications

In this paper, we define the notion of the flex curve F ⁽⁾(f; P) at a nonsingular point P of a plane curve Ca. We construct interesting plane curves using a cyclic covering transform, branched along F ⁽⁾(f; P). As an application, we show the moduli space of projective curves of degree 12 with 27 cusps has at least three irreducible components. Simultaneously, we give an example of Alexander-equivalent Zariski pair of irreducible curves.     

Constructions of harmonic polynomial maps between spheres

The complexity of _q -eigenmaps, i.e. homogeneous degreeq harmonic polynomial mapsf:S ^m S ⁿ, increases fast with the degreeq and the source dimensionm. Here we introduce a variety of methods of manufacturing new eigenmaps out of old ones. They include degree and source dimension raising operators. As a byproduct, we get estimates on the possible range dimensions of full eigenmaps and obtain a geometric insight of the harmonic product of ₂-eigenmaps.     

On a generalization of the Gallai-Sylvester theorem

It is shown that ifS ^d , affS=aff ^d , and every hyperplane spanned by (a subset of)S misses fewer thank points ofS(k2), then (a) #Skm ifd=2m–1 is odd and (b) #Skm+1 ifd=2m is even. We also fully describe the extreme sets for which equality holds in (a) or in (b). For oddd the proofs are later modified to purely algebraic ones, and carry over to , where is an arbitrary field. For evend, (b) is generally not true when , but we prove some weaker inequalities that do hold over arbitrary fields.This is part of a Ph.D. thesis, supervised by Professor Micha A. Perles at the Hebrew University of Jerusalem. This research was supported in part by the Landau Center for Mathematical Research.     

How to be sure of finding a root of a complex polynomial using Newton's method

The trouble with Newton's method for finding the roots of a complex polynomial is knowing where to start the iteration. In this paper we apply the theory of rational maps and some estimates based on distortion theorems for univalent functions to find lower bounds, depending only on the degreed, for the size of regions from which the iteration will certainly converge to a root. We can also bound the number of iterations required and we give a method that works for every polynomial and takes at most some constant timesd ²(logd)² log(d ³/) iterations to find one root to within an accuracy of .     

Gorenstein curves and symmetry of the semigroup of values

LetO be the local ring of a irreducible algebroid curve and S its semigroup of values, Kunz in [7] proves thatO is a Gorenstein ring if and only if S is symmetrical. In this paper we give a generalization of this fact for the case of reduced curves with an arbitrary number of branches, d. For it we introduce a concept of symmetry for the semigroup of values S₊ ^d which generalizes the well known symmetry for d=1 (i.e. the irreducible case). This concept of symmetry is also closely related to the symmetry introduced by García in [4] (for the d=2 case) and the author in [3] (for arbitrary d) with the main goal of the explicit determination of S (in the case of plane curves).     

Some remarks on the schemesW d r

Summary Let X be an irreducible smooth projective curve of genus g. Let _d ^r (g) be the Brill-Noether Number. In this paper we prove some results concerning the schemes W _d ^r of special divisors. 1) Suppose dim (W _d–1 ^r )= _{d– 1} ^r (g)0 and _d ^r (g) < g. If W _{d– 1} ^r is a reduced (resp. irreducible) scheme, then W _d ^r is a reduced (resp. irreducible) scheme. 2) Under certain conditions, if Z is a generically reduced irreducible component of W _d–1 ^r then Z W ₁ ⁰ is a generically reduced irreducible component of W _d ^r . For r=1, we obtain some further results in this direction. 3) As an application of it we are able to prove some dimension theorems for the schemes W _d ¹ .     

Constraints on the degree of a sofic homomorphism and the induced multiplication of measures on unstable sets

Letf be an endomorphism of an irreducible sofic systemS, whereS has entropy log λ. Thedegree off is the numberd such thatf isd to 1 almost everywhere. Thend divides a power of the greatest common divisor of the nonleading coefficients of the minimal polynomial of λ. Also,f multiplies the natural measure on unstable sets of generic points by a positive unit of the ring generated by 1/λ and the algebraic integers ofQ[λ]. Related results hold for bounded to one homomorphisms of sofic systems.     

Continuity of the Visibility Function in the Boundary

The visibility function of a compact set SE ^d assigns to each xS the Lebesgue outer measure of its star in S. This function was introduced by G. Beer in 1972. In 1991, A. Forte Cunto characterized the points of discontinuity of the visibility function in the boundary of a planar Jordan domain. In a recent paper, the present authors extended this characterization to compact subsets of E ^d with certain topological restrictions. These restrictions are removed here and it is proved that the visibility function of a compact subset of E ^d is continuous at a point if and only if the set of restricted visibility of this point has null Lebesgue outer measure. Mathematics Subject Classifications (2000): Primary: 52A35, Secondary: 52A10. Key words: starshaped set, Beer's visibility function, point of restricted visibility.     

On the dimension of bivariate spline spaces of smoothnessr and degreed=3r+1

Summary We consider the well-known spaces of bivariate piecewise polynomials of degreed defined over arbitrary triangulations of a polygonal domain and possessingr continuous derivatives globally. To date, dimension formulae for such spaces have been established only whend3r+2, (except for the special case wherer=1 andd=4). In this paper we establish dimension formulae for allr1 andd=3r+1 for almost all triangulations.Dedicated to R. S. Varga on the occasion of his sixtieth birthdaySupported in part by National Science Foundation Grant DMS-8701121Supported in part by National Science Foundation Grant DMS-8602337     

Traversing a Set of Points with a Minimum Number of Turns

Given a finite set of points S in ℝ ^d , consider visiting the points in S with a polygonal path which makes a minimum number of turns, or equivalently, has the minimum number of segments (links). We call this minimization problem the minimum link spanning path problem. This natural problem has appeared several times in the literature under different variants. The simplest one is that in which the allowed paths are axis-aligned. Let L(S) be the minimum number of links of an axis-aligned path for S, and let G _n ^d be an n×…×n grid in ℤ ^d . Kranakis et al. (Ars Comb. 38:177–192, 1994) showed that L(G _n ²)=2n−1 and and conjectured that, for all d≥3, We prove the conjecture for d=3 by showing the lower bound for L(G _n ³). For d=4, we prove that For general d, we give new estimates on L(G _n ^d ) that are very close to the conjectured value. The new lower bound of improves previous result by Collins and Moret (Inf. Process. Lett. 68:317–319, 1998), while the new upper bound of differs from the conjectured value only in the lower order terms. For arbitrary point sets, we include an exact bound on the minimum number of links needed in an axis-aligned path traversing any planar n-point set. We obtain similar tight estimates (within 1) in any number of dimensions d. For the general problem of traversing an arbitrary set of points in ℝ ^d with an axis-aligned spanning path having a minimum number of links, we present a constant ratio (depending on the dimension d) approximation algorithm. Work by A. Dumitrescu was partially supported by NSF CAREER grant CCF-0444188. Work by F. Hurtado was partially supported by projects MECMTM2006-01267 and Gen. Cat. 2005SGR00692. Work by P. Valtr was partially supported by the project 1M0545 of the Ministry of Education of the Czech Republic.     

Weierstrass points and multiple intersection points of closed geodesics

We classify smooth complex projective surfaces of degreed and class , satisfying either (i) –d16, or (ii) 25. All these surfaces are rational or ruled. Indeed, we prove that the smallest value of the class of a non-ruled surface is 30 and in fact there are at least two surfacesS, both of degreed=10 and sectional genusg=6, with Kodaira dimension (S)=0 and class =30. Finally, we classify the smoothk-folds (k3) whose sectional surface has class 23.     

Hypersurface variations are maximal,I

Summary The variation of Hodge structure defined by the natural family of hypersurfaces of degreed and dimensionn is maximal if the cohomology has Hodge level >1. There is a small list of hypersurfaces of level one which give non-maximal variations: plane curves of degreed5, cubics of dimension 3 and 5, and quartic threefolds.Research partially supported by the National Science Foundation     

Windmill polynomials over fields of characteristic two

Chambers andSmeets [3] have designed a windmill arrangement of linear feedback shift registers (LFSRs) to generate pn-sequences overGF(2) with high speed. When the windmill hasv vanes, the associated minimal feedback polynomial (having degreen, relatively prime tov) can be taken to have the shapef ₁(x ^v )+x ⁿ f ₂(x ^–v ), where the polynomialsf ₁ andf ₂ have degree [n/v]. Their numerical evidence, whenv is divisible by 4, suggests that, surprisingly, there areno such windmill polynomials which are irreducible ifn±3 (mod 8), while about twice as many irreducible and primitive windmill polynomials as they expected occur ifn±1 (mod 8). A discussion of this behaviour is presented here with proofs. The brief explanation is that the Galois group of the underlying generic windmill polynomial overGF (4) is equal to the alternating groupA _n .     

Curves and 0-cycles on projective surfaces

LetC be a smooth curve with ag _n ¹ , i.e. a linear system of dimension 1 and degreen, lying on a smooth projective surfaceS. Let :S P ^N be the map associated to the line bundleK _S +[C] and letD be a general divisor of the given linear systemg _n ¹ . LetV be the linear space spanned by the image ofD through . We study the case in whichn:=dimV=1 and in general we discuss the case in whichn is small. The starting point is an analysis of the adjunction map using Bogomolov-Reider-Serrano techniques; several results from curve theory are also needed.     

Calculating cohomology groups of ℳ̄0,n (ℙ r ,d)

Here we investigate the rational cohomology of the moduli space ̄_0,n(^r,d) of degree d stable maps from n-pointed rational curves to ^r. We obtain partial results for small values of d with an inductive method inspired by a paper of Enrico Arbarello and Maurizio Cornalba.     

On the moduli of surfaces admitting genus two fibrations over elliptic curves

In this paper, we study the structure, deformations and the moduli spaces of complex projective surfaces admitting genus two fibrations over elliptic curves. We observe that a surface admitting a smooth fibration as above is elliptic, and we employ results on the moduli of polarized elliptic surfaces to construct moduli spaces of these smooth fibrations. In the case of nonsmooth fibrations, we relate the moduli spaces to the Hurwitz schemes of morphisms of degree n from elliptic curves to the modular curve X(d), d ≥ 3. Ultimately, we show that the moduli spaces in the nonsmooth case are fiber spaces over the affine line with fibers determined by the components of . Received: 30 August 2006