Remarks on the Schoof-Elkies-Atkin algorithm

Schoof's algorithm computes the number of points on an elliptic curve defined over a finite field . Schoof determines modulo small primes using the characteristic equation of the Frobenius of and polynomials of degree . With the works of Elkies and Atkin, we have just to compute, when is a ``good" prime, an eigenvalue of the Frobenius using polynomials of degree . In this article, we compute the complexity of Müller's algorithm, which is the best known method for determining one eigenvalue and we improve the final step in some cases. Finally, when is ``bad", we describe how to have polynomials of small degree and how to perform computations, in Schoof's algorithm, on -values only.

     

Approximating the independence number via theϑ-function

We describe an approximation algorithm for the independence number of a graph. If a graph onn vertices has an independence numbern/k + m for some fixed integerk 3 and somem > 0, the algorithm finds, in random polynomial time, an independent set of size , improving the best known previous algorithm of Boppana and Halldorsson that finds an independent set of size (m ^1/(k–1)) in such a graph. The algorithm is based on semi-definite programming, some properties of the Lovász-function of a graph and the recent algorithm of Karger, Motwani and Sudan for approximating the chromatic number of a graph. If the-function of ann vertex graph is at leastMn ^1–2/k for some absolute constantM, we describe another, related, efficient algorithm that finds an independent set of sizek. Several examples show the limitations of the approach and the analysis together with some related arguments supply new results on the problem of estimating the largest possible ratio between the-function and the independence number of a graph onn vertices. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by a USA—Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences and by the Minkowski Minerva Center for Geometry at Tel Aviv University.This work was partly done while the author was at XEROX PARC and partly at DIMACS.     

Sommes D'Exponentielles et Entiers Sans Grand Facteur Premier

Let S(x,y) be the set S(x,y)= 1 n x : P(n) y, where P(n) denotesthe largest prime factor of n. We study , where f is a multiplicative function. When f=1and when f=µ, we widen the domain of uniform approximationusing the method of Fouvry and Tenenbaum and making explicitthe contribution of the Siegel zero. Soit S(x,y) l'ensemble S(x,y)= 1 n x : P(n) y, désigne le plus grand facteur premier den. Nous étudions , lorsque f est une fonction multiplicative. Quand f=1 et quand f=µ,nous élargissons le domaine d'approximation uniformeenutilisant la méthode développée par Fouvryet Tenenbaum et en explicitant la contribution du zérode Siegel. 1991 Mathematics Subject Classification: 11N25, 11N99.     

Some theta function identities related to the Rogers-Ramanujan continued fraction

In his first and second letters to Hardy, Ramanujan made several assertions about the Rogers-Ramanujan continued fraction . In order to prove some of these claims, G. N. Watson established two important theorems about that he found in Ramanujan's notebooks. In his lost notebook, after stating a version of the quintuple product identity, Ramanujan offers three theta function identities, two of which contain as special cases the celebrated two theorems of Ramanujan proved by Watson. Using addition formulas, the quintuple product identity, and a new general product formula for theta functions, we prove these three identities of Ramanujan from his lost notebooks.

     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m × n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of long but straight continuous parts while the remaining curved part is relatively “short”. R. D. C. Monteiro was supported in part by NSF Grants CCR-0203113 and CCF-0430644 and ONR grant N00014-05-1-0183. T. Tsuchiya was supported in part by Japan-US Joint Research Projects of Japan Society for the Promotion of Science “Algorithms for linear programs over symmetric cones” and the Grants-in-Aid for Scientific Research (C) 15510144 of Japan Society for the Promotion of Science.     

Covering the alternating groups by products of cycle classes

Given integers k,l?2, where either l is odd or k is even, we denote by n=n(k,l) the largest integer such that each element of An is a product of k cycles of length l. For an odd l, k is the diameter of the undirected Cayley graph Cay(An,Cl), where Cl is the set of all l-cycles in An. We prove that if k?2 and l?9 is odd and divisible by 3, then . This extends earlier results by Bertram [E. Bertram, Even permutations as a product of two conjugate cycles, J. Combin. Theory 12 (1972) 368-380] and Bertram and Herzog [E. Bertram, M. Herzog, Powers of cycle-classes in symmetric groups, J. Combin. Theory Ser. A 94 (2001) 87-99].     

Local boundedness of the number of solutions of Plateau’s problem for polygonal boundary curves

In the present article, the author proves two generalizations of his “finiteness-result” (I.H.P. Anal. Non-lineaire, 2006, accepted) which states for any extreme simple closed polygon that every immersed, stable disc-type minimal surface spanning Γ is an isolated point of the set of all disc-type minimal surfaces spanning Γ w.r.t. the C ⁰-topology. First, it is proved that this statement holds true for any simple closed polygon in , provided it bounds only minimal surfaces without boundary branch points. Also requiring that the interior angles at the vertices of such a polygon Γ have to be different from the author proves the existence of some neighborhood O of Γ in and of some integer , depending only on Γ, such that the number of immersed, stable disc-type minimal surfaces spanning any simple closed polygon contained in O, with the same number of vertices as Γ, is bounded by .      

List colorings with measurable sets

The measurable list chromatic number of a graph G is the smallest number ξ such that if each vertex v of G is assigned a set L(v) of measure ξ in a fixed atomless measure space, then there exist sets such that each c(v) has measure one and for every pair of adjacent vertices v and v'. We provide a simpler proof of a measurable generalization of Hall's theorem due to Hilton and Johnson [J Graph Theory 54 (2007), 179–193] and show that the measurable list chromatic number of a finite graph G is equal to its fractional chromatic number. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 229–238, 2008