Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

A construction for equidistant permutation arrays of index one

An equidistant permutation array (EPA) which we denote by A(r, λ; ν) is a ν × r array such that every row is a permutation of the integers 1, 2,…, r and such that every pair of distinct rows has precisely λ columns in common. R(r, λ) is the maximum ν such that there exists an A(r, λ; ν). In this paper we show that R(n² + n + 2, 1) ? 2n² + n where n is a prime power.     

On operator norms of submatrices

Both of the following conditions are equivalent to the absoluteness of a norm ν in $\text{C}$ⁿ: (1) for all n×n diagonal matrices D=(d_k), the subordinate operator norm N_ν(D)=max_k|d_k|; (2) for all n×n matrices A, N_ν(A) ?N_ν(|A|). These conditions are modified for partitioned matrices by replacing absolute values with norms of blocks. A generalization of absoluteness is thus obtained.     

Transversal numbers of translates of a convex body

Let F be a family of translates of a fixed convex set M in Rⁿ. Let τ(F) and ν(F) denote the transversal number and the independence number of F, respectively. We show that ν(F)?τ(F)?8ν(F)-5 for n=2 and τ(F)?2^n-1nⁿν(F) for n?3. Furthermore, if M is centrally symmetric convex body in the plane, then ν(F)?τ(F)?6ν(F)-3.     

Ruzsa’s constant on additive functions

A function f : N → R is called additive if f(mn)= f(m)+f(n)for all m, n with(m, n)= 1. Let μ(x)= max n≤x(f(n)f(n + 1))and ν(x)= max n≤x(f(n + 1)f(n)). In 1979, Ruzsa proved that there exists a constant c such that for any additive function f , μ(x)≤ cν(x 2 )+ c f , where c f is a constant depending only on f . Denote by R af the least such constant c. We call R af Ruzsa's constant on additive functions. In this paper, we prove that R af ≤ 20.     

λ-fold indecomposable large sets of Steiner triple systems

A family (X, B1), (X, B2), . . . , (X, Bq) of q STS(v)s is a λ-fold large set of STS(v) and denoted by LSTSλ(v) if every 3-subset of X is contained in exactly λ STS(v)s of the collection. It is indecomposable and denoted by IDLSTSλ(v) if there exists no LSTSλ (v) contained in the collection for any λ λ. In 1995, Griggs and Rosa posed a problem: For which values of λ 1 and orders v ≡ 1, 3 (mod 6) do there exist IDLSTSλ(v)? In this paper, we use partitionable candelabra systems (PCSs) and holey λ-fold large set of STS(v) (HLSTSλ(v)) as auxiliary designs to establish a recursive construction for IDLSTSλ(v) and show that there exists an IDLSTSλ(v) for λ = 2, 3, 4 and v ≡ 1, 3 (mod 6).     

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows：Dv（H）≤min{α≤（H）, p（H）, p（H）, T（H）}; De（H）≤min{v（H）, T（H）, p（H）}; DT（H） ≤αT（H）; S（H）≤ Dv （H） ＋ α（H）≤n; 2≤ Dv （H） ＋ T（H） ≤n; 2 〈 Dv （H） ＋ v（H）≤n/2 ＋ [n/r]; Dv （H） ＋ p（H） 〈_n;2≤De（H） ＋ Dv（H）≤n/2 ＋ [n/r];α（H） ＋ De（H）≤n;2 ≤ De（H） ＋ v（H）≤2[n/r]; 2 De（H） ＋ p（H）≤n-r ＋ 2.     

On the number of A-mappings

Suppose that $ \mathfrak{S} $ _n is the semigroup of mappings of the set of n elements into itself, A is a fixed subset of the set of natural numbers ?, and V _n (A) is the set of mappings from $ \mathfrak{S} $ _n whose contours are of sizes belonging to A. Mappings from V _n (A) are usually called A-mappings. Consider a random mapping σ _n , uniformly distributed on V n(A). Suppose that ν _n is the number of components and λ _n is the number of cyclic points of the random mapping σ _n . In this paper, for a particular class of sets A, we obtain the asymptotics of the number of elements of the set V _n (A) and prove limit theorems for the random variables ν _n and λ _n as n → ∞.     

Coarse-grained entropy in dynamical systems

Let M be the phase space of a physical system. Consider the dynamics, determined by the invertible map T: M → M, preserving the measure µ on M. Let ν be another measure on M, dν = ρdµ. Gibbs introduced the quantity s(ρ) = ?∝ρ log ρdµ as an analog of the thermodynamical entropy. We consider a modification of the Gibbs (fine-grained) entropy the so called coarse-grained entropy. First we obtain a formula for the difference between the coarse-grained and Gibbs entropy. The main term of the difference is expressed by a functional usually referenced to as the Fisher information. Then we consider the behavior of the coarse-grained entropy as a function of time. The dynamics transforms ν in the following way: ν → ν _n , dν _n = ρ ○ T ^?n dµ. Hence, we obtain the sequence of densities ρ _n = ρ ○ T ^?n and the corresponding values of the Gibbs and the coarse-grained entropy. We show that while the Gibbs entropy remains constant, the coarse-grained entropy has a tendency to a growth and this growth is determined by dynamical properties of the map T. Finally, we give numerical calculation of the coarse-grained entropy as a function of time for systems with various dynamical properties: integrable, chaotic and with mixed dynamics and compare these calculation with theoretical statements.     

Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)     

On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

Graphs and ranks of monoids

For a finite monoid S, let ν(S) (ν_d(S)) denote the least number n such that there exists a graph (directed graph) Γ of order n with End(Γ)?S. Also let rank(S) be the smallest number of elements required to generate S. In this paper, we use Cayley digraphs of monoids, to connect lower bounds of ν(S) (ν_d(S)) to the lower bounds of rank(S). On the other hand, we connect upper bounds of rank(S) to upper bounds of ν(S) (ν_d(S)).     

Sur les entiers dont la somme des chiffres est moyenne

The goal of this paper is to study sets of integers with an average sum of digits. More precisely, let g be a fixed integer, s(n) be the sum of the digits of n in basis g. Let f:N→N such that, in any interval [g^ν,g^ν+1[, f(n) is constant and near from (g-1)ν/2. We give an asymptotic for the number of integers n<x such that s(n)=f(n) and we prove that for every irrational α the sequence (αn) is equidistributed mod 1, for n satisfying s(n)=f(n).     

A note on the diophantine equation (a n − 1)(b n − 1) = x 2

Let a, b be fixed positive integers such that a ≠ b, min(a, b) > 1, ν(a?1) and ν(b ? 1) have opposite parity, where ν(a ? 1) and ν(b ? 1) denote the highest powers of 2 dividing a ? 1 and b ? 1 respectively. In this paper, all positive integer solutions (x, n) of the equation (a ⁿ ? 1)(b ⁿ ? 1) = x ² are determined.     

Some Results for Decomposition Numbers for the Hecke Algebra of Type A with q = −1

Let ? = ?_{?, ?1}(𝔖 _n ) be the Hecke algebra of the symmetric group 𝔖 _n . For partitions λ and ν with ν 2 ? regular, define the Specht module S(λ) and the irreducible module D(ν). Define d _λν = [S(λ): D(ν)] to be the composition multiplicity of D(ν) in S(λ). In this paper we compute the decomposition numbers d _λν for all partitions of the form λ = (a, c, 1 ^b ) and ν 2 ? regular.     

Integral representations and summations of the modified Struve function

It is known that the Struve function H _ν and the modified Struve function L _ν are closely connected to the Bessel function of the first kind J _ν and to the modified Bessel function of the first kind I _ν and possess representations through higher transcendental functions like the generalized hypergeometric ₁ F ₂ and the Meijer G function. Also, the NIST project and Wolfram formula collection contain a set of Kapteyn type series expansions for L _ν (x). In this paper firstly, we obtain various another type integral representation formulae for L _ν (x) using the technique developed by D. Jankov and the authors. Secondly, we present some summation results for different kind of Neumann, Kapteyn and Schlömilch series built by I _ν (x) and L _ν (x) which are connected by a Sonin–Gubler formula, and by the associated modified Struve differential equation. Finally, solving a Fredholm type convolutional integral equation of the first kind, Bromwich–Wagner line integral expressions are derived for the Bessel function of first kind J _ν and for an associated generalized Schlömilch series.     

On locally repeated values of certain arithmetic functions,I

Let ν(n) denote the number of distinct prime factors of n. We show that the equation n + ν(n) = m + ν(m) has many solutions with n ≠ m. We also show that if ν is replaced by an arbitrary, integer-valued function f with certain properties assumed about its average order, then the equation n + f(n) = m + f(m) has infinitely many solutions with n ≠ m.     

Prime and composite integers close to powers of a number

We prove that, for any real numbers ξ ≠ 0 and ν, the sequence of integer parts [ξ2 ⁿ  + ν], n = 0, 1, 2, . . . , contains infinitely many composite numbers. Moreover, if the number ξ is irrational, then the above sequence contains infinitely many elements divisible by 2 or 3. The same holds for the sequence [ξ( ? 2) ⁿ  + ν _n ], n = 0, 1, 2, . . . , where ν ₀, ν ₁, ν ₂, . . . all lie in a half open real interval of length 1/3. For this, we show that if a sequence of integers x ₁, x ₂, x ₃, . . . satisfies the recurrence relation x _n+d  = cx _n  + F(x _n+1, . . . , x _n+d-1) for each n  ≥  1, where c ≠ 0 is an integer, \({F(z_1,\dots,z_{d-1}) \in \mathbb {Z}[z_1,\dots,z_{d-1}],}\) and lim _{n→ ∞}|x _n | = ∞, then the number |x _n | is composite for infinitely many positive integers n. The proofs involve techniques from number theory, linear algebra, combinatorics on words and some kind of symbolic computation modulo 3.     

Zeta measures and Thermodynamic Formalism for temperature zero

We address the analysis of the following problem: given a real Hölder potential f defined on the Bernoulli space and μ _f its equilibrium state, it is known that this shift-invariant probability can be weakly approximated by probabilities in periodic orbits associated to certain zeta functions. Given a Hölder function f > 0 and a value s such that 0 < s < 1, we can associate a shift-invariant probability ν _s such that for each continuous function k we have $ \int {kd} v_s = \frac{{\sum\nolimits_{n = 1}^\infty {\sum\nolimits_{x \in Fix_n } {e^{sf^n (x) - nP(f)\frac{{k^n (x)}} {n}} } } }} {{\sum\nolimits_{n = 1}^\infty {\sum\nolimits_{x \in Fix_n } {e^{sf^n (x) - nP(f)} } } }}, $ , where P(f) is the pressure of f, Fix _n is the set of solutions of σ ⁿ (x) = x, for any n ∈ ?, and f ⁿ (x) = f(x) + f(σ (x)) + … + f(σ ^n?1(x)). We call νs a zeta probability for f and s, because it can be obtained in a natural way from the dynamical zeta-functions. From the work of W. Parry and M. Pollicott it is known that ν _s → µ _f , when s → 1. We consider for each value c the potential c f and the corresponding equilibrium state μ _cf . What happens with ν _s when c goes to infinity and s goes to one? This question is related to the problem of how to approximate the maximizing probability for f by probabilities on periodic orbits. We study this question and also present here the deviation function I and Large Deviation Principle for this limit c → ∞, s → 1. We will make an assumption: for some fixed L we have lim _{c→∞, s→1} c(1 ? s) = L > 0. We do not assume here the maximizing probability for f is unique in order to get the L.D.P.