Enumeration of rectangular arrays of zeros and ones

For r=1,2 the rectangular arrays of zeros and ones with r rows and n columns, with m_i zeros and r_i changes in the ith row, and with s_i vertical changes between the ith and (i+1)st rows, i=1,…,r-1, are enumerated. The number of arrays of zeros and ones with 3 rows and n columns, with r_i changes in the ith row, i=1,2,3, and with s_i vertical changes between the ith and (i+1)st rows, i=1,2, is also determined.     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Pointwise bornological spaces

With each metric space (X,d) we can associate a bornological space (X,Bd) where Bd is the set of all subsets of X with finite diameter. Equivalently, Bd is the set of all subsets of X that are contained in a ball with finite radius. If the metric d can attain the value infinite, then the set of all subsets with finite diameter is no longer a bornology. Moreover, if d is no longer symmetric, then the set of subsets with finite diameter does not coincide with the set of subsets that are contained in a ball with finite radius. In this text we will introduce two structures that capture the concept of boundedness in both symmetric and non-symmetric extended metric spaces.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

On the m-capacitated peripatetic salesman problem with capacity restrictions

We consider a special case of the problem of finding m Hamiltonian cycles with capacity restrictions on the number of usages of the edges (m-Capacitated Peripatetic Salesman Problem or m-CPSP): the minimization and maximization 2-CPSP with edge weights chosen from an integer segment {1, q} with the edges capacities given as independent identically distributed random variables equal to 2 with probability p and 1 with probability (1 ? p). Some polynomial algorithms are proposed for 2-CPSP_min and 2-CPSP_max with average performance guarantees. In particular, when the edge weights are equal to 1 and 2, the algorithms have approximation ratios (19 ? 5p)/12 and (25 + 7p)/36 for the minimization and the maximization problem correspondingly.     

Flows satisfying mixed no-slip and no-shear conditions

Summary Solutions are presented which describe eight viscous flows satisfying mixed no-slip and no-shear conditions: 1. shear flow over a plate with a longitudinal no-shear slot; 2, shear flow over a plate with a regular array of such stots; 3. flow in a circular tube with one or more such slots; 4. flows between two parallel plates with a longitudinal no-shear slot in one of them; 5. flows between two parallel plates with a regular array of such slots in one of them; 6. shear Stokes flow over a plate with a transverse no-shear slot; 7, shear Stokes flow over a plate with a regular array of such slots; 8. Stokes flow due to a two-belt stirer. The solutions carry over to appropriate applications in diffusion, heat conduction, electricity, and elasticity.

---

Zusammenfassung Acht Beispiele für Strömungen einer zähen, unzusammendrükbaren Flüssigkeit, die gemischte Randbedingungen erfüllen (Haften und Gleiten) werden gegeben: 1. Scherströmung über eine Platte mit einem längsgerichteten Schlitz ohne Schubspannung; 2. Scherströmung über eine Platte mit senkrecht angeordneten Schlitzen; 3. Strömung in einem zylindrischen Rohr, mit einem oder mehreren Schlitzen; 4. Strömungen zwischen zwei parallelen Platten mit einem längsgerichteten nichtscherenden Schlitz in einer Platte; 5. Strömungen zwischen zwei parallelen Platten mit einer senkrechten Anordnung solcher Schlitze in einer Platte; 6. Stokes Scherströmung über einer Platte mit einer senkrechten Anordnung finden auch Anwendungen auf Probleme der Diffusion, Wärmeleitung, Elektrizität und Elastizität.

     

Some Boolean Algebras with Finitely Many Distinguished Ideals I

We consider the theory Th_prin of Boolean algebras with a principal ideal, the theory Th_max of Boolean algebras with a maximal ideal, the theory Th_ac of atomic Boolean algebras with an ideal where the supremum of the ideal exists, and the theory Th_sa of atomless Boolean algebras with an ideal where the supremum of the ideal exists. First, we find elementary invariants for Th_prin and Th_sa. If T is a theory in a first order language and α is a linear order with least element, then we let Sentalg(T) be the Lindenbaum-Tarski algebra with respect to T, and we let intalg(α) be the interval algebra of α. Using rank diagrams, we show that Sentalg(Th_prin) ? intalg(ω⁴), Sentalg(Th_max) ? intalg(ω³) ? Sentalg(Th_ac), and Sentalg(Th_sa) ? intalg(ω² + ω²). For Th_max and Th_ac we use Ershov's elementary invariants of these theories. We also show that the algebra of formulas of the theory Tx of Boolean algebras with finitely many ideals is atomic.     

Mesons and diquarks in a dense quark medium with color superconductivity

In the framework of the Nambu-Jona-Lasinio model with two quark flavors, we investigate the spectrum of meson and diquark excitations of dense quark matter in the phase with color superconductivity. The color SU_c(3) symmetry is spontaneously broken to SU_c(2) in this phase. But instead of the expected five Goldstone bosons in the mass spectrum, we observe only three, among which two bosons obey the quadratic dispersion law. We find the doublet of light diquark states with the mass ∼ 15 MeV and also the heavy diquark resonance (SU_c(2) singlet) with the mass ∼ 1100 MeV. The π-and σ-mesons have the mass ∼ 330 Mev in the phase with color superconductivity. The π-mesons are then stable particles, while the σ-meson is stable only in the chiral limit in which the current quark mass m₀ becomes zero. If m₀ ≠ 0, then the σ-meson mixes with diquarks in the phase with color superconductivity and becomes a resonance with the width ∼ 30 MeV. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 150, No. 1, pp. 95–111, January, 2007.     

Deterministic symmetric rendezvous with tokens in a synchronous torus

In the rendezvous problem, the goal for two mobile agents is to meet whenever this is possible. In the rendezvous with detection problem, an additional goal for the agents is to detect the impossibility of a rendezvous (e.g., due to symmetrical initial positions of the agents) and stop. We consider the rendezvous problem with and without detection for identical anonymous mobile agents (i.e., running the same deterministic algorithm) with tokens in an anonymous synchronous torus with a sense of direction, and show that there is a striking computational difference between one and more tokens. Specifically, we show that (1) two agents with a constant number of unmovable tokens, or with one movable token each, cannot rendezvous in an n×n torus if they have o(logn) memory, while they can solve the rendezvous with detection problem in an n×m torus as long as they have one unmovable token and O(logn+logm) memory; in contrast, (2) when two agents have two movable tokens each then the rendezvous problem (respectively, rendezvous with detection problem) is solvable with constant memory in an arbitrary n×m (respectively, n×n) torus; and finally, (3) two agents with three movable tokens each and constant memory can solve the rendezvous with detection problem in an n×m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in a torus.     

Analoga der steinerschen konstruktion in einer absoluten geometrie

We consider an absolute geometry with the following base of axioms: Hilbert's plane axioms of incidence, order and congruence and a circle axiom. Thus no parallelism and not much continuity is involved. In this geometry the metric cannot be determined by Steiner's basic structure “fixed circle with centre”. In this work it will be proved that the following basic figures are suitable for such an absolute geometry in the sense that, after tracing any one of them, all constructions of second order can be done only with a ruler:

1. Two non-concentric circles, one of them with centre.
2. A unit-turner and a non-concentric circle without centre.
3. A circle with centreO and a line segmentA B with midpointM, the linesA B andO M being not orthogonal.
4. A circle with centre and two orthogonal lines, none of them passing through the centre.
5. A circle with centre and a distance-line (with their two branches).

In the basic structures 1, 3, 4, 5, instead of a circle with centre, a finite arc of a circle with centre or two concentric circles without centre may be taken.     

Matrix Extension with Symmetry and Applications to Symmetric Orthonormal Complex M-wavelets

Matrix extension with symmetry is to find a unitary square matrix P of 2π-periodic trigonometric polynomials with symmetry such that the first row of P is a given row vector p of 2π-periodic trigonometric polynomials with symmetry satisfying p[`(p)]^T=1\mathbf {p}\overline{\mathbf{p}}^{T}=1 . Matrix extension plays a fundamental role in many areas such as electronic engineering, system sciences, wavelet analysis, and applied mathematics. In this paper, we shall solve matrix extension with symmetry by developing a step-by-step simple algorithm to derive a desired square matrix P from a given row vector p of 2π-periodic trigonometric polynomials with complex coefficients and symmetry. As an application of our algorithm for matrix extension with symmetry, for any dilation factor M, we shall present two families of compactly supported symmetric orthonormal complex M-wavelets with arbitrarily high vanishing moments. Wavelets in the first family have the shortest possible supports with respect to their orders of vanishing moments; their existence relies on the establishment of nonnegativity on the real line of certain associated polynomials. Wavelets in the second family have increasing orders of linear-phase moments and vanishing moments, which are desirable properties in numerical algorithms.     

A note on class one graphs with maximum degree six

It is known that there are class two graphs with Δ=6 which can be embedded in a surface Σ with Euler characteristic χ(Σ)?0. However, it is unknown whether there are class two graphs on the projective plane or on the plane with Δ=6. In this paper, we prove that every graph with Δ=6 is class one if it can be embedded in a surface with Euler characteristic at least -3 and is C₃-free, or C₄-free or if it can be embedded in a surface with Euler characteristic at least -1 and is C₅-free. This generalizes Zhou's results in [G. Zhou, A note on graphs of class I, Discrete Math. 263 (2003) 339-345] on planar graphs.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

G-Closed fields and imbeddings of quadratic number fields

A field, K, that has no extensions with Galois group isomorphic to G is called G-closed. It is proved that a finite extension of K admits an infinite number of nonisomorphic extensions with Galois group G. A trinomial of degree n is exhibited with Galois group, the symmetric group of degree n, and with prescribed discriminant. This result is used to show that any quadratic extension of an A_n-closed field admits an extension with Galois group A_n.     

Perfect difference families,perfect difference matrices,and related combinatorial structures

The existence problems of perfect difference families with block size k, k=4,5, and additive sequences of permutations of length n, n=3,4, are two outstanding open problems in combinatorial design theory for more than 30 years. In this article, we mainly investigate perfect difference families with block size k=4 and additive sequences of permutations of length n=3. The necessary condition for the existence of a perfect difference family with block size 4 and order v, or briefly (v, 4,1)‐PDF, is v≡1(mod12), and that of an additive sequence of permutations of length 3 and order m, or briefly ASP (3, m), is m≡1(mod2). So far, (12t+1,4,1)‐PDFs with t<50 are known only for t=1,4−36,41,46 with two definiteexceptions of t=2,3, and ASP (3, m)'s with odd 3<m<200 are known only for m=5,7,13−29,35,45,49,65,75,85,91,95,105,115,119,121,125,133,135,145,147,161,169,175,189,195 with two definite exceptions of m=9,11. In this article, we show that a (12t+1,4,1)‐PDF exists for any t⩽1,000 except for t=2,3, and an ASP (3, m) exists for any odd 3<m<200 except for m=9,11 and possibly for m=59. The main idea of this article is to use perfect difference families and additive sequences of permutations with “holes”. We first introduce the concepts of an incomplete perfect difference matrix with a regular hole and a perfect difference packing with a regular difference leave, respectively. We show that an additive sequence of permutations is in fact equivalent to a perfect difference matrix, then describe an important recursive construction for perfect difference matrices via perfect difference packings with a regular difference leave. Plenty of perfect difference packings with a desirable difference leave are constructed directly. We also provide a general recursive construction for perfect difference packings, and as its applications, we obtain extensive recursive constructions for perfect difference families, some via incomplete perfect difference matrices with a regular hole. Examples of perfect difference packings directly constructed are used as ingredients in these recursive constructions to produce vast numbers of perfect difference families with block size 4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 415–449, 2010     

A class of vertex-transitive digraphs,II

(1). We determine the number of non-isomorphic classes of self-complementary circulant digraphs with pq vertices, where p and q are distinct primes. The non-isomorphic classes of these circulant digraphs with pq vertices are enumerated. (2). We also determine the number of non-isomorphic classes of self-complementary, vertex-transitive digraphs with a prime number p vertices, and the number of self-complementary strongly vertex-transitive digraphs with p vertices. The non-isomorphic classes of strongly vertex-transitive digraphs with p vertices are also enumerated.     

Stability in CAN-free graphs

A class $\text{F}$ of graphs characterized by three forbidden subgraphs C, A, N is considered; C is the claw (the unique graph with degree sequence (1, 1, 1, 3)), A is the antenna (a graph with degree sequence (1, 2, 2, 3, 3, 3) which does not contain C), and N is the net (the unique graph with degree sequence (1, 1, 1, 3, 3, 3)). These graphs are called CAN-free. A construction is described which associates with every CAN-free graph G another CAN-free graph G′ with strictly fewer nodes than G and with stbility number α(G′) = α(G) ? 1. This gives a good algorithm for determining the stability number of CAN-free graphs.     

n-bathycenters

Does there exist a polygon with the property that for a suitable point p in the plane every ray with endpoint p intersects the polygon in exactly n connected components? Does there exist a polygon with the property that there are two such points, or three, or a segment of such points? For polygon P call a point p with the property that every ray from p intersects P in exactly n connected components n-isobathic with respect to P. Define the n-bathycenter of a polygon P as the set of all points p that are n-isobathic with respect to P. Further define a set S to be an n-bathycenter if there exists a polygon P of which S is the n-bathycenter. This paper deals with the characterization of 2- and 3-bathycenters, together with some results on the general case.     

Proof of the local REM conjecture for number partitioning. II. Growing energy scales

We continue our analysis of the number partitioning problem with n weights chosen i.i.d. from some fixed probability distribution with density ρ. In Part I of this work, we established the so‐called local REM conjecture of Bauke, Franz and Mertens. Namely, we showed that, as n → ∞, the suitably rescaled energy spectrum above some fixed scale α tends to a Poisson process with density one, and the partitions corresponding to these energies become asymptotically uncorrelated. In this part, we analyze the number partitioning problem for energy scales α_n that grow with n, and show that the local REM conjecture holds as long as n^‐1/4α_n → 0, and fails if α_n grows like κn^1/4 with κ > 0. We also consider the SK‐spin glass model, and show that it has an analogous threshold: the local REM conjecture holds for energies of order o(n), and fails if the energies grow like κn with κ > 0. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Axisymmetrical rotating jets

The article presents computation results for a free jet emerging from a nozzle of radius R with Mach number M = 1 and nonrated value n = 3. The jet rotates at the nozzle outlet with constant angular velocity ω = 2 and corresponding circular velocity W = ωr (r < R ). The computation results for this jet are compared with those for a laminar (non-rotating) jet with the same fluid-dynamic parameters. The numerical results corroborate the theoretical conclusions concerning the effect of jet rotation on flow structure. Specifically, it is confirmed that the mixing of the jet with the surrounding gas is more intense and that a strongly twisted jet exhibits backflow toward the nozzle in the axial region. Translated from Prikladnaya Matematika i Informatika, No. 28, pp. 44–49, 2008.