On multipliers of polynomial addition sets

Let G be a group of order v, and f(x) be a nonzero integral polynomial. A (v, k, f(x))-polynomial addition set in G is a subset D of G with k distinct elements such that f(Σ_d?Dd) = λΣ_g?Gg for some integer λ. We discuss the multipliers of polynomial addition sets. The structure of some polynomial addition sets is studied, and in particular, we give a complete characterization of the case where G is cyclic and f(x) is irreducible.     

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).     

Degree sets for digraphs

The degree setD _D of a digraphD is the set of outdegrees of the vertices ofD. For a finite, nonempty setS of nonnegative integers, it is shown that there exists an asymmetric digraph (oriented graph)D such thatD _D =S. Furthermore, the minimum order of such a digraphD is determined. Also, given two finite sequences of nonnegative integers, a necessary and sufficient condition is provided for which these sequences are the outdegree sequences of the two sets of an asymmetric bipartite digraph.     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.     

Cyclotomy and addition sets

In this paper, we develop methods to solve the polynomial congruence θ(x)θ(x^g) ≡ d + λ(1 + x +… + x^p?1) (mod x^p ? 1), where p is an odd prime and θ(x) is a polynomial with nonnegative integral coefficients. Using these methods, we construct some new addition sets that are the unions of index classes for some primes p. We also establish the nonexistence of both the (95, 10, 1, 18)-addition set and the (95, 10, 1, 56)-addition set.     

Polynomial kernels for deletion to classes of acyclic digraphs

We consider the problem to find a set $X$ of vertices (or arcs) with $\left|X\right|\le k$ in a given digraph $G$ such that $D=G-X$ is an acyclic digraph. In its generality, this is Directed Feedback Vertex Set (or Directed Feedback Arc Set); the existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider the vertex deletion problem with an additional restriction on $D$, namely that $D$ must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of the above three restrictions we can obtain a kernel with $k^{O\left(1\right)}$ vertices on general digraphs. We also show that the arc deletion problem with the first two restrictions (out-forest and out-tree) can be solved in polynomial time; this contrasts the status of the vertex deletion problem of these restrictions, which is $\mathrm{NP}$-hard even for acyclic digraphs. The arc and vertex deletion problem with the third restriction (pumpkin), however, can be solved in polynomial time for acyclic digraphs, but becomes $\mathrm{NP}$-hard for general digraphs. We believe that the idea of restricting $D$ could yield new insights towards resolving the status of Directed Feedback Vertex Set.     

On the greedoid polynomial for rooted graphs and rooted digraphs

We examine some properties of the 2-variable greedoid polynomial f(G·,t,z) when G is the branching greedoid associated to a rooted graph or a rooted directed graph. For rooted digraphs, we show a factoring property of f(G·,t,z) determines whether or not the rooted digraph has a directed cycle. © 1993 John Wiley & Sons, Inc.     

Polynomial configurations in difference sets

We prove a quantitative result on the existence of linearly independent polynomial configurations in the difference set of sparse subsets of the integers. This result is achieved by first establishing a higher dimensional analogue of a theorem of Sárközy and then applying a simple lifting argument.     

Perfect addition sets

A subset S of Z_n is called a perfect addition set if the form x+y, for x≠ y in S, does not represent 0 and represents all non-zero elements the same number of times. The known perfect addition sets with 1?2 elements are (up to equivalence) one for each prime n=4a+3>3 and one each for n=2,4. It is shown that there are no others with 21>n?9, or with l divisible by 5; and there are some other restrictions.     

多项式组的特征分解

任一多项式理想的特征对是指由该理想的约化字典序Grobner基G和含于其中的极小三角列C构成的有序对(G,C).当C为正则列或正规列时,分别称特征对(G,C)为正则的或正规的.当G生成的理想与C的饱和理想相同时,称特征对(G,C)为强的.一组多项式的(强)正则或(强)正规特征分解是指将该多项式组分解为有限多个(强)正则或(强)正规特征对,使其满足特定的零点与理想关系.本文简要回顾各种三角分解及相应零点与理想分解的理论和方法,然后重点介绍(强)正则与(强)正规特征对和特征分解的性质,说明三角列、Ritt特征列和字典序Grobner基之间的内在关联,建立特征对的正则化定理以及正则、正规特征对的强化方法,进而给出两种基于字典序Grobner基计算、按伪整除关系分裂和构建、商除可除理想等策略的(强)正规与(强)正则特征分解算法.这两种算法计算所得的强正规与强正则特征对和特征分解都具有良好的性质,且能为输入多元多项式组的零点提供两种不同的表示.本文还给出示例和部分实验结果,用以说明特征分解方法及其实用性和有效性.     

Extremal results on feedback arc sets in digraphs

For an oriented graph $G$, let $\beta (G)$ denote the size of a minimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any $m$-edge oriented graph $G$ satisfies $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$. We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$, the bound $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$ is sharp as a function of $m$ if $B$ is not bipartite, but the exponent $3/4$ in the lower order term can be improved if $B$ is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in $[3/4,1]$ is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets.     

Piecewise parametric polynomial fuzzy sets

We present a scheme for tractable parametric representation of fuzzy set membership functions based on the use of a recursive monotonic hierarchy that yields different polynomial functions with different orders. Polynomials of the first order were found to be simple bivalent sets, while the second order polynomials represent the typical saw shape triangles. Higher order polynomials present more diverse membership shapes. The approach demonstrates an enhanced method to manage and fit the profile of membership functions through the access to the polynomials order, the number and the multiplicity of anchor points as wells as the uniformity and periodicity features used in the approach. These parameters provide an interesting means to assist in fitting a fuzzy controller according to system requirements. Besides, the polynomial fuzzy sets have tractable characteristics concerning the continuity and differentiability that depend on the order of the polynomials. Higher order polynomials can be differentiated as many times as the order of the polynomial less the multiplicity of the anchor points. An algorithmic optimization approach using the steepest descent method is introduced for fuzzy controller tuning. It was shown that the controller can be optimized to model a certain output within small number of iterations and very small error margins. The mathematics generated by the approach is consistent and can be simply generalized to standard applications. The recursive propagation was noticed for its clarity and ease of calculations. Further, the degree of association between the sets is not limited to the neighbors as in traditional applications; instead, it may extend beyond.Such approach can be useful in dynamic fuzzy sets for adaptive modeling in view of the fact that the shape parameters can be easily altered to get different profiles while keeping the math unchanged. Hypothetically, any shape of membership functions under the partition of unity constraint can be produced. The significance of the mentioned characteristics of such modeling can be observed in the field of combinatorial and continuous parameter optimization, automated tuning, optimal fuzzy control, fuzzy-neural control, membership function fitting, adaptive modeling, and many other fields that require customized as well as standard fuzzy membership functions. Experimental work of different scenarios with diverse fuzzy rules and polynomial sets has been conducted to verify and validate our results.     

On polynomial sets of classS k,and sets of rankk

Summary Al-Salam and Verma introduced the class S^k of polynomial sets, and characterized such sets by their generating functions. Here we define a class V^k of sets of rank k by means of recurrence relations, and show that S^k ⊂ V^k; and we characterize those sets of S^k, and of V^k, that are orthogonal. Entrata in Redazione il 24 giugno 1977.     

On Diophantine sets over polynomial rings

We prove that the recursively enumerable relations over a polynomial ring , where is the ring of integers in a totally real number field, are exactly the Diophantine relations over .