An Algebraic Formulation of the Graph Reconstruction Conjecture

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck—the collection of its vertex‐deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph G and any finite sequence of graphs, it gives a linear constraint that every reconstruction of G must satisfy. Let be the number of distinct (mutually nonisomorphic) graphs on n vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for n‐vertex graphs if and only if . We give a framework based on Kocay's lemma to study this discrepancy. We prove that if M is a matrix of covering numbers of graphs by sequences of graphs, then . In particular, all n‐vertex graphs are reconstructible if one such matrix has rank . To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix M of covering numbers satisfies .     

On two conjectures for M&m sequences

In this paper, the recently introduced M&m sequences and associated mean-median map are studied. These sequences are built by adding new points to a set of real numbers by balancing the mean of the new set with the median of the original. This process, although seemingly simple, gives rise to complicated dynamics. The main result is that two conjectures put forward by Chamberland and Martelli are shown to be true for a subset of possible starting conditions.     

Planar Triangulations with Real Chromatic Roots Arbitrarily Close to 4

We exhibit infinite families of planar triangulations with real chromatic roots arbitrarily close to 4, thus resolving a long-standing conjecture in the affirmative. Received November 12, 2005     

On the Ramsey Number of Sparse 3-Graphs

We consider a hypergraph generalization of a conjecture of Burr and Erd?s concerning the Ramsey number of graphs with bounded degree. It was shown by Chvátal, Rödl, Trotter, and Szemerédi [The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), no. 3, 239–243] that the Ramsey number R(G) of a graph G of bounded maximum degree is linear in |V(G)|. We derive the analogous result for 3-uniform hypergraphs.     

Primitive roots in quadratic fields, II

We consider an analogue of Artin's primitive root conjecture for algebraic numbers which are not units in quadratic fields. Given such an algebraic number α, for a rational prime p which is inert in the field, the maximal possible order of α modulo (p) is p²−1. An extension of Artin's conjecture is that there are infinitely many such inert primes for which this order is maximal. We show that for any choice of 113 algebraic numbers satisfying a certain simple restriction, at least one of the algebraic numbers has order at least for infinitely many inert primes p.     

Small deviations, JIT sequencing and symmetric case of Fraenkel's conjecture

We prove Fraenkel's conjecture for the special case of symmetric words, and show that this proof implies the conjecture of Brauner and Crama [Facts and questions about the maximum deviation just-in-time scheduling problem, Discrete Appl. Math. 134 (2004) 25-50] concerning instances of the just-in-time sequencing problem with maximum deviation .     

The Milnor–Chow homomorphism revisited

The aim of this note is to give a simplified proof of the surjectivity of the natural Milnor–Chow homomorphism between Milnor K-theory and higher Chow groups for essentially smooth (semi-)local k-algebras A with infinite residue fields. It implies the exactness of the Gersten resolution for Milnor K-theory at the generic point. Our method uses the Bloch–Levine moving technique and some properties of the Milnor K-theory norm for fields. Furthermore we give new applications. Supported by Studienstiftung des deutschen Volkes and Deutsche Forschungsgemeinschaft.     

流形及其附加结构

从附加结构的角度将流形的多种概念有机地串联起来,并给出了一种直观理解流形、微分流形等抽象概念的新颖方式.同时,本文阐述了微分几何的主要特点、思想,介绍了与附加结构相关的流形分类问题、Poincare猜测等的研究情况.     

A note on the strength and minimum color sum of bipartite graphs

The strength of a graph G is the smallest integer s such that there exists a minimum sum coloring of G using integers {1,…,s}, only. For bipartite graphs of maximum degree Δ we show the following simple bound: s≤⌈Δ/2⌉+1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree Δ≤4.     

Restricted set addition: The exceptional case of the Erd?s-Heilbronn conjecture

Let A≠B be nonempty subsets of the group of integers modulo a prime p. If p?|A|+|B|−2, then at least |A|+|B|−2 different residue classes can be represented as a+b, where a∈A, b∈B and a≠b. This result complements the solution of a problem of Erd?s and Heilbronn obtained by Alon, Nathanson, and Ruzsa.