Biased partitions and judicious <Emphasis Type="Italic">k</Emphasis>-partitions of graphs

Let G = (V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1- p, let m_p(G) be the minimum of qe(V₁) +pe(V₂) over partitions V = V₁ ∪ V₂, where e(V_i) denotes the number of edges spanned by V_i. We show that if mp(G) = pqm-δ, then there exists a bipartition V₁, V₂ of G such that e(V₁) ≤ p²m - δ + p√m/2 + o(√m) and e(V₂) ≤ q²m - δ + q √m/2 + o(√m) for δ = o(m^2/3). This is sharp for complete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) = (1 - 1/k)m + α, then G admits a k-partition such that each vertex class spans at most m/k² - Ω(m/k^7.5) edges for α = Ω(m/k⁶). Both of the above improve the results of Bollobás and Scott.     

Self-maps of <Emphasis Type="Italic">S</Emphasis><Superscript>2</Superscript> homotopic to a smooth map with a single <Emphasis Type="Italic">n</Emphasis>-periodic point

We show for which (d,n) ∈ Z×N there exists a smooth self-map f:S² → S² so that deg(f)=d and Fix(fⁿ) is a point.     

An improved product construction for large sets of Kirkman triple systems

It has been shown by Lei, in his recent paper, that there exists a large set of Kirkman triple systems of order uv (LKTS(uv)) if there exist an LKTS(v), a TKTS(v) and an LR(u), where a TKTS(v) is a transitive Kirkman triple system of order v, and an LR(u) is a new kind of design introduced by Lei. In this paper, we improve this product construction by removing the condition “there exists a TKTS(v)”. Our main idea is to use transitive resolvable idempotent symmetric quasigroups instead of TKTS. As an application, we can combine the known results on LKTS and LR-designs to obtain the existence of an LKTS(3ⁿm(2·13^n₁+1)(2·13^n_t+1)) for n1, m{1,5,11,17,25,35,43,67,91,123}{2^2r+125^s+1 : r0,s0}, t0 and n_i1 (i=1,…,t).     

Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs

Let S₁ and S₂ be two (k-1)-subsets in a k-uniform hypergraph H. We call S₁ and S₂ strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S₁ ∩ e ≠∅ and S₂ ∩ e ≠∅ or e ⊆ S₁ ∪ S₂ or e ⊇ S₁ ∪ S₂, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k²-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.     

Solution to an extremal problem on bigraphic pairs with a <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connected realization

Let S=(a₁,...,a_m; b₁,...,b_n), where a₁,...,a_m and b₁,...,b_n are two nonincreasing sequences of nonnegative integers. The pair S=(a₁,...,a_m; b₁,...,b_n) is said to be a bigraphic pair if there is a simple bipartite graph G=(X ∪ Y, E) such that a₁,...,a_m and b₁,...,b_n are the degrees of the vertices in X and Y, respectively. Let Z₃ be the cyclic group of order 3. Define σ(Z₃, m, n) to be the minimum integer k such that every bigraphic pair S=(a₁,...,a_m; b₁,...,b_n) with a_m, b_n ≥ 2 and σ(S)=a₁ +... + a_m ≥ k has a Z₃-connected realization. For n=m, Yin[Discrete Math., 339, 2018-2026 (2016)] recently determined the values of σ(Z₃, m, m) for m ≥ 4. In this paper, we completely determine the values of σ(Z₃, m, n) for m ≥ n ≥ 4.     

<Emphasis Type="Italic">n</Emphasis>-transitivity of bisection groups of a Lie groupoid

The notion of n-transitivity can be carried over from groups of diffeomorphisms on a manifold M to groups of bisections of a Lie groupoid over M. The main theorem states that the n-transitivity is fulfilled for all n ∈ N by an arbitrary group of C^r-bisections of a Lie groupoid Γ of class C^r, where 1 ≤ r ≤ ω, under mild conditions. For instance, the group of all bisections of any Lie groupoid and the group of all Lagrangian bisections of any symplectic groupoid are n-transitive in the sense of this theorem. In particular, if Γ is source connected for any arrow γ ∈ Γ, there is a bisection passing through γ.     

The existence of Schröder designs with equal-sized holes

A holey Schröder design of type h₁^n₁h₂^n₂ … h_k^n_k (HSD(h₁^n₁h₂^n₂ … h_k^n_k)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h₁^n₁h₂^n₂ … h_k^n_k)) of order n with n_i missing subquasigroups (holes) of order h_i, (1 i k), which are disjoint and spanning, that is, Σ_{1 i k} n_ih_i = n. In this paper, it is shown that an HSD(hⁿ) exists if and only if h²n(n − 1) 0 (mod 4) with expceptions (h, n) ε {{(1,5),(1,9),(2,4)}} and the possible exception of (h, n) = (6,4).     

Full quadrature sums for pth powers of polynomials with Freud weights

In this paper, we provide a solution of the quadrature sum problem of R. Askey for a class of Freud weights. Let r> 0, b (− ∞, 2]. We establish a full quadrature sum estimate

1 p < ∞, for every polynomial P of degree at most n + rn^1/3, where W² is a Freud weight such as exp(−¦x¦), > 1, λ_jn are the Christoffel numbers, x_jn are the zeros of the orthonormal polynomials for the weight W², and C is independent of n and P. We also prove a generalisation, and that such an estimate is not possible for polynomials P of degree M = m(n) if m(n) = n + ξ_nn^1/3, where ξ_n → ∞ as n → ∞. Previous estimates could sum only over those x_jn with ¦x_jn¦ σx_1n, some fixed 0 < σ < 1.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

Large 2P3-free graphs with bounded degree

Let ex^* (D;H) be the maximum number of edges in a connected graph with maximum degree D and no induced subgraph H; this is finite if and only if H is a disjoint union of paths. If the largest component of such an H has order m, then ex^*(D; H) = O(D²ex^*(D; P_m)). Constructively, ex^*(D;qP_m) = Θ(gD²ex^*(D;P_m)) if q>1 and m> 2(Θ(gD²) if m = 2). For H = 2P₃ (and D 8), the maximum number of edges is if D is even and

Full-size image

if D is odd, achieved by a unique extremal graph.     

Bondage number of strong product of two paths

The bondage number b(G) of a graph G is the cardinality of a minimum set of edges whose removal from G results in a graph with a domination number greater than that of G. In this paper, we obtain the exact value of the bondage number of the strong product of two paths. That is, for any two positive integers m≥2 and n≥2, b(P_m?P_n) = 7 - r(m) - r(n) if (r(m), r(n)) = (1, 1) or (3, 3), 6 - r(m) - r(n) otherwise, where r(t) is a function of positive integer t, defined as r(t) = 1 if t ≡ 1 (mod 3), r(t) = 2 if t ≡ 2 (mod 3), and r(t) = 3 if t ≡ 0 (mod 3).     

A note on <Emphasis Type="Italic">n</Emphasis>! modulo <Emphasis Type="Italic">p</Emphasis>

Let p be a prime, \(\varepsilon >0\) and \(0<L+1<L+N < p\). We prove that if \(p^{1/2+\varepsilon }< N <p^{1-\varepsilon }\), then

$$\begin{aligned} \#\{n!\,\,({\mathrm{mod}} \,p);\,\, L+1\le n\le L+N\} > c (N\log N)^{1/2},\,\, c=c(\varepsilon )>0. \end{aligned}$$

We use this bound to show that any \(\lambda \not \equiv 0\ ({\mathrm{mod}}\, p)\) can be represented in the form \(\lambda \equiv n_1!\cdots n_7!\ ({\mathrm{mod}}\, p)\), where \(n_i=o(p^{11/12})\). This refines the previously known range for \(n_i\).

     

Existence of 1-Rotational <Emphasis Type="Italic">k</Emphasis>-Cycle Systems of the Complete Graph

We explicitly solve the existence problem for 1-rotational k-cycle systems of the complete graph K_v with v1 or k (mod 2k). For v1 (mod 2k) we have existence if and only if k is an odd composite number. For any odd k and vk (mod 2k), (except k3 and v15, 21 (mod 24)) a 1-rotational k-cycle system of K_v exists.Final version received: June 18, 2003     

Solvable block transitive automorphism groups of 2−(v,5,1) designs

Let G be a solvable block transitive automorphism group of a 2−(v,5,1) design and suppose that G is not flag transitive. We will prove that

(1) if G is point imprimitive, then v=21, and GZ₂₁:Z₆;

(2) if G is point primitive, then GAΓL(1,v) and v=p^a, where p is a prime number with p≡21 (mod 40), and a an odd integer.

     

Solvable <Emphasis Type="Italic">D</Emphasis><Subscript>2</Subscript>-groups

Let G be a finite group, Irr¹(G) be the set of nonlinear irreducible characters of G and cd¹(G) the set of degrees of the characters in Irr¹(G). A group G is said to be a D₂-group if|cd¹(G)|=|Irr¹(G)|-2. In this paper, we give a complete classification of solvable D₂-groups.     

Equivalent characterization of centralizers on <Emphasis Type="Italic">B</Emphasis>(<Emphasis Type="Italic">H</Emphasis>)

Let H be a Hilbert space with dim H≥2 and Z∈ß(H) be an arbitrary but fixed operator. In this paper we show that an additive map Φ:ß(H) → ß(H) satisfies Φ(AB)=Φ(A)B=AΦ(B) for any A,B∈ß(H) with AB=Z if and only if Φ(AB)=Φ(A)B=AΦ(B), ∀A, B∈ß(H), that is, Φ is a centralizer. Similar results are obtained for Hilbert space nest algebras. In addition, we show that Φ(A²)=AΦ(A)=Φ(A)A for any A∈ ß(H) with AA²=0 if and only if Φ(A)=AΦ(I)=Φ(I)A, ∀A∈ß(H), and generalize main results in Linear Algebra and its Application, 450, 243-249 (2014) to infinite dimensional case. New equivalent characterization of centralizers on ß(H) is obtained.     

On the <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>-conjecture for locally compact groups

Let G be a locally compact group. For 1 < p < ∞, it is well-known that f * g exists and belongs to L^p(G) for all f, g L^p (G) if and only if G is compact. Here, for 2 < p < ∞, we show that f * g exists for all f, g L^p(G) if and only if G is compact. We also show that this result does not remain true for 1 < p ≤ 2. Received: 23 April 2006     

Almost resolvable maximum packings of complete graphs with 5-cycles

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.     

Cubic vertex-transitive non-Cayley graphs of order 12<Emphasis Type="Italic">p</Emphasis>

A graph is said to be vertex-transitive non-Cayley if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive non-Cayley graphs of order 12p, where p is a prime, is given. As a result, there are 11 sporadic and one infinite family of such graphs, of which the sporadic ones occur when p equals 5, 7 or 17, and the infinite family exists if and only if p ≡ 1 (mod 4), and in this family there is a unique graph for a given order.     

An extension theorem for t-designs

In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an S_λ(t,k,v) such that

then there exists an S_λ(v−t+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns S_λ(t,k,v). Moreover, if B_i and B_j are any two blocks belonging to two distinct such subdesigns, then d|B_i∩B_j|<k−h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an S_λ(t,k,v) such that

where m=min{s,v−k} and n=min{i,t}, then there exists an

having pairwise disjoint subdesigns S_λ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs.