Search

Hoffman's bound is a well-known spectral bound on the chromatic number of a graph, known to be tight for instance for bipartite graphs. While Hoffman colorings (colorings attaining the bound) were studied before for regular graphs, for irregular graphs not much is known. We investigate tightness of the Hoffman bound, with a particular focus on irregular graphs, obtaining several results on the graph structure of Hoffman colorings. In particular, we study the connection between Hoffman colorability and graph tensor products, and as a byproduct, we obtain constructions of infinite families of irregular Hoffman colorable graphs. Moreover, we present a Decomposition Theorem, which describes the structure of Hoffman colorings, and we use it to completely classify Hoffman colorability of cone graphs and line graphs. We also prove a partial converse, the Composition Theorem, leading to various new constructions of Hoffman colorable graphs and to an algorithm for computing all connected Hoffman colorable graphs for some given number of vertices and colors. Since several graph coloring parameters are known to be sandwiched between the Hoffman bound and the chromatic number, as a byproduct of our results on Hoffman colorability, we obtain the values of such chromatic parameters., Comment: v1: Master Thesis in Mathematics of the third author, supervised by first two authors v2: Article, consisting of parts of the thesis (v1)

We prove that five ways to define entry A086377 in the On-Line Encyclopedia of Integer Sequences do lead to the same integer sequence.

We describe the results of the computation of aliquot sequences with small starting values. In particular all sequences with starting values less than a million have been computed until either termination occurred (at 1 or a cycle), or an entry of 100 decimal digits was encountered. All dependencies were recorded, and numerous statistics, curiosities, and records are reported., Comment: 18 pages, numerous figures

Suppose that $a$ and $b$ are multiplicatively independent Gaussian integers, that are both of modulus~$\geq \sqrt 5$. We prove that there exist a $X\subset \mathbb Z[i]$ which is $a$-automatic but not $b$-automatic. This settles a problem of Allouche, Cateland, Gilbert, Peitgen, Shallit, and Skordev.

We give an algorithm that finds a sequence of approximations with Dirichlet coefficients bounded by a constant only depending on the dimension. The algorithm uses the LLL-algorithm for lattice basis reduction. We present a version of the algorithm that runs in polynomial time of the input., Comment: 16 pages, 7 figures

The average value of log s(n)/n taken over the first N even integers is shown to converge to a constant lambda when N tends to infinity; moreover, the value of this constant is approximated and proven to be less than 0. Here s(n) sums the divisors of n less than n. Thus the geometric mean of s(n)/n, the growth factor of the function s, in the long run tends to be less than 1. This could be interpreted as probabilistic evidence that aliquot sequences tend to remain bounded., Comment: 16 pages

We investigate here the representability of integers as sums of triangular numbers, where the $n$-th triangular number is given by $T_n = n(n + 1)/2$. In particular, we show that $f(x_1,x_2,..., x_k) = b_1 T_{x_1} +...+ b_k T_{x_k}$, for fixed positive integers $b_1, b_2,..., b_k$, represents every nonnegative integer if and only if it represents 1, 2, 4, 5, and 8. Moreover, if `cross-terms' are allowed in $f$, we show that no finite set of positive integers can play an analogous role, in turn showing that there is no overarching finiteness theorem which generalizes the statement from positive definite quadratic forms to totally positive quadratic polynomials.

Expansions that furnish increasingly good approximations to real numbers are usually related to dynamical systems. Although comparing dynamical systems seems difficult in general, Lochs was able in 1964 to relate the relative speed of approximation of decimal and regular continued fraction expansions (almost everywhere) to the quotient of the entropies of their dynamical systems. He used detailed knowledge of the continued fraction operator. In 2001, a generalization of Lochs' result was given by Dajani and Fieldsteel in \citeDajF, describing the rate at which the digits of one number-theoretic expansion determine those of another. Their proofs are based on covering arguments and not on the dynamics of specific maps. In this paper we give a dynamical proof for certain classes of transformations, and we describe explicitly the distribution of the number of digits determined when comparing two expansions in integer bases. Finally, using this generalization of Lochs' result, we estimate the unknown entropy of certain number theoretic expansions by comparing the speed of convergence with that of an expansion with known entropy., Comment: Published at http://dx.doi.org/10.1214/074921706000000202 in the IMS Lecture Notes--Monograph Series (http://www.imstat.org/publications/lecnotes.htm) by the Institute of Mathematical Statistics (http://www.imstat.org)