A fast algorithm for equitable coloring

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemerédi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(rn ²) time, where n is the number of vertices.     

Bifurcation and Stability Analysis of the Equilibrium States in Thermodynamic Systems in a Small Vicinity of the Equilibrium Values of Parameters

The dynamic behavior of thermodynamic system, described by one order parameter and one control parameter, in a small neighborhood of ordinary and bifurcation equilibrium values of the system parameters is studied. Using the general methods of investigating the branching (bifurcations) of solutions for nonlinear equations, we performed an exhaustive analysis of the order parameter dependences on the control parameter in a small vicinity of the equilibrium values of parameters, including the stability analysis of the equilibrium states, and the asymptotic behavior of the order parameter dependences on the control parameter (bifurcation diagrams). The peculiarities of the transition to an unstable state of the system are discussed, and the estimates of the transition time to the unstable state in the neighborhood of ordinary and bifurcation equilibrium values of parameters are given. The influence of an external field on the dynamic behavior of thermodynamic system is analyzed, and the peculiarities of the system dynamic behavior are discussed near the ordinary and bifurcation equilibrium values of parameters in the presence of external field. The dynamic process of magnetization of a ferromagnet is discussed by using the general methods of bifurcation and stability analysis presented in the paper.     

Thermal transport in semiconductor nanostructures,graphene,and related two-dimensional materials

We review experimental and theoretical results on thermal transport in semiconductor nanostructures(multilayer thin films, core/shell and segmented nanowires), single-and few-layer graphene, hexagonal boron nitride, molybdenum disulfide, and black phosphorus. Different possibilities of phonon engineering for optimization of electrical and heat conductions are discussed. The role of the phonon energy spectra modification on the thermal conductivity in semiconductor nanostructures is revealed. The dependence of thermal conductivity in graphene and related two-dimensional(2 D) materials on temperature, flake size, defect concentration, edge roughness, and strain is analyzed.     

On neighborly families of convex bodies

A family of convex bodies in E^d is called neighborly if the intersection of every two of them is (d-1)-dimensional. In the present paper we prove that there is an infinite neighborly family of centrally symmetric convex bodies in E^d, d 3, such that every two of them are affinely equivalent (i.e., there is an affine transformation mapping one of them onto another), the bodies have large groups of affine automorphisms, and the volumes of the bodies are prescribed. We also prove that there is an infinite neighborly family of centrally symmetric convex bodies in E^d such that the bodies have large groups of symmetries. These two results are answers to a problem of B. Grünbaum (1963). We prove also that there exist arbitrarily large neighborly families of similar convex d-polytopes in E^d with prescribed diameters and with arbitrarily large groups of symmetries of the polytopes.     

Contribution to the nonlinear theory of sound and hydrodynamic turbulence of a compressible liquid

The interaction of sound with hydrodynamic turbulence has been studied in detail. The sound absorption decrement, the correlation time and length and the frequency diffusion coefficient for the acoustic wave packet are calculated. The spectral composition of the sound radiated by a unit, turbulent volume and the spectral energy density of sound in equilibrium with the turbulence are studied. The region of applicability of the kinetic equation for sound with a linear dispersion low is found.     

Structures and tautomeric interconversions of anthraquinone imine derivatives

Substituted 1-hydroxy-9,10-anthraquinone-9-imines have been found to exhibit tautomeric interconversions between the 9,10- and 1,10-quinonoid forms in the solid state as well as in solution. Single-crystal X-ray crystallography was used to study the structures of 4-(N-acetyl-p-tolylamino)-9-amino-1,10-anthracenedione and 4-hydroxy-1-phenylamino-10-mesitylimino-9(10H)-anthracenone at ambient and low temperatures. The former compound gave crystals belonging to the monoclinic space group P2_l/c and, at 295 K,a=9.684(2),b=16.371(3),c=12.097(2) å,=110.41(1), V=1797 å³,Z=4, R(F)=0.042, and GOF=0.863. The latter compound gave crystals belonging to the monoclinic space group C2/c and, at 295 K,a=38.158(8),b=6.322(2),c=19.325(4) å,=101.78(2),V=4564 å³,Z=8, R(F)=0.052, and GOF=0.981, while at 150 K,a=37.852(6),b=6.245(1),c=19.235(4) å,=102.81(1),V=4434 å³,R(F)=0.047, and GOF=1.006. Comparison of the geometric parameters of the two compounds illustrates the considerable zwitterionic nature of the first, a distinctive feature of which is a very short bond N(9)-C(9) whose length is essentially equal to that of a double bond. Molecular modeling studies using AMI semiempirical calculations were shown to be capable of satisfactorily reproducing the energetics of the tautomeric equilibrium once the medium effect was taken into account.     

CSP for binary conservative relational structures

We prove that whenever \({\mathbb {A}}\) is a 3-conservative relational structure with only binary and unary relations, then the algebra of polymorphisms of \({\mathbb {A}}\) either has no Taylor operation (i.e., CSP(\({\mathbb {A}}\)) is NP-complete), or it generates an SD(\({\wedge}\)) variety (i.e., CSP(\({\mathbb {A}}\)) has bounded width).     

Coloring,sparseness and girth

Using the classical analysis resolution of singularities algorithm of [G4], we generalize the theorems of [G3] on Rⁿ sublevel set volumes and oscillatory integrals with real phase function to functions over an arbitrary local field of characteristic zero. The p-adic cases of our results provide new estimates for exponential sums as well as new bounds on how often a function f(x), such as a polynomial with integer coefficients, is divisible by various powers of a prime p when x is an integer. Unlike many papers on such exponential sums and p-adic oscillatory integrals, we do not require the Newton polyhedron of the phase to be nondegenerate, but rather as in [G3] we have conditions on the maximum order of the zeroes of certain polynomials corresponding to the compact faces of this Newton polyhedron.     

Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .