The parallelized Pollard kangaroo method in real quadratic function fields

We show how to use the parallelized kangaroo method for computing invariants in real quadratic function fields. Specifically, we show how to apply the kangaroo method to the infrastructure in these fields. We also show how to speed up the computation by using heuristics on the distribution of the divisor class number, and by using the relatively inexpensive baby steps in the real quadratic model of a hyperelliptic function field. Furthermore, we provide examples for regulators and class numbers of hyperelliptic function fields of genus that are larger than those ever reported before.

     

New heuristics for the vertex coloring problem based on semidefinite programming

The Lovász theta number Lovász (IEEE Trans Inf Theory 25:1–7, 1979) is a well-known lower bound on the chromatic number of a graph \(G\), and \(\varPsi _K(G)\) is its impressive strengthening Gvozdenovi? and Laurent (SIAM J Optim 19(2):592–615, 2008). The bound \(\varPsi _K(G)\) was introduced in very specific and abstract setting which is tough to translate into usual mathematical programming framework. In the first part of this paper we unify the motivations and approaches to both bounds and rewrite them in a very similar settings which are easy to understand and straightforward to implement. In the second part of the paper we provide explanations how to solve efficiently the resulting semidefinite programs and how to use optimal solutions to get good coloring heuristics. We propose two vertex coloring heuristics based on \(\varPsi _K(G)\) and present numerical results on medium sized graphs.     

Sieving for rational points on hyperelliptic curves

We give a new and efficient method of sieving for rational points on hyperelliptic curves. This method is often successful in proving that a given hyperelliptic curve, suspected to have no rational points, does in fact have no rational points; we have often found this to be the case even when our curve has points over all localizations . We illustrate the practicality of the method with some examples of hyperelliptic curves of genus .

     

Extremes of the internal energy of the Potts model on cubic graphs

We prove tight upper and lower bounds on the internal energy per particle (expected number of monochromatic edges per vertex) in the anti‐ferromagnetic Potts model on cubic graphs at every temperature and for all . This immediately implies corresponding tight bounds on the anti‐ferromagnetic Potts partition function. Taking the zero‐temperature limit gives new results in extremal combinatorics: the number of q‐colorings of a 3‐regular graph, for any , is maximized by a union of 's. This proves the d = 3 case of a conjecture of Galvin and Tetali.     

Integral points on elliptic curves and -torsion in class groups

We give new bounds for the number of integral points on elliptic curves. The method may be said to interpolate between approaches via diophantine techniques and methods based on quasi-orthogonality in the Mordell-Weil lattice. We apply our results to break previous bounds on the number of elliptic curves of given conductor and the size of the -torsion part of the class group of a quadratic field. The same ideas can be used to count rational points on curves of higher genus.

     

Towers of 2-covers of hyperelliptic curves

In this article, we give a way of constructing an unramified Galois-cover of a hyperelliptic curve. The geometric Galois-group is an elementary abelian -group. The construction does not make use of the embedding of the curve in its Jacobian, and it readily displays all subcovers. We show that the cover we construct is isomorphic to the pullback along the multiplication-by- map of an embedding of the curve in its Jacobian.

We show that the constructed cover has an abundance of elliptic and hyperelliptic subcovers. This makes this cover especially suited for covering techniques employed for determining the rational points on curves. In particular the hyperelliptic subcovers give a chance for applying the method iteratively, thus creating towers of elementary abelian 2-covers of hyperelliptic curves.

As an application, we determine the rational points on the genus curve arising from the question of whether the sum of the first fourth powers can ever be a square. For this curve, a simple covering step fails, but a second step succeeds.

     

On Graph-Lagrangians of Hypergraphs Containing Dense Subgraphs

Motzkin and Straus established a remarkable connection between the maximum clique and the Graph-Lagrangian of a graph in (Can. J. Math. 17:533–540, 1965). This connection and its extensions were successfully employed in optimization to provide heuristics for the maximum clique number in graphs. It is useful in practice if similar results hold for hypergraphs. In this paper, we provide upper bounds on the Graph-Lagrangian of a hypergraph containing dense subgraphs when the number of edges of the hypergraph is in certain ranges. These results support a pair of conjectures introduced by Peng and Zhao (Graphs Comb. 29:681–694, 2013) and extend a result of Talbot (Comb. Probab. Comput. 11:199–216, 2002).     

Construction of hyperelliptic function fields of high three-rank

We present several explicit constructions of hyperelliptic function fields whose Jacobian or ideal class group has large -rank. Our focus is on finding examples for which the genus and the base field are as small as possible. Most of our methods are adapted from analogous techniques used for generating quadratic number fields whose ideal class groups have high -rank, but one method, applicable to finding large -ranks for odd primes is new and unique to function fields. Algorithms, examples, and numerical data are included.

     

Groups of <Emphasis Type="Italic">S</Emphasis>-Units and the Problem of Periodicity of Continued Fractions in Hyperelliptic Fields

We construct a theory of periodic and quasiperiodic functional continued fractions in the field k((h)) for a linear polynomial h and in hyperelliptic fields. In addition, we establish a relationship between continued fractions in hyperelliptic fields, torsion in the Jacobians of the corresponding hyperelliptic curves, and S-units for appropriate sets S. We prove the periodicity of quasiperiodic elements of the form \(\sqrt f /d{h^s}\), where s is an integer, the polynomial f defines a hyperelliptic field, and the polynomial d is a divisor of f; such elements are important from the viewpoint of the torsion and periodicity problems. In particular, we show that the quasiperiodic element \(\sqrt f \) is periodic. We also analyze the continued fraction expansion of the key element \(\sqrt f /{h^{g + 1}}\), which defines the set of quasiperiodic elements of a hyperelliptic field.     

Matchings and independent sets of a fixed size in regular graphs

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size ℓ in the graph consisting of disjoint copies of K_d,d. This provides asymptotic evidence for a conjecture of S. Friedland et al. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.     

Irregular Gabor frames and their stability

In this paper we give sufficient conditions for irregular Gabor systems to be frames. We show that for a large class of window functions, every relatively uniformly discrete sequence in with sufficiently high density will generate a Gabor frame. Explicit frame bounds are given. We also study the stability of irregular Gabor frames and show that every Gabor frame with arbitrary time-frequency parameters is stable if the window function is nice enough. Explicit stability bounds are given.

     

Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems

Lagrangian relaxation is a powerful bounding technique that has been applied successfully to manyNP-hard combinatorial optimization problems. The basic idea is to see anNP-hard problem as an easy-to-solve problem complicated by a number of nasty side constraints. We show that reformulating nasty inequality constraints as equalities by using slack variables leads to stronger lower bounds. The trick is widely applicable, but we focus on a broad class of machine scheduling problems for which it is particularly useful. We provide promising computational results for three problems belonging to this class for which Lagrangian bounds have appeared in the literature: the single-machine problem of minimizing total weighted completion time subject to precedence constraints, the two-machine flow-shop problem of minimizing total completion time, and the single-machine problem of minimizing total weighted tardiness.     

Modular equations for hyperelliptic curves

We define modular equations describing the -torsion subgroups of the Jacobian of a hyperelliptic curve. Over a finite base field, we prove factorization properties that extend the well-known results used in Atkin's improvement of Schoof's genus 1 point counting algorithm.

     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

The concept of hyperellipticity on surfaces with nodes

A surface with nodes X is hyperelliptic if there exists an involution such that the genus of X/〈h〉 is 0. We prove that this definition is equivalent, as in the category of surfaces without nodes, to the existence of a degree 2 morphism satisfying an additional condition where the genus of Y is 0. Other question is if the hyperelliptic involution is unique or not. We shall prove that the hyperelliptic involution is unique in the case of stable Riemann surfaces but is not unique in the case of Klein surfaces with nodes. Finally, we shall prove that a complex double of a hyperelliptic Klein surface with nodes could not be hyperelliptic.     

Improving degree-based variable ordering heuristics for solving constraint satisfaction problems

In this paper, we improved two classical degree-based variable ordering heuristics, \(\frac{\textit{Dom}}{\textit{Ddeg}}\) and \(\frac{\textit{Dom}}{\textit{Wdeg}}\). We propose a method using the summation of constraint tightness in degree-based heuristics. We also propose two methods to calculate dynamic constraint tightness for binary extensional constraints and non-binary intensional constraints respectively. Our work shows how constraint tightness can be practically used to guide search. We performed a number of experiments on some benchmark instances. The results have shown that, the new heuristics improve the classical ones by both computational time and search tree nodes and they are more efficient than some other successful heuristics on the instances where the classical heuristics work well.     

Geometric Properties of W-Algebras and the Toda model

The W-algebra minimal models on hyperelliptic Riemann surfaces are constructed. Using a proposal by Polyakov, we reduce the partition function of the Toda field theory on the hyperelliptic surface to a product of partition functions: one of a free field theory on the sphere with inserted Toda vertex operators and one of a free scalar field theory with antiperiodic boundary conditions with inserted twist fields.     

The p-rank strata of the moduli space of hyperelliptic curves

We prove results about the intersection of the p-rank strata and the boundary of the moduli space of hyperelliptic curves in characteristic p?3. This yields a strong technique that allows us to analyze the stratum of hyperelliptic curves of genus g and p-rank f. Using this, we prove that the endomorphism ring of the Jacobian of a generic hyperelliptic curve of genus g and p-rank f is isomorphic to Z if g?4. Furthermore, we prove that the Z/?-monodromy of every irreducible component of is the symplectic group Sp2g(Z/?) if g?3, and ?≠p is an odd prime (with mild hypotheses on ? when f=0). These results yield numerous applications about the generic behavior of hyperelliptic curves of given genus and p-rank over finite fields, including applications about Newton polygons, absolutely simple Jacobians, class groups and zeta functions.     

Remarks on the minus (signed) total domination in graphs

A function f:V(G)→{+1,0,-1} defined on the vertices of a graph G is a minus total dominating function if the sum of its function values over any open neighborhood is at least 1. The minus total domination number of G is the minimum weight of a minus total dominating function on G. By simply changing “{+1,0,-1}” in the above definition to “{+1,-1}”, we can define the signed total dominating function and the signed total domination number of G. In this paper we present a sharp lower bound on the signed total domination number for a k-partite graph, which results in a short proof of a result due to Kang et al. on the minus total domination number for a k-partite graph. We also give sharp lower bounds on and for triangle-free graphs and characterize the extremal graphs achieving these bounds.     

The Geometry of Two Generator Groups: Hyperelliptic Handlebodies

A Kleinian group naturally stabilizes certain subdomains and closed subsets of the closure of hyperbolic three space and yields a number of different quotient surfaces and manifolds. Some of these quotients have conformal structures and others hyperbolic structures. For two generator free Fuchsian groups, the quotient three manifold is a genus two solid handlebody and its boundary is a hyperelliptic Riemann surface. The convex core is also a hyperelliptic Riemann surface. We find the Weierstrass points of both of these surfaces. We then generalize the notion of a hyperelliptic Riemann surface to a hyperelliptic three manifold. We show that the handlebody has a unique order two isometry fixing six unique geodesic line segments, which we call the Weierstrass lines of the handlebody. The Weierstrass lines are, of course, the analogue of the Weierstrass points on the boundary surface. Further, we show that the manifold is foliated by surfaces equidistant from the convex core, each fixed by the isometry of order two. The restriction of this involution to the equidistant surface fixes six generalized Weierstrass points on the surface. In addition, on each of these equidistant surfaces we find an orientation reversing involution that fixes curves through the generalized Weierstrass points.Mathematics Subject Classifications (2000). primary 30F10, 30F35, 30F40; secondary 14H30, 22E40.