The Relation Between k-Circularity and Circularity of Codes.

A code X is k-circular if any concatenation of at most k words from X, when read on a circle, admits exactly one partition into words from X. It is circular if it is k-circular for every integer k. While it is not a priori clear from the definition, there exists, for every pair [Formula: see text], an integer k such that every k-circular [Formula: see text]-letter code over an alphabet of cardinality n is circular, and we determine the least such integer k for all values of n and [Formula: see text]. The k-circular codes may represent an important evolutionary step between the circular codes, such as the comma-free codes, and the genetic code.

Coloring triangle-free graphs with local list sizes.

We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring. Our proof of the second illustrates the use of the hard-core model to prove a Johansson-type result, which may be of independent interest.

Occupancy fraction, fractional colouring, and triangle fraction.

Given ε > 0 , there exists f 0 such that, if f 0 ≤ f ≤ Δ 2 + 1 , then for any graph G on n vertices of maximum degree Δ in which the neighbourhood of every vertex in G spans at most Δ 2 ∕ f edges, (i)an independent set of G drawn uniformly at random has at least ( 1 ∕ 2 - ε ) ( n ∕ Δ ) log f vertices in expectation, and(ii)the fractional chromatic number of G is at most ( 2 + ε ) Δ ∕ log f . These bounds cannot in general be improved by more than a factor 2 asymptotically. One may view these as stronger versions of results of Ajtai, Komlós and Szemerédi and Shearer. The proofs use a tight analysis of the hard-core model.

Mixed circular codes.

By an extensive statistical analysis in genes of bacteria, archaea, eukaryotes, plasmids and viruses, a maximal C3-self-complementary trinucleotide circular code has been found to have the highest average occurrence in the reading frame of the ribosome during translation. Circular codes may play an important role in maintaining the correct reading frame. On the other hand, as several evolutionary theories propose primeval codes based on dinucleotides, trinucleotides and tetranucleotides, mixed circular codes were investigated. By using a graph-theoretical approach of circular codes recently developed, we study mixed circular codes, which are the union of a dinucleotide circular code, a trinucleotide circular code and a tetranucleotide circular code. Maximal mixed circular codes of (di,tri)-nucleotides, (tri,tetra)-nucleotides and (di,tri,tetra)-nucleotides are constructed, respectively. In particular, we show that any maximal dinucleotide circular code of size 6 can be embedded into a maximal mixed (di,tri)-nucleotide circular code such that its trinucleotide component is a maximal C3-comma-free code. The growth function of self-complementary mixed circular codes of dinucleotides and trinucleotides is given. Self-complementary mixed circular codes could have been involved in primitive genetic processes.