Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

On 4-semiregular 1-factorizations of complete graphs and complete bipartite graphs

A 4-semiregular 1-factorization is a 1-factorization in which every pair of distinct 1-factors forms a union of 4-cycles. LetK be the complete graphK _2nor the complete bipartite graphK _{n, n} .We prove that there is a 4-semiregular 1-factorization ofK if and only ifn is a power of 2 andn2, and 4-semiregular 1-factorizations ofK are isomorphic, and then we determine the symmetry groups. They are known for the case of the complete graphK _2n ,however, we prove them in a different method.     

Invariant Subspaces for Banach Space Operators with a Multiply Connected Spectrum

We consider a multiply connected domain where denotes the unit disk and denotes the closed disk centered at with radius r _j for j = 1, . . . , n. We show that if T is a bounded linear operator on a Banach space X whose spectrum contains ∂Ω and does not contain the points λ₁, λ₂, . . . , λ _n , and the operators T and r _j (T − λ _j I)⁻¹ are polynomially bounded, then there exists a nontrivial common invariant subspace for T ^* and (T − λ _j I)^*-1.     

Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs

We prove that every Eulerian orientation of K_m,n contains arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004     

Simple minimum coverings ofK n with copies ofK 4 −e

Summary AK ₄–e design of ordern is a pair (S, B), whereB is an edge-disjoint decomposition ofK _n (the complete undirected graph onn vertices) with vertex setS, into copies ofK ₄–e, the graph on four vertices with five edges. It is well-known [1] thatK ₄–e designs of ordern exist for alln 0 or 1 (mod 5),n 6, and that if (S, B) is aK ₄–e design of ordern then |B| =n(n – 1)/10.Asimple covering ofK _n with copies ofK ₄–e is a pair (S, C) whereS is the vertex set ofK _n andC is a collection of edge-disjoint copies ofK ₄–e which partitionE(K_n)P, for some . Asimple minimum covering ofK _n (SMCK _n) with copies ofK ₄–e is a simple covering whereP consists of as few edges as possible. The collection of edgesP is called thepadding. Thus aK ₄–e design of ordern isSMCK _n with empty padding.We show that forn 3 or 8 (mod 10),n 8, the padding ofSMCK _n consists of two edges and that forn 2, 4, 7 or 9 (mod 10),n 9, the padding consists of four edges. In each case, the padding may be any of the simple graphs with two or four edges respectively. The smaller cases need separate treatment:SMCK ₅ has four possible paddings of five edges each,SMCK ₄ has two possible paddings of four edges each andSMCK ₇ has eight possible paddings of four edges each.The recursive arguments depend on two essential ingredients. One is aK ₄–e design of ordern with ahole of sizek. This is a triple (S, H, B) whereB is an edge-disjoint collection of copies ofK ₄–e which partition the edge set ofK _n\K_k, whereS is the vertex set ofK _n, and is the vertex set ofK _k. The other essential is acommutative quasigroup with holes. Here we letX be a set of size 2n 6, and letX = {x ₁, x₂, ..., x_n} be a partition ofX into 2-element subsets, calledholes of size two. Then a commutative quasigroup with holesX is a commutative quasigroup (X, ) such that for each holex _i X, (x_i, ) is a subquasigroup. Such quasigroups exist for every even order 2n 6 [4].     

Extension to R + n+1 of singular integrals and fractional integrals

In this paper, a natural R ₊ ⁿ⁺¹ extension of singular integrals, i.e.,T _κ:f→K*φ _t *t with K a standard C-Z kernel and ϕ usual one, is investigated. One of the main results is: Let (dμ, udx) ∈C₁ and u-Mw, w∈A_∞, then T_k is of type (L^p(udx), L^p(dμ)). As a related topic, a maximal operator is proved to be of type , where , provided (dμ, udx) ∈C₁ and u∈ A_∞. Supported by National Science Foundation of China     

Asymptotic expansion of the log-likelihood function based on stopping times defined on a Markov process

Consider the parameter space Θ which is an open subset of ℝ ^k ,k≧1, and for each θ∈Θ, let the r.v.′sY _n ,n=0, 1, ... be defined on the probability space (X,A,P _θ) and take values in a Borel setS of a Euclidean space. It is assumed that the process {Y _n },n≧0, is Markovian satisfying certain suitable regularity conditions. For eachn≧1, let υ _n be a stopping time defined on this process and have some desirable properties. For 0 < τ _n → ∞ asn→∞, set h _n →h ∈R ^k , and consider the log-likelihood function of the probability measure with respect to the probability measure . Here is the restriction ofP _θ to the σ-field induced by the r.v.′sY ₀,Y ₁, ..., . The main purpose of this paper is to obtain an asymptotic expansion of in the probability sense. The asymptotic distribution of , as well as that of another r.v. closely related to it, is obtained under both and . This research was supported by the National Science Foundation, Grant MCS77-09574. Research supported by the National Science Foundation, Grant MCS76-11620.     

Some inequalities about mixed volumes

We prove inequalities about the quermassintegralsV _k (K) of a convex bodyK in ℝ ⁿ (here,V _k (K) is the mixed volumeV((K, k), (B _n ,n − k)) whereB _n is the Euclidean unit ball). (i) The inequality

Panconnected graphs II

A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that d_G(u, v)lp – 1, whered _G (u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected.     

On the number of subtrees for almost all graphs

In this article it is shown that the number of common edges of two random subtrees of K_n having r and s vertices, respectively, has a Poisson distribution with expectation 2λμ if $\mathop {\lim }\limits_{n \to \infty } r/n = \lambda$ and $\mathop {\lim }\limits_{n \to \infty } s/n = \mu$. Also, some estimations of the number of subtrees for almost all graphs are made by using Chebycheff's inequality. © 1994 John Wiley & Sons, Inc.     

Packing,covering and decomposing of a complete uniform hypergraph into delta-systems

Anh-uniform hypergraph generated by a set of edges {E ₁,...,E _c} is said to be a delta-system Δ(p,h,c) if there is ap-element setF such that ∇F|=p andE _i⌢E _j=F,∀i≠j. The main result of this paper says that givenp, h andc, there isn ₀ such that forn≥n ₀ the set of edges of a completeh-uniform hypergraphK _n ^h can be partitioned into subsets generating isomorphic delta-systems Δ(p, h, c) if and only if . This result is derived from a more general theorem in which the maximum number of delta-systems Δ(p, h, c) that can be packed intoK _n ^h and the minimum number of delta-systems Δ(p, h, c) that can cover the edges ofK _n ^h are determined for largen. Moreover, we prove a theorem on partitioning of the edge set ofK _n ^h into subsets generating small but not necessarily isomorphic delta-systems.     

A sufficient condition for graphs to be weaklyk-linked

We consider graphs, which are finite, undirected, without loops and in which multiple edges are possible. For each natural numberk letg(k) be the smallest natural numbern, so that the following holds:LetG be ann-edge-connected graph and lets ₁,...,s _k,t ₁,...,t _k be vertices ofG. Then for everyi {1,..., k} there existsa pathP _i froms _i tot _i, so thatP ₁,...,P _k are pairwise edge-disjoint. We prove      

A lower bound for the optimal crossing-free Hamiltonian cycle problem

Consider a drawing in the plane ofK _n , the complete graph onn vertices. If all edges are restricted to be straight line segments, the drawing is called rectilinear. Consider a Hamiltonian cycle in a drawing ofK _n . If no pair of the edges of the cycle cross, it is called a crossing-free Hamiltonian cycle (cfhc). Let (n) represent the maximum number of cfhc's of any drawing ofK _n , and (n) the maximum number of cfhc's of any rectilinear drawing ofK _n . The problem of determining (n) and (n), and determining which drawings have this many cfhc's, is known as the optimal cfhc problem. We present a brief survey of recent work on this problem, and then, employing a recursive counting argument based on computer enumeration, we establish a substantially improved lower bound for (n) and (n). In particular, it is shown that (n) is at leastk × 3.2684 ⁿ . We conjecture that both (n) and (n) are at mostc × 4.5 ⁿ .This research, part of which was conducted at Queen's University, was supported by an N.S.E.R.C. postgraduate scholarship.     

Representations of double coset hypergroups and induced representations

The principal goal of this paper is to investigate the representation theory of double coset hypergroups. IfK=G//H is a double coset hypergroup, representations ofK can canonically be obtained from those ofG. However, not every representation ofK originates from this construction in general, i.e., extends to a representation ofG. Properties of this construction are discussed, and as the main result it turns out that extending representations ofK is compatible with the inducing process (as introduced in [7]). It follows that a representation weakly contained in the left-regular representation ofK always admits an extension toG. Furthermore, we realize the Gelfand pair (where are a local field andR its ring of integers) as a polynomial hypergroup on ℕ₀ and characterize the (proper) subset of its dual consisting of extensible representations.     

Isoperimetric problems for convex bodies and a localization lemma

We study the smallest number ψ(K) such that a given convex bodyK in ℝ ⁿ can be cut into two partsK ₁ andK ₂ by a surface with an (n−1)-dimensional measure ψ(K) vol(K ₁)·vol(K ₂)/vol(K). LetM ₁(K) be the average distance of a point ofK from its center of gravity. We prove for the “isoperimetric coefficient” that

<Emphasis Type="Italic">c</Emphasis>*-Supplemented subgroups and <Emphasis Type="Italic">p</Emphasis>-nilpotency of finite groups

A subgroup H of a finite group G is said to be c*-supplemented in G if there exists a subgroup K such that G = HK and H ⋂ K is permutable in G. It is proved that a finite group G that is S ₄-free is p-nilpotent if N _G (P) is p-nilpotent and, for all x ∈ G\N _G (P), every minimal subgroup of is c*-supplemented in P and (if p = 2) one of the following conditions is satisfied: (a) every cyclic subgroup of of order 4 is c*-supplemented in P, (b) , (c) P is quaternion-free, where P a Sylow p-subgroup of G and is the p-nilpotent residual of G. This extends and improves some known results. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1011–1019, August, 2007.     

On polynomial automorphisms of spheres

Let K be an infinite field with characteristic different from two and (K) the n-sphere over K. We show that ambient polynomial automorphisms of (K) preserve the quadratic form x ₀² + ⋯ + x _n ² and the group Aut ((K ⁿ⁺¹, (K)) of such automorphisms of (K) is isomorphic to the (n + 1)-orthogonal group O(n + 1, K) provided K is real. Next, the restriction map Aut (K ³, (K)) → Aut ( (K)) yields a surjection provided K is an algebraically closed field as well. Furthermore, for any such a field K, there is an imbedding

Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph

Let G be a graph with n vertices, m edges and a vertex degree sequence (d ₁, d ₂,..., d _n ), where d ₁ ≥ d ₂ ≥ ... ≥ d _n . The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with

Near 2-factorizations of 2K n : Cycles of even length

We show that the edges of the complete multigraph 2K _{mk+ 1} can be partitioned intomk + 1 factors, each the union ofmk-cycles, for all evenk, k 4.Both authors are grateful to the Mathematics Department at Queen's University for the hospitality extended to them while visiting.The author acknowledges the financial support of the Natural Sciences and Engineering Research Council of Canada under Grant No. A7829.     

On A Hypergraph Turán Problem Of Frankl

Let be the 2k-uniform hypergraph obtained by letting P₁, . . .,P_r be pairwise disjoint sets of size k and taking as edges all sets P_i∪P_j with i ≠ j. This can be thought of as the ‘k-expansion’ of the complete graph K_r: each vertex has been replaced with a set of size k. An example of a hypergraph with vertex set V that does not contain can be obtained by partitioning V = V1 ∪V₂ and taking as edges all sets of size 2k that intersect each of V₁ and V₂ in an odd number of elements. Let denote a hypergraph on n vertices obtained by this construction that has as many edges as possible. For n sufficiently large we prove a conjecture of Frankl, which states that any hypergraph on n vertices that contains no has at most as many edges as . Sidorenko has given an upper bound of for the Tur′an density of for any r, and a construction establishing a matching lower bound when r is of the form 2^p+1. In this paper we also show that when r=2^p+1, any -free hypergraph of density looks approximately like Sidorenko’s construction. On the other hand, when r is not of this form, we show that corresponding constructions do not exist and improve the upper bound on the Turán density of to , where c(r) is a constant depending only on r. The backbone of our arguments is a strategy of first proving approximate structure theorems, and then showing that any imperfections in the structure must lead to a suboptimal configuration. The tools for its realisation draw on extremal graph theory, linear algebra, the Kruskal–Katona theorem and properties of Krawtchouck polynomials. * Research supported in part by NSF grants DMS-0355497, DMS-0106589, and by an Alfred P. Sloan fellowship.