b-coloring of Kneser graphs

A $b$-coloring of a graph $G$ with $k$ colors is a proper coloring of $G$ using $k$ colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer $k$ for which $G$ has a $b$-coloring using $k$ colors is the $b$-chromatic number $b\left(G\right)$ of $G$. The $b$-spectrum $S_b\left(G\right)$ of a graph $G$ is the set of positive integers $k,\chi \left(G\right)\le k\le b\left(G\right)$, for which $G$ has a $b$-coloring using $k$ colors. A graph $G$ is $b$-continuous if $S_b\left(G\right)$ = the closed interval $[\chi \left(G\right),b\left(G\right)]$. In this paper, we obtain an upper bound for the $b$-chromatic number of some families of Kneser graphs. In addition we establish that $[\chi \left(G\right),n+k+1]?S_b\left(G\right)$ for the Kneser graph $G=K(2n+k,n)$ whenever $3\le n\le k+1$. We also establish the $b$-continuity of some families of regular graphs which include the family of odd graphs.     

Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

Parameters of connectivity in (a,b)-linear graphs

For some a and b positive rational numbers, a simple graph with n vertices and $m=an-b$ edges is an $(a,b)$-linear graph, when $n>2b$. We characterize non-empty classes of $(a,b)$-linear graphs and determine those which contain connected graphs. For non-empty classes, we build sequences of $(a,b)$-linear graphs and sequences of connected $(a,b)$-linear graphs. Furthermore, for each of these sequences where every graph is bounded by a constant, we show that its correspondent sequence of diameters diverges, while its correspondent sequence of algebraic connectivities converges to zero.     

A degree condition for a graph to have (a,b)-parity factors

Let $a$ and $b$ be two positive integers such that $a\le b$ and $a\equiv b(mod2)$. A graph $F$ is an $(a,b)$-parity factor of a graph $G$ if $F$ is a spanning subgraph of $G$ and for all vertices $v\in V\left(F\right)$, $d_F\left(v\right)\equiv b(mod2)$ and $a\le d_F\left(v\right)\le b$. In this paper we prove that every connected graph $G$ with $n\ge b(a+b)(a+b+2)∕\left(2a\right)$ vertices has an $(a,b)$-parity factor if $na$ is even, $\delta \left(G\right)\ge (b?a)∕a+a$, and for any two nonadjacent vertices $u,v\in V\left(G\right)$, $max\{d_G\left(u\right),d_G\left(v\right)\}\ge \frac{an}{a+b}$. This extends an earlier result of Nishimura (1992) and strengthens a result of Cai and Li (1998).     

Graph coloring and Graham’s greatest common divisor problem

In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer $k$ consider a graph $B_k$ whose vertex set is the set of all positive integers with two vertices $a,b$ joined by an edge whenever the two numbers $a∕gcd(a,b)$ and $b∕gcd(a,b)$ are both at most $k$. We conjecture that the chromatic number of every such graph $B_k$ is equal to $k$. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of $B_k$ is equal to $k$. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.     

Characterization of Lipschitz spaces via commutators of the Hardy–Littlewood maximal function

Let M be the Hardy–Littlewood maximal function and b be a locally integrable function. Denote by $M_b$ and $[b,M]$ the maximal commutator and the (nonlinear) commutator of M with b. In this paper, the author considers the boundedness of $M_b$ and $[b,M]$ on Lebesgue spaces and Morrey spaces when b belongs to the Lipschitz space, by which some new characterizations of the Lipschitz spaces are given.     

Generating regular elements

Let R be a prime right Goldie ring. A useful fact is that, if $a,b\in R$ are such that $aR+bR$ contains a regular element, then there exists $\lambda \in R$ such that $a+b\lambda$ is regular. We show that the analogous result holds for $n?1$ pairs of elements: if R contains a field of cardinality at least $n+1$, and if $a_i,b_i\in R$ are such that $a_{i}R+b_{i}R$ contains a regular element for $1?i?n$, then there exists a single element $\lambda \in R$ such that $a_i+b_i\lambda$ is regular for each i.     

Annihilator-stability and unique generation

A ring R is said to be left uniquely generated if $Ra=Rb$ in R implies that $a=ub$ for some unit u in R. These rings have been of interest since Kaplansky introduced them in 1949 in his classic study of elementary divisors. Writing $\mathtt{l}(b)=\{r\in R|rb=0\}$, a theorem of Canfell asserts that R is left uniquely generated if and only if, whenever $Ra+\mathtt{l}(b)=R$ where $a,b\in R$, then $a?u\in \mathtt{l}(b)$ for some unit u in R. By analogy with the stable range 1 condition we call a ring with this property left annihilator-stable. In this paper we exploit this perspective on the left UG rings to construct new examples and derive new results. For example, writing J for the Jacobson radical, we show that a semiregular ring R is left annihilator-stable if and only if $R/J$ is unit-regular, an analogue of Bass' theorem that semilocal rings have stable range 1.     

Classification of bm-Nambu structures of top degree

In this paper, we classify $b^m$-Nambu structures via $b^m$-cohomology. The complex of $b^m$-forms is an extension of the De Rham complex, which allows us to consider singular forms. $b^m$-Cohomology is well understood thanks to Scott (2016) [12], and it can be expressed in terms of the De Rham cohomology of the manifold and of the critical hypersurface using a Mazzeo–Melrose-type formula. Each of the terms in $b^m$-Mazzeo–Melrose formula acquires a geometrical interpretation in this classification. We also give equivariant versions of this classification scheme.     

The intermediate disorder regime for a directed polymer model on a hierarchical lattice

We study a directed polymer model defined on a hierarchical diamond lattice, where the lattice is constructed recursively through a recipe depending on a branching number $b\in \mathbb{N}$ and a segment number $s\in \mathbb{N}$. When $b\le s$ it is known that the model exhibits strong disorder for all positive values of the inverse temperature $\beta$, and thus weak disorder reigns only for $\beta =0$ (infinite temperature). Our focus is on the so-called intermediate disorder regime in which the inverse temperature $\beta \equiv {\beta }_n$ vanishes at an appropriate rate as the size $n$ of the system grows. Our analysis requires separate treatment for the cases $b<s$ and $b=s$. In the case $b<s$ we prove that when the inverse temperature is taken to be of the form ${\beta }_n=\stackrel{?}{\beta }{(b/s)}^{n/2}$ for $\stackrel{?}{\beta }>0$, the normalized partition function of the system converges weakly as $n\to \infty$ to a distribution $L\left(\stackrel{?}{\beta }\right)$ and does so universally with respect to the initial weight distribution. We prove the convergence using renormalization group type ideas rather than the standard Wiener chaos analysis. In the case $b=s$ we find a critical point in the behavior of the model when the inverse temperature is scaled as ${\beta }_n=\stackrel{?}{\beta }/n$; for an explicitly computable critical value ${\kappa }_b>0$ the variance of the normalized partition function converges to zero with large $n$ when $\stackrel{?}{\beta }\le {\kappa }_b$ and grows without bound when $\stackrel{?}{\beta }>{\kappa }_b$. Finally, we prove a central limit theorem for the normalized partition function when $\stackrel{?}{\beta }\le {\kappa }_b$.     

Stochastic Komatu–Loewner evolutions and BMD domain constant

For Komatu–Loewner equation on a standard slit domain, we randomize the Jordan arc in a manner similar to that of Schramm (2000) to find the SDEs satisfied by the induced motion $\xi \left(t\right)$ on $?\mathbb{H}$ and the slit motion $\mathbf{s}\left(t\right)$. The diffusion coefficient $\alpha$ and drift coefficient $b$ of such SDEs are homogeneous functions.Next with solutions of such SDEs, we study the corresponding stochastic Komatu–Loewner evolution, denoted as ${\mathrm{SKLE}}_{\alpha ,b}$. We introduce a function $b_{\mathrm{BMD}}$ measuring the discrepancy of a standard slit domain from $\mathbb{H}$ relative to BMD. We show that ${\mathrm{SKLE}}_{\sqrt{6},?b_{\mathrm{BMD}}}$ enjoys a locality property.     

Fractional parts of powers and Sturmian words

Let $b?2$ be an integer. In terms of combinatorics on words we describe all irrational numbers $\xi >0$ with the property that the fractional parts $\{\xi b^n\}$, $n?0$, all belong to a semi-open or an open interval of length $1/b$. The length of such an interval cannot be smaller, that is, for irrational ξ, the fractional parts $\{\xi b^n\}$, $n?0$, cannot all belong to an interval of length smaller than $1/b$. To cite this article: Y. Bugeaud, A. Dubickas, C. R. Acad. Sci. Paris, Ser. I 341 (2005).