Difference Covering Arrays and Pseudo-Orthogonal Latin Squares

A pair of Latin squares, A and B, of order n, is said to be pseudo-orthogonal if each symbol in A is paired with every symbol in B precisely once, except for one symbol with which it is paired twice and one symbol with which it is not paired at all. A set of t Latin squares, of order n, are said to be mutually pseudo-orthogonal if they are pairwise pseudo-orthogonal. A special class of pseudo-orthogonal Latin squares are the mutually nearly orthogonal Latin squares (MNOLS) first discussed in 2002, with general constructions given in 2007. In this paper we develop row complete MNOLS from difference covering arrays. We will use this connection to settle the spectrum question for sets of 3 mutually pseudo-orthogonal Latin squares of even order, for all but the order 146.     

Existence of saddle solutions of a nonlinear elliptic equation involving <Emphasis Type="Italic">p</Emphasis>-Laplacian in more even-dimensional spaces

We show that there exist saddle solutions of the nonlinear elliptic equation involving the p-Laplacian, p > 2, -Δ _p u = f(u) in R^2m for all dimensions satisfying 2m ≥ p, by using sub-supersolution method. The existence of saddle solutions of the above problem was known only in dimensions 2m ≥ 2p.     

Pentavalent symmetric graphs of order 2p3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.     

Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization

Recently, the alternating direction method of multipliers (ADMM) has found many efficient applications in various areas; and it has been shown that the convergence is not guaranteed when it is directly extended to the multiple-block case of separable convex minimization problems where there are m ≥ 3 functions without coupled variables in the objective. This fact has given great impetus to investigate various conditions on both the model and the algorithm’s parameter that can ensure the convergence of the direct extension of ADMM (abbreviated as “e-ADMM”). Despite some results under very strong conditions (e.g., at least (m ? 1) functions should be strongly convex) that are applicable to the generic case with a general m, some others concentrate on the special case of m = 3 under the relatively milder condition that only one function is assumed to be strongly convex. We focus on extending the convergence analysis from the case of m = 3 to the more general case of m ≥ 3. That is, we show the convergence of e-ADMM for the case of m ≥ 3 with the assumption of only (m ? 2) functions being strongly convex; and establish its convergence rates in different scenarios such as the worst-case convergence rates measured by iteration complexity and the globally linear convergence rate under stronger assumptions. Thus the convergence of e-ADMM for the general case of m ≥ 4 is proved; this result seems to be still unknown even though it is intuitive given the known result of the case of m = 3. Even for the special case of m = 3, our convergence results turn out to be more general than the existing results that are derived specifically for the case of m = 3.     

On Substructure Densities of Hypergraphs

A real number α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c > 0 such that for any ∈ > 0 and any integer m ≥ r, there exists an integer n ₀ such that any r-uniform graph with n > n ₀ vertices and density ≥ α + ∈ contains a subgraph with m vertices and density ≥ α + c. It follows from a fundamental theorem of Erdös and Stone that every α ∈ [0, 1) is a jump for r = 2. Erdös also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3 and asked whether every number in [0, 1) is a jump for r ≥ 3 as well. Frankl and Rödl gave a negative answer by showing a sequence of non-jumps for every r ≥ 3. Recently, more non-jumps were found for some r ≥ 3. But there are still a lot of unknowns on determining which numbers are jumps for r ≥ 3. The set of all previous known non-jumps for r = 3 has only an accumulation point at 1. In this paper, we give a sequence of non-jumps having an accumulation point other than 1 for every r ≥ 3. It generalizes the main result in the paper ‘A note on the jumping constant conjecture of Erdös’ by Frankl, Peng, Rödl and Talbot published in the Journal of Combinatorial Theory Ser. B. 97 (2007), 204–216.     

Planar Posets,Dimension, Breadth and the Number of Minimal Elements

In recent years, researchers have shown renewed interest in combinatorial properties of posets determined by geometric properties of its order diagram and topological properties of its cover graph. In most cases, the roots for the problems being studied today can be traced back to the 1970’s, and sometimes even earlier. In this paper, we study the problem of bounding the dimension of a planar poset in terms of the number of minimal elements, where the starting point is the 1977 theorem of Trotter and Moore asserting that the dimension of a planar poset with a single minimal element is at most 3. By carefully analyzing and then refining the details of this argument, we are able to show that the dimension of a planar poset with t minimal elements is at most 2t + 1. This bound is tight for t = 1 and t = 2. But for t ≥ 3, we are only able to show that there exist planar posets with t minimal elements having dimension t + 3. Our lower bound construction can be modified in ways that have immediate connections to the following challenging conjecture: For every d ≥ 2, there is an integer f(d) so that if P is a planar poset with dim(P) ≥ f(d), then P contains a standard example of dimension d. To date, the best known examples only showed that the function f, if it exists, satisfies f(d) ≥ d + 2. Here, we show that lim _d→∞ f(d)/d ≥ 2.     

The Existence and Application of Strongly Idempotent Self-orthogonal Row Latin Magic Arrays

Let N = {0, 1, · · ·, n ? 1}. A strongly idempotent self-orthogonal row Latin magic array of order n (SISORLMA(n) for short) based on N is an n × n array M satisfying the following properties: (1) each row of M is a permutation of N, and at least one column is not a permutation of N; (2) the sums of the n numbers in every row and every column are the same; (3) M is orthogonal to its transpose; (4) the main diagonal and the back diagonal of M are 0, 1, · · ·, n ? 1 from left to right. In this paper, it is proved that an SISORLMA(n) exists if and only if n ? {2, 3}. As an application, it is proved that a nonelementary rational diagonally ordered magic square exists if and only if n ? {2, 3}, and a rational diagonally ordered magic square exists if and only if n ≠ 2.     

Existence of generalized Latin squares which are not embeddable in any group

Let n be a positive integer. A generalized Latin square of order n is an \(n\times n\) matrix such that the elements in each row and each column are distinct. In this paper, we show that for any integer \(n\ge 6\) and any integer m where \(m\in \left\{ n, n+1, \dots , \frac{n(n+1)}{2}-2\right\} \), there exists a commutative generalized Latin square of order n with m distinct elements which is not embeddable in any group. In addition, we show that for any integer \(r\ge 3\) and any integer s where \(s\in \{ r, r+1, \dots , r^2-2\}\), there exists a non-commutative generalized Latin square of order r with s distinct elements which is not embeddable in any group.     

Regularity in the Local CR Embedding Problem

We consider a formally integrable, strictly pseudoconvex CR manifold M of hypersurface type, of dimension 2n?1≥7. Local CR, i.e., holomorphic, embeddings of M are known to exist from the works of Kuranishi and Akahori. We address the problem of regularity of the embedding in standard Hölder spaces C ^a (M), a∈R. If the structure of M is of class C ^m , m∈Z, 4≤m≤∞, we construct a local CR embedding near each point of M. This embedding is of class C ^a , for every a, 0≤a<m+(1/2). Our method is based on Henkin’s local homotopy formula for the embedded case, some very precise estimates for the solution operators in it, and a substantial modification of a previous Nash–Moser argument due to the second author.     

Complexity of function systems over a finite field in the class of polarized polynomial forms

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L _q ^PPF (n,m) = q ⁿ for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L₂^PPF (n,m) = 2 ⁿ and L₃^PPF (n,m) = 3 ⁿ for all n ≥ 1 and m ≥ 2.     

Intersection of Hamming codes avoiding Hamming subcodes

We prove that given a binary Hamming code \({{\mathcal{H}}^n}\) of length n = 2 ^m ? 1, m ≥ 3, or equivalently a projective geometry PG(m ? 1, 2), there exist permutations \({\pi \in \mathcal{S}_n}\) , such that \({{\mathcal{H}}^n}\) and \({\pi({\mathcal{H}}^n)}\) do not have any Hamming subcode with the same support, or equivalently the corresponding projective geometries do not have any common flat. The introduced permutations are called AF permutations. We study some properties of these permutations and their relation with the well known APN functions.     

Dual submanifolds in rational homology spheres

Let Σ be a simply connected rational homology sphere. A pair of disjoint closed submanifolds M_+, M_-? Σ are called dual to each other if the complement Σ-M_+ strongly homotopy retracts onto M_- or vice-versa. In this paper, we are concerned with the basic problem of which integral triples(n; m_+, m-) ∈ N~3 can appear, where n = dimΣ-1 and m_± = codim M_±-1. The problem is motivated by several fundamental aspects in differential geometry.(i) The theory of isoparametric/Dupin hypersurfaces in the unit sphere S~(n+1) initiated by′Elie Cartan, where M_± are the focal manifolds of the isoparametric/Dupin hypersurface M ? S~(n+1), and m± coincide with the multiplicities of principal curvatures of M.(ii) The Grove-Ziller construction of non-negatively curved Riemannian metrics on the Milnor exotic spheres Σ,i.e., total spaces of smooth S~3-bundles over S~4 homeomorphic but not diffeomorphic to S~7, where M_± =P_±×_(SO(4))S~3, P → S~4 the principal SO(4)-bundle of Σ and P_± the singular orbits of a cohomogeneity one SO(4) × SO(3)-action on P which are both of codimension 2.Based on the important result of Grove-Halperin, we provide a surprisingly simple answer, namely, if and only if one of the following holds true:· m_+ = m_-= n;· m_+ = m_-=1/3n ∈ {1, 2, 4, 8};· m_+ = m_-=1/4n ∈ {1, 2};· m_+ = m_-=1/6n ∈ {1, 2};·n/(m_++m_-)= 1 or 2, and for the latter case, m_+ + m_-is odd if min(m_+, m_-)≥2.In addition, if Σ is a homotopy sphere and the ratio n/(m_++m_-)= 2(for simplicity let us assume 2 m_- m_+),we observe that the work of Stolz on the multiplicities of isoparametric hypersurfaces applies almost identically to conclude that, the pair can be realized if and only if, either(m_+, m_-) =(5, 4) or m_+ + m_-+ 1 is divisible by the integer δ(m_-)(see the table on Page 1551), which is equivalent to the existence of(m_--1) linearly independent vector fields on the sphere S~(m_++m_-)by Adams' celebrated work. In contrast, infinitely many counterexamples are given if Σ is a rational homology sphere.     

On the Strong <Emphasis Type="Italic">n</Emphasis>-partite Tournaments with Exactly Two Cycles of Length <Emphasis Type="Italic">n</Emphasis> − 1

Gutin and Rafiey (Australas J. Combin. 34 (2006), 17-21) provided an example of an n-partite tournament with exactly n ? m + 1 cycles of length of m for any given m with 4 ≤ m ≤ n, and posed the following question. Let 3 ≤ m ≤ n and n ≥ 4. Are there strong n-partite tournaments, which are not themselves tournaments, with exactly n ? m + 1 cycles of length m for two values of m? In the same paper, they showed that this question has a negative answer for two values n ? 1 and n. In this paper, we prove that a strong n-partite tournament with exactly two cycles of length n ? 1 must contain some given multipartite tournament as subdigraph. As a corollary, we also show that the above question has a negative answer for two values n ? 1 and any l with 3 ≤ l ≤ n and l ≠ n ? 1.     

On Jumping Densities of Hypergraphs

A number \({\alpha\in [0, 1)}\) is a jump for an integer r ≥ 2 if there exists a constant c > 0 such that for any family \({{\mathcal F}}\) of r-uniform graphs, if the Turán density of \({{\mathcal F}}\) is greater than α, then the Turán density of \({{\mathcal F}}\) is at least α + c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0, 1) is a jump for r = 2. Erd?s also showed that every number in [0, r!/r ^r ) is a jump for r ≥ 3. However, not every number in [0, 1) is a jump for r ≥ 3. In fact, Frankl and Rödl showed the existence of non-jumps for r ≥ 3. By a similar approach, more non-jumps were found for some r ≥ 3 recently. But there are still a lot of unknowns regarding jumps for hypergraphs. In this note, we show that if \({c\cdot{\frac{r!}{r^r}}}\) is a non-jump for r ≥ 3, then for every p ≥ r, \({c\cdot{\frac{p!}{p^p}}}\) is a non-jump for p.     

A note on the Structure of Turán Densities of Hypergraphs

Let r ≥ 2 be an integer. A real number α ∈ [0, 1) is a jump for r if there exists c > 0 such that no number in (α, α + c) can be the Turán density of a family of r-uniform graphs. A result of Erd?s and Stone implies that every α ∈ [0, 1) is a jump for r = 2. Erd?s asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.     

Dense 3-uniform hypergraphs containing a large clique

An r-uniform graph C is dense if and only if every proper subgraph G' of G satisfies λ(G') λ(G).,where λ(G) is the Lagrangian of a hypergraph G. In 1980's, Sidorenko showed that π(F), the Turán density of an γ-uniform hypergraph F is r! multiplying the supremum of the Lagrangians of all dense F-hom-free γ-uniform hypergraphs. This connection has been applied in the estimating Turán density of hypergraphs. When γ=2 the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph. However,when r ≥ 3, it becomes much harder to estimate the Lagrangians of γ-uniform hypergraphs and to characterize the structure of all dense γ-uniform graphs. The main goal of this note is to give some sufficient conditions for3-uniform graphs with given substructures to be dense. For example, if G is a 3-graph with vertex set [t] and m edges containing [t-1]~(3),then G is dense if and only if m≥{t-2 3)+(t-2 2)+1. We also give a sufficient condition on the number of edges for a 3-uniform hypergraph containing a large clique minus 1 or 2 edges to be dense.     

On the maximality of a set of mutually orthogonal Sudoku Latin Squares

The maximum number of mutually orthogonal Sudoku Latin squares (MOSLS) of order \(n=m^2\) is \(n-m\). In this paper, we construct for \(n=q^2\), q a prime power, a set of \(q^2-q-1\) MOSLS of order \(q^2\) that cannot be extended to a set of \(q^2-q\) MOSLS. This contrasts to the theory of ordinary Latin squares of order n, where each set of \(n-2\) mutually orthogonal Latin Squares (MOLS) can be extended to a set of \(n-1\) MOLS (which is best possible). For this proof, we construct a particular maximal partial spread of size \(q^2-q+1\) in \(\mathrm {PG}(3,q)\) and use a connection between Sudoku Latin squares and projective geometry, established by Bailey, Cameron and Connelly.     

On total colorings of some special 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we verify the total coloring conjecture for every 1-planar graph G if either Δ(G) ≥ 9 and g(G) ≥ 4, or Δ(G) ≥ 7 and g(G) ≥ 5, where Δ(G) is the maximum degree of G and g(G) is the girth of G.     

The Shape of Orthogonal Cycles in Three Dimensions

Let σ be a directed cycle whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that σ is a shape cycle. We consider the following problem. Does there exist an orthogonal representation Γ of σ in 3D space such that no two edges of Γ intersect except at common endpoints and such that each edge of Γ has the direction specified in σ? If the answer is positive, we say that σ is simple. This problem arises in the context of extending orthogonal graph drawing techniques from 2D to 3D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms.     

The unramified computation of Rankin–Selberg integrals expressed in terms of Bessel models for split orthogonal groups: Part I

In this paper, we compute the local integrals, with normalized unramified data, over a p-adic field F, arising from general Rankin–Selberg integrals for SO _m × GL_r+k+1, where the orthogonal group is split over F, \(k \leqslant \left[ {\frac{{m - 1}}{2}} \right]\), and the irreducible representation of SO _m (F) has a Bessel model with respect to an irreducible representation of the split orthogonal group SO_m?2k?1(F). Our proof is by “analytic continuation from the unramified computation in the generic case”. We let the unramified parameters of the representations involved vary, and express the local integrals in terms of the Whittaker models of the representations, which exist at points in general position. Then we apply analytic continuation and the known unramified computation in the generic case. We discuss some applications to poles of partial L-functions and functorial lifting.