A note on linearization of actions of finitely semisimple Hopf algebras on local algebras

Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x₁, …, x_n of generators of the maximal ideal m such that h.x_i ε kx₁ + …+ kx_n for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact.     

A sufficient and necessary condition for an OWA bag mapping having the self-identity

A mapping ƒ : _n=1^∞Iⁿ → I is called a bag mapping having the self-identity if for every (x₁,…,x_n) ε _i=1^∞Iⁿ we have (1) ƒ(x₁,…,x_n) = ƒ(x_i1,…,x_in) for any arrangement (i₁,…,i_n) of {1,…,n}; monotonic; (3) ƒ(x₁,…,x_n, ƒ(x₁,…,x_n)) = ƒ(x₁,…,x_n). Let {ω_i,n : I = 1,…,n;n = 1,2,…} be a family of non-negative real numbers satisfying Σ_i=1ⁿω_i,n = 1 for every n. Then one calls the mapping ƒ : _i=1^∞Iⁿ → I defined as follows an OWA bag mapping: for every (x₁,…,x_n) ε _i=1^∞Iⁿ, ƒ(x₁,…,x_n) = Σ_i=1ⁿω_i,ny_i, where y_i is the it largest element in the set {x₁,…,x_n}. In this paper, we give a sufficient and necessary condition for an OWA bag mapping having the self-identity.     

Cycle decompositions of crowns

For an integer n3, the crown S_n⁰ is defined to be the graph with vertex set {x₀,x₁,…,x_n−1,y₀,y₁,…,y_n−1} and edge set {x_iy_j: 0i,jn−1, i≠j}. In this paper we give some sufficient conditions for the edge decomposition of the crown into isomorphic cycles.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

A generalization of carathéodory''s theorem

The following theorem is proved. If the sets and a εⁿ⁺¹_i=1 conv V_i, then there exist elements v_i ε V_i (i=1…,n+1) such that a ε conv{v₁,…,v_n+1}. This is generalization of Carathéodory's theorem. By applying this and similar results some open questions are answered.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

The smallest degree sum that yields potentially kCℓ-graphic sequences

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(_kC_ℓ,n) such that each n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(_kC_ℓ,n) has a realization G containing a cycle of length r for each r, krℓ.     

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.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

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).     

Boundedness and asymptotic behavior of the solutions of a fuzzy difference equation

In this paper we study the existence, the uniqueness, the boundedness and the asymptotic behavior of the positive solutions of the fuzzy difference equation x_n+1=∑_i=0^kA_i/x_n−i^p_i, where k{1,2,…,}, A_i, i{0,1,…,k}, are positive fuzzy numbers, p_i, i{0,1,…,k}, are positive constants and x_i, i{−k,−k+1,…,0}, are positive fuzzy numbers.     

A Helly theorem for geodesic convexity in strongly dismantlable graphs

A (finite or infinite) graph G is strongly dismantlable if its vertices can be linearly ordered x₀,…, x so that, for each ordinal β < , there exists a strictly increasing finite sequence (i_j)_{0 j n} of ordinals such that i₀ = β, i_n = and x_ij+1 is adjacent with x_ij and with all neighbors of x_ij in the subgraph ofG induced by {x_y: β γ }. We show that the Helly number for the geodesic convexity of such a graph equals its clique number. This generalizes a result of Bandelt and Mulder (1990) for dismantlable graphs. We also get an analogous equality dealing with infinite families of convex sets.     

Polyhedral graphs with extreme numbers of types of faces

A face F of a polyhedral graph G(V,E,F) is an a₁,a₂,…,a_l-face if is an l-gon and the degrees d(x_i) of the vertices x_iV incident with in the cyclic order are a_i,i=1,2,…,l. The lexicographic minimum b₁,b₂,…,b_l such that is a b₁,b₂,…,b_l-face is the type of . All polyhedral graphs having only one type of faces are listed. It is proved that the set of triangulations having only faces of different types is non-empty and finite.     

Length-bounded disjoint paths in planar graphs

The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r₁,s₁},…,{r_k,s_k} of G adjacent to the unbounded face, positive integers b₁,…,b_k and a function ; find: pairwise vertex-disjoint paths P₁,…,P_k such that for each i=1,…,k, P_i is a r_i−s_i-path and the sum of the l-length of all edges in P_i is at most b_i. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.     

Split and balanced colorings of complete graphs

An (r, n)-split coloring of a complete graph is an edge coloring with r colors under which the vertex set is partitionable into r parts so that for each i, part i does not contain K_n in color i. This generalizes the notion of split graphs which correspond to (2, 2)-split colorings. The smallest N for which the complete graph K_N has a coloring which is not (r, n)-split is denoted by ƒ_r(n). Balanced (r,n)-colorings are defined as edge r-colorings of KN such that every subset of [N/r] vertices contains a monochromatic K_n in all colors. Then g_r(n) is defined as the smallest N such that K_N has a balanced (r, n)-coloring. The definitions imply that f_r(n) g_r(n). The paper gives estimates and exact values of these functions for various choices of parameters.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Connectivity of generalized prisms over G

The problem of building larger graphs with a given graph as an induced subgraph is one which can arise in various applications and in particular can be important when constructing large communications networks from smaller ones. What one can conclude from this paper is that generalized prisms over G may provide an important such construction because the connectivity of the newly created graph is larger than that of the original (connected) graph, regardless of the permutation used.

For a graph G with vertices labeled 1,2,…, n and a permutation in S_n, the generalized prisms over G, (G) (also called a permutation graph), consists of two copies of G, say G_x and G_y, along with the edges (x_i, y_(i), for 1≤i≤n. The purpose of this paper is to examine the connectivity of generalized prisms over G. In particular, upper and lower bounds are found. Also, the connectivity and edge-connectivity are determined for generalized prisms over trees, cycles, wheels, n-cubes, complete graphs, and complete bipartite graphs. Finally, the connectivity of the generalized prism over G, (G), is determined for all in the automorphism group of G.     

Upper bounds for Ramsey numbers

The Ramsey number R(G₁,G₂,…,G_k) is the least integer p so that for any k-edge coloring of the complete graph K_p, there is a monochromatic copy of G_i of color i. In this paper, we derive upper bounds of R(G₁,G₂,…,G_k) for certain graphs G_i. In particular, these bounds show that R(9,9)6588 and R(10,10)23556 improving the previous best bounds of 6625 and 23854.