Existence of frame SOLS of type ab

An SOLS (self-orthogonal latin square) of order v with n_i missing sub-SOLS (holes) of order h_i (1ik), which are disjoint and spanning (i.e. ∑_i=1^k n_ih_i=v), is called a frame SOLS and denoted by FSOLS(h₁^n₁h₂^n₂ h_k^n_k). It has been proved that for b2 and n odd, an FSOLS(aⁿb¹) exists if and only if n4 and n1+2b/a. In this paper, we show the existence of FSOLS(aⁿb¹) for n even and FSOLS(aⁿ1¹) for n odd.     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

On H-Linked Graphs

For a fixed multigraph H, possibly containing loops, with V(H)={h₁, . . . , h_k}, we say a graph G is H-linked if for every choice of k vertices v₁, . . . , v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). This notion clearly generalizes the concept of k-linked graphs (as well as other properties). In this paper we determine, for a connected multigraph H and for any sufficiently large graph G, a sharp lower bound on δ(G) (depending upon H) such that G is H-linked.     

Optimal pairs of score vectors for positional scoring rules

Letw=(w ₁,,w _m ) andv=(v ₁,,v _m-1 ) be nonincreasing real vectors withw ₁>w _m andv ₁>v _m-1 . With respect to a lista ₁,,a _n of linear orders on a setA ofm3 elements, thew-score ofaA is the sum overi from 1 tom ofw _i times the number of orders in the list that ranka inith place; thev-score ofaA{b} is defined in a similar manner after a designated elementb is removed from everya _j .We are concerned with pairs (w, v) which maximize the probability that anaA with the greatestw-score also has the greatestv-score inA{b} whenb is randomly selected fromA{a}. Our model assumes that linear ordersa _j onA are independently selected according to the uniform distribution over them linear orders onA. It considers the limit probabilityP _m (w, v) forn that the element inA with the greatestw-score also has the greatestv-score inA{b}.It is shown thatP _m (m,v) takes on its maximum value if and only if bothw andv are linear, so thatw _i –w _i+1=w _i+1–w _i+2 forim–2, andv _i –v _i+1 =v _i+1 –v _i+2 forim–3. This general result for allm3 supplements related results for linear score vectors obtained previously form{3,4}.     

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

On H‐immersions

For a fixed multigraph H, possibly containing loops, with V(H) = {h₁,…, h_k}, we say a graph G is H‐linked if for every choice of k vertices v₁,…,v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). An H‐immersion in G is similar except that the paths in G, playing the role of the edges of H, are only required to be edge disjoint. In this article, we extend the notion of an H‐linked graph by determining minimum degree conditions for a graph G to contain an H‐immersion with a bounded number of vertex repetitions on any choice of k vertices. In particular, we extend results found in [2,3,5]. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 245–254, 2008     

The k-orbit reconstruction and the orbit algebra

Let (G, W) be a permutation group on a finite set W = {w ₁,..., w _n}. We consider the natural action of G on the set of all subsets of W. Let h ₀, h ₁,..., h _N be the orbits of this action. For each i, 1 i N, there exists k, 1 k n, such that h _i is a set of k-element subsets of W. In this case h _i is called a symmetrized k-orbit of the group (G, W) or simply a k-orbit. With a k-orbit h _i we associate a multiset H(h _i ) = % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyykJeoaaa!3690!\[\langle \]h _i ⁽¹⁾, h _i ⁽²⁾,..., h _i ^(k)% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOkJepaaa!36A1!\[\rangle \] of its (k – 1)-suborbits. Orbits h _i and h _j are called equivalent if H(h _i ) = H(h _j ). An orbit is reconstructible if it is equivalent to itself only. The paper concerns the k-orbit reconstruction problem and its connections with different problems in combinatorics. The technique developed is based on the notion of orbit and co-orbit algebras associated with a given permutation group (G, W).     

Robustness of positional scoring over subsets of alternatives

Positional score vectorsw=(w ₁,,w _m ) for anm-element setA, andv=(v ₁,,v _k ) for ak-element proper subsetB ofA, agree at a profiles of linear orders onA when the restriction toB of the ranking overA produced byw operating ons equals the ranking overB produced byv operating on the restriction ofs toB. Givenw ₁>w _mandv ₁>v _k , this paper examines the extent to which pairs of nonincreasing score vectors agree over sets of profiles. It focuses on agreement ratios as the number of terms in the profiles becomes infinite. The limiting agreement ratios that are considered for (m, k) in {(3,2),(4,2),(4,3)} are uniquely maximized by pairs of Borda (linear, equally-spaced) score vectors and are minimized when (w,v) is either ((1,0,,0),(1,,1,0)) or ((1,,,1,0),(1,0,,0)).This research was supported by the National Science Foundation, Grants SOC 75-00941 and SOC 77-22941.     

Minimum degree conditions for -linked graphs

For a fixed multigraph H with vertices w₁,…,w_m, a graph G is H-linked if for every choice of vertices v₁,…,v_m in G, there exists a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d^′ such that every n-vertex graph with minimum degree at least d^′ is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.     

The adaptable choosability number grows with the choosability number

The adaptable choosability number of a multigraph G, denoted ch_a(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that ch_a grows with ch, i.e. there is a function f tending to infinity such that ch_a(G)≥f(ch(G)).     

Investigating the exact integrability of the multiwave nonlinear Schrödinger equation

It is shown that the multiwave nonlinear Schrödinger equation describing the evolution of several quasimonochromatic waves having the same group velocities is not exactly integrable (in the sense that no infinite sequence of local conservation laws and symmetries exists). The exact integrability for systems of the form w _t ⁱ =α_iw _xx ⁱ +a _klm ⁱ w^kw^lw^m is investigated, where α_i are different from zero.     

Phase Transition in Vertex-Reinforced Random Walks on {\mathbb{Z}} with Non-linear Reinforcement

Vertex-reinforced random walk is a random process which visits a site with probability proportional to the weight w _k of the number k of previous visits. We show that if w _k ∼ k ^α, then there is a large time T ₀ such that after T ₀ the walk visits 2, 5, or ∞ sites when α < 1, = 1, or > 1, respectively. More general results are also proven.      

A symmetry relationship for a class of partitions

Let S(n, k, v) denote the number of vectors (a₀,…, a_n?1) with nonnegative integer components that satisfy a₀ + … + a_{n ? 1} = k and Σ_i=0^n?1ia_i ≡ v (mod n). Two proofs are given for the relation S(n, k, v) = S(k, n, v). The first proof is by algebraic enumeration while the second is by combinatorial construction.     

The increase of sums and products dependent on (y 1, …,y n ) by rearrangement of this set

LetF(u, v) be a symmetric real function defined forα<u, v<β and assume thatG(u, v, w)=F(u, v)+F(u, w)−F(v, w) is decreasing inv andw foru≦min (u, v). For any set (y)=(y ₁, …,y _n ),α<y _i <β, given except in arrangement Σ _i ^=1/n F(y _i ,y _i+1) wherey _n+1=y ₁) is maximal if (and under some additional assumptions only if) (y) is arranged in circular symmetrical order. Examples are given and an additional result is proved on the productΠ _i ^=1/n [(y2i−1y2i) ^m +α ₁(y _2i−1 y _2i ) ^m−1+ … +a _m ] wherea _k ≧0 and where the set (y)=(y ₁, ..,y _n ),y _i ≧0 is given except in arrangement. The problems considered here arose in connection with a theorem by A. Lehman [1] and a lemma of Duffin and Schaeffer [2]. This paper is part of the author’s Master of Science dissertation at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Professor E. Jabotinsky for their help in the preparation of this paper.     

Implications among linkage properties in graphs

Given a graph H with vertices w₁, …, w_m, a graph G with at least m vertices is H‐linked if for every choice of vertices v₁, …, v_m in G, there is a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i ). This concept generalizes the notions of k‐linked, k‐connected, and k‐ordered graphs. For graphs H₁ and H₂ with the same order that are not contained in stars, the property of being H₁‐linked implies that of being H₂‐linked if and only if H₂?H₁. The implication also holds when H₁ is obtained from H₂ by replacing an edge xy with an edge from y to a new vertex x′. Other instances of nonimplication are obtained, using a lemma that the number of vertices appearing in minimum vertex covers of a graph G is at most the vertex cover number plus the size of a maximum matching. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 327‐337, 2009     

On Cycle Sequences

. For each vertex v in a graph G, the maximum length of a cycle which passes through v is called the cycle number of v, denoted by c(v). A sequence a ₁,a ₂,…,a _n of nonnegative integers is called a cycle sequence of a graph G if the vertices of G can be labeled as v ₁,v ₂,…,v _n such that a _i =c(v _i ) for 1≤i≤n. We give some sufficient and necessary conditions for a sequence to be a cycle sequence. We can thereby derive a polynomial time procedure for recognizing cycle sequences. Received: July 14, 1997 Final version received: June 15, 1998     

Simultaneous weighted sums of elements of finitely generated multiplicative groups

Let {G_j}_jεJ be a finite set of finitely generated subgroups of the multiplicative group of complex numbers C^x. Write H=∩ _jεJ G_j. Let n be a positive integer and a_ij a complex number for i = 1, ..., n and j ε J. Then there exists a set W with the following properties. The cardinality of W depends only on {G_j}_jεJ and n. If, for each jεJ, α has a representation α = Σ _iⁿ = ₁a _ijg_ij in elements g_ij of G_j, then α has a representation a= Σ_k=1ⁿ w_kh_k with w_kεW, h_k εH for k = 1,..., n. The theorem in this note gives information on such representations.     

On a conjecture concerningk-Hamilton-nice sequences

In this paper, we prove that a non-negative rational number sequence (a ₁,a ₂, ...,a _k+1) isk-Hamilton-nice, if (1)a _k+12, and (2) _j ^=1/h (i _j –1)k–1 implies for arbitraryi ₁,i ₂,...i _h {1,2,... ,k}. This result was conjectured by Guantao Chen and R.H. Schelp, and it generalizes several well-known sufficient conditions for graphs to be Hamiltonian.This project is supported by the National Natural Science Foundation of China.     

Oscillatory solutions of nonhomogeneous linear differential equations

The complex oscillation of nonhomogeneous linear differential equations with transcendental coefficients is discussed. Results concerning the equation f ^(k)+a _k−1 f ^(k−1)+...+a ₀ f=F where a ₀,...,a _k−i and Fare entire functions, possessing an oscillatory solution subspace in which all solutions (with at most one exception) have infinite exponent of convergence of zeros are obtained. All solutions of the equation are also characterized when the coefficients a ₀,a ₁,...,a _k−1 are polynomials and F=h exp (p ₀), where p ₀ is a polynomial and h is an entire function. Author supported by Max-Planck-Gesellschaft and by NSFC.