An Analogue of Gromov’s Waist Theorem for Coloring the Cube

It is proved that if we partition a d-dimensional cube into \(n^d\) small cubes and color the small cubes in \(m+1\) colors then there exists a monochromatic connected component consisting of at least \(f(d, m) n^{d-m}\) small cubes. Another proof of this result is given in Matdinov’s preprint (Size of components of a cube coloring, arXiv:1111.3911, 2011)     

An Analogue of Beurling’s Theorem for NA Groups

In this paper, we prove Beurling’s theorem for NA groups, from which we derive some other versions of uncertainty principles.     

An Analogue of Bochner’s Theorem for Damek-Ricci Spaces

We characterize the image of radial positive measures θ’s on a harmonic NA group S which satisfies ∫ _S ? ₀(x)?dθ(x)<∞ under the spherical transform, where ? ₀ is the elementary spherical function.     

On the Crossing Number of Circular Graphs

1.IntroductionInVLSIchipdesign,thetwo-layerroutingofgraphGplayanimportantrole.Thatis,theupperlayercanonlybeusedforverticalwiringandthesecondlaer,theloweroneonlyforhorizontalwiring.Soweconsidertheplanarprojectionofth.etwolayers,i.e.,consideratwodimensionalgridasapropergraphmodel.ThenoneobviousconditiontoberequiredisthateveryvertexofGhasitsdegreeatmost4.Withoutlossofgeneralitylweonlyconsider4regUlargraphs.IfGisaplanargraphwitha(G)S4,alinearalgorithmhadbeenprovidedforfindingarectilineajrrout…     

Total Chromatic Number of the Join of K_(m,n) and C_n

The total chromatic number XT(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if XT(G)=Δ(G) 1. In this paper we prove that the join of a complete bipartite graph Km,n and a cycle Cn is of Type 1.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

Nordhaus–Gaddum-Type Theorem for Rainbow Connection Number of Graphs

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc(G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus–Gaddum-type result for the rainbow connection number. We prove that if G and ${\overline{G}}$ are both connected, then ${4\leq rc(G)+rc(\overline{G})\leq n+2}$ . Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively.     

An Analogue of Nakayama’s Conjecture for Johnson Schemes

Nakayamas Conjecture is one of the most famous theorems for representation theory of symmetric groups. Two general irreducible characters of a symmetric group belong to the same p-block if and only if the p-cores of the young diagrams corresponding to them are the same. The conjecture was first proven in 1947 by Brauer and Robinson. We consider an analogue of Nakayamas Conjecture for Johnson schemes.Received January 28, 2004     

An Analog of Titchmarsh’s Theorem for the Fourier–Walsh Transform

The space clos(X) of all nonempty closed subsets of an unbounded metric space X is considered. The space clos(X) is endowed with a metric in which a sequence of closed sets converges if and only if the distances from these sets to a fixed point θ are bounded and, for any r, the sequence of the unions of the given sets with the exterior balls of radius r centered at θ converges in the Hausdorff metric. The metric on clos(X) thus defined is not equivalent to the Hausdorff metric, whatever the initial metric space X. Conditions for a set to be closed, totally bounded, or compact in clos(X) are obtained; criteria for the bounded compactness and separability of clos(X) are given. The space of continuous maps from a compact space to clos(X) is considered; conditions for a set to be totally bounded in this space are found.     

An Algebraic Version of the Cantor-Bernstein-Schröder Theorem

The Cantor-Bernstein-Schröder theorem of the set theory was generalized by Sikorski and Tarski to -complete boolean algebras, and recently by several authors to other algebraic structures. In this paper we expose an abstract version which is applicable to algebras with an underlying lattice structure and such that the central elements of this lattice determine a direct decomposition of the algebra. Necessary and sufficient conditions for the validity of the Cantor-Bernstein-Schröder theorem for these algebras are given. These results are applied to obtain versions of the Cantor-Bernstein-Schröder theorem for -complete orthomodular lattices, Stone algebras, BL-algebras, MV-algebras, pseudo MV-algebras, ukasiewicz and Post algebras of order n.     

An Equivariant Analog of the Poincaré―Hopf Theorem

A new method for localization of algebro-topological invariants of smooth manifolds via equivariant tangent vector fields is presented. Main realizations of direct image constructions (the Gysin map and the BeckerGottlieb transfer map) are calculated for Grassmannizations of complex vector bundles and for a complex-oriented cohomology theory. Bibliography: 12 titles.     

An All-Unbounded-Operator Version of the Fuglede–Putnam Theorem

We present in this paper a new version of the famous Fuglede?CPutnam theorem where all the operators involved are unbounded.     

An Analog of the Brown–Schreiber–Taylor Theorem for Weighted Hyperbolic Shifts

In the present paper, using a development of the technique of transmutation mappings, we obtain the first weighted analog of the well-known Brown–Schreiber–Taylor theorem on the eigenvalues of the Laplacian for corresponding spaces of continuous functio     

An analogue of Edmonds’ Branching Theorem for infinite digraphs

We extend Edmonds’ Branching Theorem to locally finite infinite digraphs. As examples of Oxley or Aharoni and Thomassen show, this cannot be done using ordinary arborescences, whose underlying graphs are trees. Instead we introduce the notion of pseudo-arborescences and prove a corresponding packing result. Finally, we verify some tree-like properties for these objects, but give also an example that their underlying graphs do in general not correspond to topological trees in the Freudenthal compactification of the underlying multigraph of the digraph.     

An Analog of the Cameron--Johnson Theorem for Linear ℂ-Analytic Equations in Hilbert Space

The well-known Cameron--Johnson theorem asserts that the equation $\dot x = \mathcal{A}\left( t \right)x$ with a recurrent (Bohr almost periodic) matrix $\mathcal{A}\left( t \right)$ can be reduced by a Lyapunov transformation to the equation $\dot y = \mathcal{B}\left( t \right)y$ with a skew-symmetric matrix $\mathcal{B}\left( t \right)$ , provided that all solutions of the equation $\dot x = \mathcal{A}\left( t \right)x$ and of all its limit equations are bounded on the whole line. In the note, a generalization of this result to linear $\mathbb{C}$ -analytic equations in a Hilbert space is presented.     

An Analogue of Beurling–Hörmander’s Theorem Associated with Partial Differential Operators

In this paper for a positive real number α we consider two partial differential operators D and D_α on the half–plane We define a generalized Fourier transform associated with the operators D and D_α. We establish an analogue of Beurling–H?rmander’s Theorem for this transform and we give some applications of this theorem.     

An Elementary Proof of the Fundamental Theorem of Projective Geometry (Dedicated to Alfred Frölicher)

The following version of the fundamental theorem is proved: Let V, W be vector spaces and g: P(V)\E P(W) a morphism between the associated projective spaces. If the image of g is not contained in a line, then there exists a semilinear map f: V W which induces g. The difficulty lies in the fact that the homomorphism of division rings associated to the map f can be nonsurjective. As an application, a short proof of Wigner's theorem is also proposed.