Classification of regular embeddings of hypercubes of odd dimension

By a regular embedding of a graph into a closed surface we mean a 2-cell embedding with the automorphism group acting regularly on flags. Recently, Kwon and Nedela [Non-existence of nonorientable regular embeddings of n-dimensional cubes, Discrete Math., to appear] showed that no regular embeddings of the n-dimensional cubes Q_n into nonorientable surfaces exist for any positive integer n>2. In 1997, Nedela and Škoviera [Regular maps from voltage assignments and exponent groups, European J. Combin. 18 (1997) 807-823] presented a construction giving for each solution of the congruence a regular embedding M_e of the hypercube Q_n into an orientable surface. It was conjectured that all regular embeddings of Q_n into orientable surfaces can be constructed in this way. This paper gives a classification of regular embeddings of hypercubes Q_n into orientable surfaces for n odd, proving affirmatively the conjecture of Nedela and Škoviera for every odd n.     

A contribution to the Zarankiewicz problem

Given positive integers let z(m,n,s,t) be the maximum number of ones in a (0,1) matrix of size m×n that does not contain an all ones submatrix of size s×t. We show that if s?2 and t?2, then for every k=0,…,s-2,

z(m,n,s,t)?(s-k-1)^1/tnm^1-1/t+kn+(t-1)m^1+k/t.     

A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs

We prove a theorem that for an integer s?0, if 12s+7 is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of K_n, where n=(12s+7)(6s+7), is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least 2^αn?+o(n?), ?>1, nonisomorphic nonorientable triangular embeddings of K_n for n=6t+1, . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied.There are three approaches to solve this problem.The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths;the second approach is to find a current assignment of the current graph by the theory of current graph;the third approach is to find exponentially many embedding(or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph.According to this three approaches,we can construct exponentially many minimum genus embeddings of complete graph K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

Classification of Regular Embeddings of Complete Multipartite Graphs

A 2‐cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph $K_{n,\dots ,n}$. We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any n, there exist one orientable regular embedding and one nonorientable regular embedding of $K_{n,n,n}$ up to isomorphism.     

Classification of regular embeddings of <Emphasis Type="Italic">n</Emphasis>-dimensional cubes

An orientably-regular map is a 2-cell embedding of a connected graph or multigraph into an orientable surface, such that the group of all orientation-preserving automorphisms of the embedding has a single orbit on the set of all arcs (incident vertex-edge pairs). Such embeddings of the n-dimensional cubes Q _n were classified for all odd n by Du, Kwak and Nedela in 2005, and in 2007, Jing Xu proved that for n=2m where m is odd, they are precisely the embeddings constructed by Kwon in 2004. Here, we give a classification of orientably-regular embeddings of Q _n for all n. In particular, we show that for all even n (=2m), these embeddings are in one-to-one correspondence with elements σ of order 1 or 2 in the symmetric group S _n such that σ fixes n, preserves the set of all pairs B _i ={i,i+m} for 1≤i≤m, and induces the same permutation on this set as the permutation B _i ↦ B _f(i) for some additive bijection f:ℤ _m →ℤ _m . We also give formulae for the numbers of embeddings that are reflexible and chiral, respectively, showing that the ratio of reflexible to chiral embeddings tends to zero for large even n.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

Centers for a 6-parameter family of polynomial vector fields of arbitrary degree

For all non-negative integers n₁,n₂,n₃,j₁,j₂ and j₃ with nk+jk>1 for k=1,2,3, (nk,jk)≠(nl,jl) if k≠l, j₃=n₃−1 and jk≠nk−1 for k=1,2, we study the center variety of the 6-parameter family of real planar polynomial vector given, in complex notation, by , where z=x+iy and A,B,C∈C\{0}.     

Thue-Morse at multiples of an integer

Let t=(tn)_n?0 be the classical Thue-Morse sequence defined by , where s₂ is the sum of the bits in the binary representation of n. It is well known that for any integer k?1 the frequency of the letter “1” in the subsequence t₀,tk,t2k,… is asymptotically 1/2. Here we prove that for any k there is an n?k+4 such that tkn=1. Moreover, we show that n can be chosen to have Hamming weight ?3. This is best in a twofold sense. First, there are infinitely many k such that tkn=1 implies that n has Hamming weight ?3. Second, we characterize all k where the minimal n equals k, k+1, k+2, k+3, or k+4. Finally, we present some results and conjectures for the generalized problem, where s₂ is replaced by sb for an arbitrary base b?2.     

Nontrivial lower bounds for the least common multiple of some finite sequences of integers

We present here a method which allows to derive a nontrivial lower bounds for the least common multiple of some finite sequences of integers. We obtain efficient lower bounds (which in a way are optimal) for the arithmetic progressions and lower bounds less efficient (but nontrivial) for quadratic sequences whose general term has the form un=an(n+t)+b with (a,t,b)∈Z³, a?5, t?0, gcd(a,b)=1. From this, we deduce for instance the lower bound: lcm{¹²+1,²²+1,…,n²+1}?0,32n(1,442) (for all n?1). In the last part of this article, we study the integer lcm(n,n+1,…,n+k) (k∈N, n∈N^∗). We show that it has a divisor dn,k simple in its dependence on n and k, and a multiple mn,k also simple in its dependence on n. In addition, we prove that both equalities: lcm(n,n+1,…,n+k)=dn,k and lcm(n,n+1,…,n+k)=mn,k hold for an infinitely many pairs (n,k).     

Regular orientable embeddings of complete bipartite graphs

In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph K_n,n are in one‐to‐one correspondence with the permutations on n elements satisfying a given criterion, and the isomorphism classes of them are completely classified when n is a product of any two (not necessarily distinct) prime numbers. For other n, a lower bound of the number of those isomorphism classes of K_n,n is obtained. As a result, many new regular orientable embeddings of the complete bipartite graph are constructed giving an answer of Nedela‐?koviera's question raised in 12 . © 2005 Wiley Periodicals, Inc. J Graph Theory     

Sparsity and non-Euclidean embeddings

We present a relation between sparsity and non-Euclidean isomorphic embeddings. We introduce a general restricted isomorphism property and show how it enables one to construct embeddings of ? _p ⁿ , p > 0, into various types of Banach or quasi-Banach spaces. In particular, for 0 < r < p < 2 with r ≤ 1, we construct a family of operators that embed ? _p ⁿ into $\ell _r^{(1 + \eta )n}$ , with sharp polynomial bounds in η > 0.     

Divisibility properties of generalized Laguerre polynomials

In this paper we give effective upper bounds for the degree k of divisors (over ?) of generalized Laguerre polynomials L^α_n(x), i.e. of for α = −tn − s − 1 and α = tn + s with t,s ∈ ?, t = O(log k), s = O(k log k) and k sufficiently large.     

New regular embeddings of n‐cubes Qn

We investigate highly symmetrical embeddings of the n‐dimensional cube Q_n into orientable compact surfaces which we call regular embeddings of Q_n. We derive some general results and construct some new families of regular embeddings of Q_n. In particular, for n = 1, 2,3(mod 4), we classify the regular embeddings of Q_n which can be expressed as balanced Cayley maps. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 297–312, 2004     

Any Diophantine quintuple contains a regular Diophantine quadruple

A set {a₁,…,am} of m distinct positive integers is called a Diophantine m-tuple if aiaj+1 is a perfect square for all i, j with 1?i<j?m. It is conjectured that if {a,b,c,d} is a Diophantine quadruple with a<b<c<d, then d=d₊, where d₊=a+b+c+2abc+2rst and , , . In this paper, we show that if {a,b,c,d,e} is a Diophantine quintuple with a<b<c<d<e, then d=d₊.