Inheritance of hyper-duality in imprimitive Bose–Mesner algebras

We prove the following result concerning the inheritance of hyper-duality by block and quotient Bose–Mesner algebras associated with a hyper-dual pair of imprimitive Bose–Mesner algebras. Let and denote Bose–Mesner algebras. Suppose there is a hyper-duality ψ from the subconstituent algebra of with respect to p to the subconstituent algebra of with respect to . Also suppose that is imprimitive with respect to a subset of Hadamard idempotents, so is dual imprimitive with respect to the subset of primitive idempotents, where is the formal duality associated with ψ. Let denote the block Bose–Mesner algebra of on the block containing p, and let denote the quotient Bose–Mesner algebra of with respect to . Then there is a hyper-duality from the subconstituent algebra of with respect to p to the subconstituent algebra of with respect to .     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

Boundedness of generalized higher commutators of Marcinkiewicz integrals

Let (b) ＝ (b1,…,bm) be a finite family of locally integrable functions. Then,we introduce generalized higher commutator of Marcinkiwicz integral as follows:μ(b)Ω=(∫∞o|F(b)Ω,t(f)(x)|2et/t)1/2,whereF(b)Ω(f)(x)＝1/t∫|x-y|≤tΩ(x-y)/|x-y|n-1m∏j=1(bj(x)-bj(y))f(y)dy.When bj ∈(A)βj, 1≤j≤m, 0＜βj＜1,m∑j=1βj =β＜n, and Ω is homogeneous of degree zero and satisfies the cancelation condition, we prove that μ(b)Ω is bounded from Lp(Rn)to Ls(Rn), where 1 ＜ p ＜ n/β and 1/s = 1/p -β/n. Moreover, if Ω also satisfies some Lq-Dini condition, then μ(b)Ω is bounded from Lp(Rn) to (F)β,∞p(Rn) and on certain Hardy spaces. The article extends some known results.     

Matching graphs of hypercubes and complete bipartite graphs

Kreweras’ conjecture [G. Kreweras, Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Q_d can be extended to a Hamiltonian cycle of Q_d. We [Jiří Fink, Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97 (6) (2007) 1074–1076] proved this conjecture but here we present a simplified proof.The matching graph of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle of G. We show that the matching graph of a complete bipartite graph is bipartite if and only if n is even or n=1. We prove that is connected for n even and has two components for n odd, n≥3. We also compute distances between perfect matchings in .     

Stepanov-like almost automorphic solutions of nonautonomous semilinear evolution equations with delay

We consider the existence and uniqueness of a Stepanov-like almost automorphic solution to the nonautonomous semilinear evolution equations with a constant delay:

where , generates an exponentially stable evolution family {U(t,s)} and satisfies a Lipschitz condition with respect to the second argument.     

The maximum edit distance from hereditary graph properties

For a graph property , the edit distance of a graph G from , denoted , is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a graph satisfying . What is the largest possible edit distance of a graph on n vertices from ? Denote this distance by .A graph property is hereditary if it is closed under removal of vertices. In a previous work, the authors show that for any hereditary property, a random graph essentially achieves the maximal distance from , proving: with high probability. The proof implicitly asserts the existence of such , but it does not supply a general tool for determining its value or the edit distance.In this paper, we determine the values of and for some subfamilies of hereditary properties including sparse hereditary properties, complement invariant properties, (r,s)-colorability and more. We provide methods for analyzing the maximum edit distance from the graph properties of being induced H-free for some graphs H, and use it to show that in some natural cases G(n,1/2) is not the furthest graph. Throughout the paper, the various tools let us deduce the asymptotic maximum edit distance from some well studied hereditary graph properties, such as being Perfect, Chordal, Interval, Permutation, Claw-Free, Cograph and more. We also determine the edit distance of G(n,1/2) from any hereditary property, and investigate the behavior of as a function of p.The proofs combine several tools in Extremal Graph Theory, including strengthened versions of the Szemerédi Regularity Lemma, Ramsey Theory and properties of random graphs.     

Semifields of order with left nucleus and center

In [G. Marino, O. Polverino, R. Trombetti, On -linear sets of PG(3,q³) and semifields, J. Combin. Theory Ser. A 114 (5) (2007) 769–788] it has been proven that there exist six non-isotopic families (i=0,…,5) of semifields of order q⁶ with left nucleus and center , according to the different geometric configurations of the associated -linear sets. In this paper we first prove that any semifield of order q⁶ with left nucleus , right and middle nuclei and center is isotopic to a cyclic semifield. Then, we focus on the family by proving that it can be partitioned into three further non-isotopic families: , , and we show that any semifield of order q⁶ with left nucleus , right and middle nuclei and center belongs to the family .     

Polynomial-time approximation schemes for piercing and covering with applications in wireless networks

Let be a set of disks of arbitrary radii in the plane, and let be a set of points. We study the following three problems: (i) Assuming contains the set of center points of disks in , find a minimum-cardinality subset of (if exists), such that each disk in is pierced by at least h points of , where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming is such that for each there exists a point in whose distance from D's center is at most αr(D), where r(D) is D's radius and 0α<1 is a given constant, find a minimum-cardinality subset of , such that each disk in is pierced by at least one point of . We call this problem minimum discrete piercing with cores. (iii) Assuming is the set of center points of disks in , and that each covers at most l points of , where l is a constant, find a minimum-cardinality subset of , such that each point of is covered by at least one disk of . We call this problem minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+ε)-approximation for minimum discrete piercing (i.e., for arbitrary ).     

Decomposing complete edge-chromatic graphs and hypergraphs. Revisited

A d-graph is a complete graph whose edges are colored by d colors, that is, partitioned into d subsets some of which might be empty. We say that a d-graph is complementary connected (CC) if the complement to each chromatic component of is connected on V. We prove that every such d-graph contains a sub-d-graph Π or , where Π has four vertices and two non-empty chromatic components each of which is a P₄, while is a three-colored triangle. This statement implies that each Π- and -free d-graph is uniquely decomposable in accordance with a tree whose leaves are the vertices of V and the interior vertices of T are labeled by the colors 1,…d. Such a tree is naturally interpreted as a positional game form (with perfect information and without moves of chance) of d players I={1,…,d} and n outcomes V={v₁,…,v_n}. Thus, we get a one-to-one correspondence between these game forms and Π- and -free d-graphs. As a corollary, we obtain a characterization of the normal forms of positional games with perfect information and, in case d=2, several characterizations of the read-once Boolean functions. These results are not new; in fact, they are 30 and, in case d=2, even 40 years old. Yet, some important proofs did not appear in English.Gyárfás and Simonyi recently proved a similar decomposition theorem for the -free d-graphs. They showed that each -free d-graph can be obtained from the d-graphs with only two non-empty chromatic components by successive substitutions. This theorem is based on results by Gallai, Lovász, Cameron and Edmonds. We obtain some new applications of these results.     

A characterization of the natural embedding of the split Cayley hexagon in by intersection numbers

In this paper, we prove that a set of q⁵+q⁴+q³+q²+q+1 lines of with the properties that (1) every point of is incident with either 0 or q+1 elements of , (2) every plane of is incident with either 0, 1 or q+1 elements of , (3) every solid of is incident with either 0, 1, q+1 or 2q+1 elements of , and (4) every hyperplane of is incident with at most q³+3q²+3q members of , is necessarily the set of lines of a regularly embedded split Cayley generalized hexagon in .     

Sur le groupe d'automorphismes des géométries paraboliques de rang 1

The aim of this article is to prove the following result, which generalizes the Ferrand–Obata theorem, concerning the conformal group of a Riemannian manifold, and the Schoen–Webster theorem about the automorphism group of a strictly pseudo-convex CR structure: let M be a connected manifold endowed with a regular Cartan geometry, modelled on the boundary of the hyperbolic space of dimension d2 over , being , , or the octonions . If the automorphism group of M does not act properly on M, then M is isomorphic, as a Cartan geometry, to X, or X minus a point.     

Lattices generated by orbits of subspaces under finite singular pseudo-symplectic groups I

Let be the (2ν+1+l)-dimensional vector space over the finite field . In the paper we assume that is a finite field of characteristic 2, and the singular pseudo-symplectic groups of degree 2ν+1+l over . Let be any orbit of subspaces under . Denote by the set of subspaces which are intersections of subspaces in and the intersection of the empty set of subspaces of is assumed to be . By ordering by ordinary or reverse inclusion, two lattices are obtained. This paper studies the inclusion relations between different lattices, a characterization of subspaces contained in a given lattice , and the characteristic polynomial of .     

Configurations in abelian categories. II. Ringel–Hall algebras

This is the second in a series on configurations in an abelian category . Given a finite poset (I,), an (I,)-configuration (σ,ι,π) is a finite collection of objects σ(J) and morphisms ι(J,K) or in satisfying some axioms, where J,KI. Configurations describe how an object X in decomposes into subobjects.The first paper defined configurations and studied moduli spaces of (I,)-configurations in , using the theory of Artin stacks. It showed well-behaved moduli stacks of objects and configurations in exist when is the abelian category coh(P) of coherent sheaves on a projective scheme P, or mod- of representations of a quiver Q.Write for the vector space of -valued constructible functions on the stack . Motivated by the idea of Ringel–Hall algebras, we define an associative multiplication * on using pushforwards and pullbacks along 1-morphisms between configuration moduli stacks, so that is a -algebra. We also study representations of , the Lie subalgebra of functions supported on indecomposables, and other algebraic structures on .Then we generalize all these ideas to stack functions , a universal generalization of constructible functions, containing more information. When Extⁱ(X,Y)=0 for all and i>1, or when for P a Calabi–Yau 3-fold, we construct (Lie) algebra morphisms from stack algebras to explicit algebras, which will be important in the sequels on invariants counting τ-semistable objects in .     

On ternary Kloosterman sums modulo 12

Let K(a) denote the Kloosterman sum on . It is easy to see that for all . We completely characterize those for which , and . The simplicity of the characterization allows us to count the number of the belonging to each of these three classes. As a byproduct we offer an alternative proof for a new class of quasi-perfect ternary linear codes recently presented by Danev and Dodunekov.     

Tensor-product approximation to operators and functions in high dimensions

In recent papers tensor-product structured Nyström and Galerkin-type approximations of certain multi-dimensional integral operators have been introduced and analysed. In the present paper, we focus on the analysis of the collocation-type schemes with respect to the tensor-product basis in a high spatial dimension d. Approximations up to an accuracy are proven to have the storage complexity with q independent of d, where N is the discrete problem size. In particular, we apply the theory to a collocation discretisation of the Newton potential with the kernel , , d3. Numerical illustrations are given in the case of d=3.     

Removing even crossings on surfaces

In this paper we investigate how certain results related to the Hanani–Tutte theorem can be extended from the plane to surfaces. We give a simple topological proof that the weak Hanani–Tutte theorem is true on arbitrary surfaces, both orientable and non-orientable. We apply these results and the proof techniques to obtain new and old results about generalized thrackles, including that every bipartite generalized thrackle on a surface S can be embedded on S. We also extend to arbitrary surfaces a result of Pach and Tóth that allows the redrawing of a graph so as to remove all crossings with even edges. From this we can conclude that , the crossing number of a graph G on surface S, is bounded by , where is the odd crossing number of G on surface S. Finally, we prove that whenever , for any surface S.     

Levels of multi-continued fraction expansion of multi-formal Laurent series

The multi-continued fraction expansion of a multi-formal Laurent series is a sequence pair consisting of an index sequence and a multi-polynomial sequence . We denote the set of the different indices appearing infinitely many times in by H_∞, the set of the different indices appearing in by H₊, and call |H_∞| and |H₊| the first and second levels of , respectively. In this paper, it is shown how the dimension and basis of the linear space over F(z) (F) spanned by the components of are determined by H_∞ (H₊), and how the components are linearly dependent on the mentioned basis.     

Perfect packings with complete graphs minus an edge

Let denote the graph obtained from K_r by deleting one edge. We show that for every integer r≥4 there exists an integer n₀=n₀(r) such that every graph G whose order n≥n₀ is divisible by r and whose minimum degree is at least contains a perfect -packing, i.e. a collection of disjoint copies of which covers all vertices of G. Here is the critical chromatic number of . The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.     

Ore-type and Dirac-type theorems for matroids

Let M be a connected binary matroid having no -minor. Let be a collection of cocircuits of M. We prove there is a circuit intersecting all cocircuits of if either one of two things hold:

(i) For any two disjoint cocircuits and in it holds that .

(ii) For any two disjoint cocircuits and in it holds that .

Part (ii) implies Ore's Theorem, a well-known theorem giving sufficient conditions for the existence of a hamilton cycle in a graph. As an application of part (i), it is shown that if M is a k-connected regular matroid and has cocircumference c^*2k, then there is a circuit which intersects each cocircuit of size c^*−k+2 or greater.We also extend a theorem of Dirac for graphs by showing that for any k-connected binary matroid M having no -minor, it holds that for any k cocircuits of M there is a circuit which intersects them.     

Rigid tensegrity labelings of graphs

Tensegrity frameworks are defined on a set of points in and consist of bars, cables, and struts, which provide upper and/or lower bounds for the distance between their endpoints. The graph of the framework, in which edges are labeled as bars, cables, and struts, is called a tensegrity graph. It is said to be rigid in if it has an infinitesimally rigid realization in as a tensegrity framework. The characterization of rigid tensegrity graphs is not known for d≥2.A related problem is how to find a rigid labeling of a graph using no bars. Our main result is an efficient combinatorial algorithm for finding a rigid cable–strut labeling of a given graph in the case when d=2. The algorithm is based on a new inductive construction of redundant graphs, i.e. graphs which have a realization as a bar framework in which each bar can be deleted without increasing the degree of freedom. The labeling is constructed recursively by using labeled versions of some well-known operations on bar frameworks.