SOLUTION OF A RESEARCH PROBLEM ON TREES OF SUBSETS

ＳＯＬＵＴＩＯＮＯＦＡＲＥＳＥＡＲＣＨＰＲＯＢＬＥＭＯＮＴＲＥＥＳＯＦＳＵＢＳＥＴＳ ＷＵＳＨＩＱＵＡＮＡｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｓｏｌｖｅａｒｅｓｅａｒｃｈｐｒｏｂｌｅｍｏｎｔｒｅｅｓｏｆｓｕｂｓｅｔｓｐｏｓｅｄｂｙＦ．Ｒ．Ｍｃ?..     

SOLUTION OF A RESEARCH PROBLEM

ＳＯＬＵＴＩＯＮＯＦＡＲＥＳＥＡＲＣＨＰＲＯＢＬＥＭＷＵＳＨＩＱＵＡＮ（巫世权）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ...     

Signed Langford sequences

We answer a question of Brown and Jordon (2021) [4] by proving the existence of signed Langford sequences of every possible order for each defect. Our proof is constructive, and the constructions are shown to have other interesting properties and connections to several conjectures concerning permutations and partial sums of sequences of elements from cyclic groups.     

Normal sequences over finite abelian groups

In this note, we obtain the structure of short normal sequences over a finite abelian p-group or a finite abelian group of rank two, thus answering positively a conjecture of Gao and Zhuang for various groups. The results obtained here improve all known results on this conjecture.     

On the index of minimal zero-sum sequences over finite cyclic groups

Let G be a cyclic group of order n?2 and a sequence over G. We say that S is a zero-sum sequence if and that S is a minimal zero-sum sequence if S is a zero-sum sequence and S contains no proper zero-sum sequence.The notion of the index of a minimal zero-sum sequence (see Definition 1.1) in G has been recently addressed in the mathematical literature. Let l(G) be the smallest integer t∈N such that every minimal zero-sum sequence S over G with length |S|?t satisfies index(S)=1. In this paper, we first prove that for n?8. Secondly, we obtain a new result about the multiplicity and the order of elements in long zero-sumfree sequences.     

Random suffix search trees

A random suffix search tree is a binary search tree constructed for the suffixes X_i = 0 · B_iB_i+1B_i+2… of a sequence B₁, B₂, B₃, … of independent identically distributed random b‐ary digits B_j. Let D_n denote the depth of the node for X_n in this tree when B₁ is uniform on ?_b. We show that for any value of b > 1, ??D_n = 2 log n + O(log²log n), just as for the random binary search tree. We also show that D_n/??D_n → 1 in probability. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Categories of exact sequences with projective middle terms

Let A be a finite-dimensional algebra over an algebraically closed field k,E the category of all exact sequences in A-mod,MP(respectively,MI)the full subcategory of E consisting of those objects with projective(respectively,injective)middle terms.It is proved that MP(respectively,MI)is contravariantly finite(respectively,covariantly finite)in E.As an application,it is shown that MP=MI is functorially finite and has Auslander-Reiten sequences provided A is selfinjective.     

Long zero-free sequences in finite cyclic groups

A sequence in an additively written abelian group is called zero-free if each of its nonempty subsequences has sum different from the zero element of the group. The article determines the structure of the zero-free sequences with lengths greater than n/2 in the additive group Z_n of integers modulo n. The main result states that for each zero-free sequence  of length ?>n/2 in Z_n there is an integer g coprime to n such that if denotes the least positive integer in the congruence class ga_i (modulo n), then . The answers to a number of frequently asked zero-sum questions for cyclic groups follow as immediate consequences. Among other applications, best possible lower bounds are established for the maximum multiplicity of a term in a zero-free sequence with length greater than n/2, as well as for the maximum multiplicity of a generator. The approach is combinatorial and does not appeal to previously known nontrivial facts.     

Degree conditions and degree bounded trees

We give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and A a vertex subset of G. We denote by σ_k(A) the minimum value of the degree sum in G of any k independent vertices in A and by w(G−A) the number of components in the induced subgraph G−A. Our main results are the following: (i) If σ_k(A)≥|V(G)|−1, then G contains a tree T with maximum degree at most k and A⊆V(T). (ii) If σ_k−w(G−A)(A)≥|A|−1, then G contains a spanning tree T such that d_T(x)≤k for every x∈A. These are generalizations of the result by Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Sem. Univ. Hamburg 43 (1975) 263-267] and the degree conditions are sharp.     

Sequences of consecutive smooth polynomials over a finite field

Given , we show that there are infinitely many sequences of consecutive -smooth polynomials over a finite field. The number of polynomials in each sequence is approximately .

     

Maximum weight independent set in trees

Computing a maximum independent set, weighted or unweighted, isNP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum weight independent set in trees. A divide and conquer approach based on centroid decomposition of trees is used to compute a maximum weight independent set withinO(n logn) time, wheren is the number of vertices in the tree. We introduce a notion of analternating tree which is crucial in obtaining a new independent set from the previous one.     

Essential cohomology of finite groups

In this paper we prove that a finite group G with Cohen-Macaulay mod p cohomology will have non-trivial undetectable elements in if and only if G is a p-group such that every element of order p in G is central. Applications and examples are also provided. Received: April 18, 1996     

On trees with real-rooted independence polynomial

The independence polynomial of a graph $G$ is

$I(G,x)=\sum _{k\ge 0}{i}_k\left(G\right)x^k,$

where $i_k\left(G\right)$ denotes the number of independent sets of $G$ of size $k$ (note that $i_0\left(G\right)=1$). In this paper we show a new method to prove real-rootedness of the independence polynomials of certain families of trees.In particular we will give a new proof of the real-rootedness of the independence polynomials of centipedes (Zhu’s theorem), caterpillars (Wang and Zhu’s theorem), and we will prove a conjecture of Galvin and Hilyard about the real-rootedness of the independence polynomial of the so-called Fibonacci trees.     

Counting degree sequences of spanning trees in bipartite graphs: A graph-theoretic proof

Given a bipartite graph with bipartition each spanning tree in has a degree sequence on and one on . Löhne and Rudloff showed that the number of possible degree sequences on equals the number of possible degree sequences on . Their proof uses a non-trivial characterization of degree sequences by -draconian sequences based on polyhedral results of Postnikov. In this paper, we give a purely graph-theoretic proof of their result.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Cyclic permutations and evolutionary trees

Given a tree with leaf set X, there are certain ways of arranging the elements of X in a circular order so that can be embedded in the plane and ‘preserve’ this ordering. We investigate some new combinatorial properties of these ‘circular orderings.’ We then use these properties to establish two results concerning dissimilarity maps on X that are induced by edge-weighted trees with leaf set X.     

Inverse sequences, rooted trees and their end spaces

In this paper we prove that if we consider the standard real metric on simplicial rooted trees then the category Tower-Set of inverse sequences can be described by means of the bounded coarse geometry of the naturally associated trees. Using this we give a geometrical characterization of Mittag-Leffler property in inverse sequences in terms of the metrically proper homotopy type of the corresponding tree and its maximal geodesically complete subtree. We also obtain some consequences in shape theory. In particular we describe some new representations of shape morphisms related to infinite branches in trees.     

Bounds of Gauss sums in finite fields

We consider Gauss sums of the form

with a nontrivial additive character of a finite field of elements of characteristic . The classical bound becomes trivial for . We show that, combining some recent bounds of Heath-Brown and Konyagin with several bounds due to Deligne, Katz, and Li, one can obtain the bound on which is nontrivial for the values of of order up to . We also show that for almost all primes one can obtain a bound which is nontrivial for the values of of order up to .