On the Ramsey number of the triangle and the cube

The Ramsey number r(K ₃,Q _n ) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K _N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erd?s conjectured that r(K ₃,Q _n )=2 ⁿ⁺¹?1 for every n∈?, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K ₃,Q _n )?7000·2 ⁿ . Here we show that r(K ₃,Q _n )=(1+o(1))2 ⁿ⁺¹ as n→∞.     

Calculating the Isotropic Subspace of a Symmetric Quasi-Definite Matrix

Solutions to the sesquilinear matrix equation X*DX + AX + X*B + C = 0, where all matrices are of size n × n, are put in correspondence with n-dimensional neutral (or isotropic) subspaces of the associated matrix M of order 2n. A way of constructing such subspaces is proposed for when M is a symmetric quasi-definite matrix of the (n, n) type.     

On an Extremal Problem for Poset Dimension

Let f(n) be the largest integer such that every poset on n elements has a 2-dimensional subposet on f(n) elements. What is the asymptotics of f(n)? It is easy to see that f(n) = n ^1/2. We improve the best known upper bound and show f(n) = O (n ^2/3). For higher dimensions, we show \(f_{d}(n)=\O \left (n^{\frac {d}{d + 1}}\right )\), where f _d (n) is the largest integer such that every poset on n elements has a d-dimensional subposet on f _d (n) elements.     

An improvement of the five halves theorem of J. Boardman

Let (M ^m , T) be a smooth involution on a closed smooth m-dimensional manifold and F = ∪ _j=0 ⁿ F ^j (n ≤ m) its fixed point set, where F ^j denotes the union of those components of F having dimension j. The famous Five Halves Theorem of J. Boardman, announced in 1967, establishes that, if F is nonbounding, then m ≤ 5/2n. In this paper we obtain an improvement of the Five Halves Theorem when the top dimensional component of F, F ⁿ , is nonbounding. Specifically, let ω = (i ₁, i ₂, …, i _r ) be a non-dyadic partition of n and s _ω (x ₁, x ₂, …, x _n ) the smallest symmetric polynomial over Z ₂ on degree one variables x ₁, x ₂, …, x _n containing the monomial \(x_1^{i_1 } x_2^{i_2 } \cdots x_r^{i_r }\). Write s _ω (F ⁿ ) ∈ H ⁿ (F ⁿ , Z ₂) for the usual cohomology class corresponding to s _ω (x ₁, x ₂, …, x _n ), and denote by ?(F ⁿ ) the minimum length of a nondyadic partition ω with s _ω (F ⁿ ) ≠ 0 (here, the length of ω = (i ₁, i ₂, …, i _r ) is r). We will prove that, if (M ^m , T) is an involution for which the top dimensional component of the fixed point set, F ⁿ , is nonbounding, then m ≤ 2n + ?(F ⁿ ); roughly speaking, the bound for m depends on the degree of decomposability of the top dimensional component of the fixed point set. Further, we will give examples to show that this bound is best possible.     

Lower bounds for the largest eigenvalue of the gcd matrix on {1, 2,..., n}

Consider the n×n matrix with (i, j)’th entry gcd (i, j). Its largest eigenvalue λ_n and sum of entries s_n satisfy λ_n > s_n/n. Because s_n cannot be expressed algebraically as a function of n, we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S.Hong, R.Loewy (2004). We also conjecture that λ_n > 6π^?2nlogn for all n. If n is large enough, this follows from F.Balatoni (1969).     

A stability result using the matrix norm to bound the permanent

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm. More specifically, suppose A is an n × n matrix over C (resp. R), and let P denote the set of n × n matrices over C (resp. R) that can be written as a permutation matrix times a unitary diagonal matrix. Then it is known that the permanent of A satisfies |per(A)| ≤ ||A|| ⁿ ₂ with equality iff A/||A||₂ ∈ P (where ||A||₂ is the operator 2-norm of A). We show a stability version of this result asserting that unless A is very close (in a particular sense) to one of these extremal matrices, its permanent is exponentially smaller (as a function of n) than ||A|| ⁿ ₂. In particular, for any fixed α, β > 0, we show that |per(A)| is exponentially smaller than ||A|| ⁿ ₂ unless all but at most αn rows contain entries of modulus at least ||A||₂(1?β).     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

New Applications of the <Emphasis Type="Italic">p</Emphasis>-Adic Nevanlinna Theory

Let IK be an algebraically closed field of characteristic 0 complete for an ultrametric absolute value. Following results obtained in complex analysis, here we examine problems of uniqueness for meromorphic functions having finitely many poles, sharing points or a pair of sets (C.M. or I.M.) defined either in the whole field IK or in an open disk, or in the complement of an open disk. Following previous works in C, we consider functions fⁿ(x)f^m(ax + b), gⁿ(x)g^m(ax + b) with |a| = 1 and n ≠ m, sharing a rational function and we show that f/g is a n + m-th root of 1 whenever n + m ≥ 5. Next, given a small function w, if n, m ∈ IN are such that |n ? m|_∞ ≥ 5, then fⁿ(x)f^m(ax + b) ? w has infinitely many zeros. Finally, we examine branched values for meromorphic functions fⁿ(x)f^m(ax + b).     

On the summability factors of infinite series

The author has established that if [λ_n] is a convex sequence such that the series Σn ^-1λ_n is convergent and the sequence {K _n} satisfies the condition |K _n|=O[log(n+1)]^k(C, 1),k?0, whereK _n denotes the (R, logn, 1) mean of the sequence {n log (n+1)a _n}, then the series Σlog(n+1)^1-kλ_n a _n is summable |R, logn, 1|. The result obtained for the particular casek=0 generalises a previous result of the author [1].     

On the k-polygonal numbers and the mean value of Dedekind sums

For any positive integer k ≥ 3, it is easy to prove that the k-polygonal numbers are a_n(k) = (2n+n(n?1)(k?2))/2. The main purpose of this paper is, using the properties of Gauss sums and Dedekind sums, the mean square value theorem of Dirichlet L-functions and the analytic methods, to study the computational problem of one kind mean value of Dedekind sums S(a_n(k)ā_m(k), p) for k-polygonal numbers with 1 ≤ m, n ≤ p ? 1, and give an interesting computational formula for it.     

Covering the sphere by equal zones

A zone of half-width w on the unit sphere S² in Euclidean 3-space is the parallel domain of radius w of a great circle. L. Fejes Tóth raised the following question in [6]: what is the minimal w_n such that one can cover S² with n zones of half-width w_n? This question can be considered as a spherical relative of the famous plank problem of Tarski. We prove lower bounds for the minimum half-width w_n for all n ≧ 5.     

Solving Equations of Free Vibration for a Cylindrical Shell Rotating on Rollers by the Fourier Method

The small free vibrations of an infinite circular cylindrical shell rotating about its axis at a constant angular velocity are considered. The shell is supported on n absolutely rigid cylindrical rollers equispaced on its circle. The roller-supported shell is a model of an ore benefication centrifugal concentrator with a floating bed. The set of linear differential equations of vibrations is sought in the form of a truncated Fourier series containing N terms along the circumferential coordinate. A system of 2N–n linear homogeneous algebraic equations with 2N–n unknowns is derived for the approximate estimation of vibration frequencies and mode shapes. The frequencies ω _k , k = 1, 2, …, 2N–n, are positive roots of the (2N–n)th-order algebraic equation D(ω²) = 0, where D is the determinant of this set. It is shown that the system of 2N–n equations is equivalent to several independent systems with a smaller number of unknowns. As a consequence, the (2N–n)th-order determinant D can be written as a product of lower-order determinants. In particular, the frequencies at N = n are the roots of algebraic equations of an order is lower than 2 and can be found in an explicit form. Some frequency estimation algorithms have been developed for the case of N > n. When N increases, the number of found frequencies also grows, and the frequencies determined at N = n are refined. However, in most cases, the vibration frequencies can not be found for N > n in an explicit form.     

Estimation of the depth of reversible circuits consisting of NOT,CNOT and 2-CNOT gates

The paper discusses the asymptotic depth of a reversible circuits consisting of NOT, CNOT and 2-CNOT gates. The reversible circuit depth function D(n, q) is introduced for a circuit implementing a mapping f: Z₂ⁿ → Z₂ⁿ as a function of n and the number q of additional inputs. It is proved that for the case of implementation of a permutation from A(Z₂ⁿ) with a reversible circuit having no additional inputs the depth is bounded as D(n, 0) ? 2ⁿ/(3log₂n). It is also proved that for the case of transformation f: Z₂ⁿ → Z₂ⁿ with a reversible circuit having q₀ ~ 2ⁿ additional inputs the depth is bounded as D(n,q₀) ? 3n.     

On the tree structure of the power digraphs modulo n

For any two positive integers n and k ? 2, let G(n, k) be a digraph whose set of vertices is {0, 1, …, n ? 1} and such that there is a directed edge from a vertex a to a vertex b if a ^k ≡ b (mod n). Let \(n = \prod\nolimits_{i = 1}^r {p_i^{{e_i}}} \) be the prime factorization of n. Let P be the set of all primes dividing n and let P ₁, P ₂ ? P be such that P ₁ ∪ P ₂ = P and P ₁ ∩ P ₂ = ?. A fundamental constituent of G(n, k), denoted by \(G_{{P_2}}^*(n,k)\), is a subdigraph of G(n, k) induced on the set of vertices which are multiples of \(\prod\nolimits_{{p_i} \in {P_2}} {{p_i}} \) and are relatively prime to all primes q ∈ P ₁. L. Somer and M. K?i?ek proved that the trees attached to all cycle vertices in the same fundamental constituent of G(n, k) are isomorphic. In this paper, we characterize all digraphs G(n, k) such that the trees attached to all cycle vertices in different fundamental constituents of G(n, k) are isomorphic. We also provide a necessary and sufficient condition on G(n, k) such that the trees attached to all cycle vertices in G(n, k) are isomorphic.     

An algorithm to compute <Emphasis Type="Italic">ω</Emphasis>-primality in a numerical monoid

Let M be a commutative, cancellative, atomic monoid and x a nonunit in M. We define ω(x)=n if n is the smallest positive integer with the property that whenever x∣a ₁???a _t , where each a _i is an atom, there is a T?{1,2,…,t} with |T|≤n such that x∣∏_k∈T a _k . The ω-function measures how far x is from being prime in M. In this paper, we give an algorithm for computing ω(x) in any numerical monoid. Simple formulas for ω(x) are given for numerical monoids of the form 〈n,n+1,…,2n?1〉, where n≥3, and 〈n,n+1,…,2n?2〉, where n≥4. The paper then focuses on the special case of 2-generator numerical monoids. We give a formula for computing ω(x) in this case and also necessary and sufficient conditions for determining when x is an atom. Finally, we analyze the asymptotic behavior of ω(x) by computing \(\lim_{x\rightarrow \infty}\frac{\omega(x)}{x}\).     

Maximum Distance Between Slater Orders and Copeland Orders of Tournaments

Given a tournament T?=?(X, A), we consider two tournament solutions applied to T: Slater’s solution and Copeland’s solution. Slater’s solution consists in determining the linear orders obtained by reversing a minimum number of directed edges of T in order to make T transitive. Copeland’s solution applied to T ranks the vertices of T according to their decreasing out-degrees. The aim of this paper is to compare the results provided by these two methods: to which extent can they lead to different orders? We consider three cases: T is any tournament, T is strongly connected, T has only one Slater order. For each one of these three cases, we specify the maximum of the symmetric difference distance between Slater orders and Copeland orders. More precisely, thanks to a result dealing with arc-disjoint circuits in circular tournaments, we show that this maximum is equal to n(n???1)/2 if T is any tournament on an odd number n of vertices, to (n ²???3n?+?2)/2 if T is any tournament on an even number n of vertices, to n(n???1)/2 if T is strongly connected with an odd number n of vertices, to (n ²???3n???2)/2 if T is strongly connected with an even number n of vertices greater than or equal to 8, to (n ²???5n?+?6)/2 if T has an odd number n of vertices and only one Slater order, to (n ²???5n?+?8)/2 if T has an even number n of vertices and only one Slater order.     

On collineation groups of finite projective spaces containing a Singer cycle

By a result of Kantor, any subgroup of GL(n, q) containing a Singer cycle normalizes a field extension subgroup. This result has as a consequence a projective analogue, and this paper gives the details of this deduction, showing that any subgroup of PΓL(n, q) containing a projective Singer cycle normalizes the image of a field extension subgroup GL(n/s, q^s) under the canonical homomorphism GL(n, q) → PGL(n, q), for some divisor s of n, and so is contained in the image of ΓL(n/s, q^s) under the canonical homomorphism ΓL(n, q) → PΓL(n, q). The actions of field extension subgroups on V (n, q) are also investigated. In particular, we prove that any field extension subgroup GL(n/s, q^s) of GL(n, q) has a unique orbit on s-dimensional subspaces of V (n, q) of length coprime to q. This orbit is a Desarguesian s-partition of V (n, q).     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.