On the phase transitions of (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">q</Emphasis>)-SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T _k (V) denote the set of all 2 ^k n ^k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T _k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and ε = ε(n) > 0 be such that εlnn/lnlnn→∞. Let k ≥ (1 + θ) log₂ n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that

$$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$

     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

<Emphasis Type="Italic">l</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis>,<Emphasis Type="Italic">s</Emphasis></Superscript>-Singular values and spectral radius of partially symmetric rectangular tensors

The real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. In this paper, we first study properties of l ^k,s -singular values of real rectangular tensors. Then, a necessary and sufficient condition for the positive definiteness of partially symmetric rectangular tensors is given. Furthermore, we show that the weak Perron-Frobenius theorem for nonnegative partially symmetric rectangular tensor keeps valid under some new conditions and we prove a maximum property for the largest l ^k,s -singular values of nonnegative partially symmetric rectangular tensor. Finally, we prove that the largest l ^k,s -singular value of nonnegative weakly irreducible partially symmetric rectangular tensor is still geometrically simple.     

The <Emphasis Type="Italic">p</Emphasis>-Adic order of the <Emphasis Type="Italic">k</Emphasis>-Fibonacci and <Emphasis Type="Italic">k</Emphasis>-Lucas numbers

Let (F _k,n ) _n and (L _k,n )n be the k-Fibonacci and k-Lucas sequence, respectively, which satisfies the same recursive relation a _n+1 = ka _n + a _n?1 with initial values F _k,0 = 0, F _k,1 = 1, L _k,0 = 2 and L _k,1 = k. In this paper, we characterize the p-adic orders ν _p (F _k,n ) and ν _p (L _k,n ) for all primes p and all positive integers k.     

Largest <Emphasis Type="Italic">H</Emphasis>-eigenvalue of uniform <Emphasis Type="Italic">s</Emphasis>-hypertrees

The k-uniform s-hypertree G = (V,E) is an s-hypergraph, where 1 ≤ s ≤ k - 1; and there exists a host tree T with vertex set V such that each edge of G induces a connected subtree of T. In this paper, some properties of uniform s-hypertrees are establised, as well as the upper and lower bounds on the largest H-eigenvalue of the adjacency tensor of k-uniform s-hypertrees in terms of the maximal degree Δ. Moreover, we also show that the gap between the maximum and the minimum values of the largest H-eigenvalue of k-uniform s-hypertrees is just Θ(Δ ^s/k ).     

Monochromatic Sinks in <Emphasis Type="Italic">k</Emphasis>-Arc Colored Tournaments

Let T be a tournament on n vertices whose arcs are colored with k colors. A 3-cycle whose arcs are colored with three distinct colors is called a rainbow triangle. A rainbow triangle dominated by any nonempty set of vertices is called a dominated rainbow triangle. We prove that when \(n\ge 5\), if T does not contain a dominated rainbow triangle and all 4- and 5-cycles of T are near-monochromatic, then T has a monochromatic sink. We also prove that when \(n\ge 4\), if T does not contain a dominated rainbow triangle and all 4-cycles are monochromatic, then T has a monochromatic sink. A semi-cycle is a digraph C that either is a cycle or contains an arc xy such that \(C-xy+yx\) is a cycle. We prove that if \(n\ge 4\) and all 4-semi-cycles of T are near-monochromatic, then T has a monochromatic sink. We also show if \(n\ge 5\) and all 5-semi-cycles of T are near-monochromatic, then T has a monochromatic sink.     

Some class 1 graphs on <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings

An edge-coloring of a graph G is an assignment of colors to all the edges of G. A g _c -coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least g(v) times. The maximum integer k such that G has a g _c -coloring with k colors is called the g _c -chromatic index of G and denoted by \(\chi\prime_{g_{c}}\)(G). In this paper, we extend a result on edge-covering coloring of Zhang and Liu in 2011, and give a new sufficient condition for a simple graph G to satisfy \(\chi\prime_{g_{c}}\)(G) = δ _g (G), where \(\delta_{g}\left(G\right) = min_{v\epsilon V (G)}\left\{\lfloor\frac{d\left(v\right)}{g\left(v\right)}\rfloor\right\}\).     

On <Emphasis Type="Italic">r</Emphasis>-recognition by prime graph of <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(3) where <Emphasis Type="Italic">p</Emphasis> is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then \({G\cong B_p(3)}\) or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then \({G\cong B_3(3), C_3(3), D_4(3)}\), or \({G/O_2(G)\cong {\rm Aut}(^2B_2(8))}\). As a corollary, the main result of the above paper is obtained.     

On a new property of <Emphasis Type="Italic">n</Emphasis>-poised and <Emphasis Type="Italic">G</Emphasis><Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets

In this paper we consider n-poised planar node sets, as well as more special ones, called G C _n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ? is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C _n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \)meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C _n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n ? 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C _n sets. At the end we present a conjecture concerning any k-node line.     

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

Strongly regular locally <Emphasis Type="Italic">GQ</Emphasis>(4,<Emphasis Type="Italic">t</Emphasis>)-graphs

Amply regular with parameters (v, k, λ, μ) we call an undirected graph with v vertices in which the degrees of all vertices are equal to k, every edge belongs to λ triangles, and the intersection of the neighborhoods of every pair of vertices at distance 2 contains exactly μ vertices. An amply regular diameter 2 graph is called strongly regular. We prove the nonexistence of amply regular locally GQ(4,t)-graphs with (t,μ) = (4, 10) and (8, 30). This reduces the classification problem for strongly regular locally GQ(4,t)-graphs to studying locally GQ(4, 6)-graphs with parameters (726, 125, 28, 20).     

The Relaxed Edge-Coloring Game and <Emphasis Type="Italic">k</Emphasis>-Degenerate Graphs

The (r, d)-relaxed edge-coloring game is a two-player game using r colors played on the edge set of a graph G. We consider this game on forests and more generally, on k-degenerate graphs. If F is a forest with Δ(F)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ?j and d≥2j+2 for 0≤j≤Δ?1. This both improves and generalizes the result for trees in Dunn, C. (Discret. Math. 307, 1767–1775, 2007). More broadly, we generalize the main result in Dunn, C. (Discret. Math. 307, 1767–1775, 2007) by showing that if G is k-degenerate with Δ(G)=Δ and j∈[Δ+k?1], then there exists a function h(k,j) such that Alice has a winning strategy for this game with r=Δ+k?j and d≥h(k,j).     

(<Emphasis Type="Italic">m</Emphasis>,<Emphasis Type="Italic">r</Emphasis>)-central Riordan arrays and their applications

For integers m > r ≥ 0, Brietzke (2008) defined the (m, r)-central coefficients of an infinite lower triangular matrix G = (d, h) = (d_n,k)_n,k∈N as d_{mn+r,(m?1)n+r}, with n = 0, 1, 2,..., and the (m, r)-central coefficient triangle of G as

$${G^{\left( {m,r} \right)}} = {\left( {{d_{mn + r,\left( {m - 1} \right)n + k + r}}} \right)_{n,k \in \mathbb{N}}}.$$

It is known that the (m, r)-central coefficient triangles of any Riordan array are also Riordan arrays. In this paper, for a Riordan array G = (d, h) with h(0) = 0 and d(0), h′(0) ≠ 0, we obtain the generating function of its (m, r)-central coefficients and give an explicit representation for the (m, r)-central Riordan array G^(m,r) in terms of the Riordan array G. Meanwhile, the algebraic structures of the (m, r)-central Riordan arrays are also investigated, such as their decompositions, their inverses, and their recessive expressions in terms of m and r. As applications, we determine the (m, r)-central Riordan arrays of the Pascal matrix and other Riordan arrays, from which numerous identities are constructed by a uniform approach.

     

<Emphasis Type="Italic">k</Emphasis>-invariant nets over an algebraic extension of a field <Emphasis Type="Italic">k</Emphasis>

Let K be an algebraic extension of a field k, let σ = (σ _ij ) be an irreducible full (elementary) net of order n ≥ 2 (respectively, n ≥ 3) over K, while the additive subgroups σ _ij are k-subspaces of K. We prove that all σij coincide with an intermediate subfield P, k ? P ? K, up to conjugation by a diagonal matrix.     

Universal zero-one <Emphasis Type="Italic">k</Emphasis>-law

The limit probabilities of first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. For any positive integer k ≥ 4 and any rational number t/s ∈ (0, 1), an interval with right endpoint t/s is found in which the zero-one k-law holds (the zero-one k-law describes the behavior of the probabilities of first-order properties expressed by formulas of quantifier depth at most k).Moreover, it is proved that, for rational numbers t/s with numerator not exceeding 2, the logarithm of the length of this interval is of the same order of smallness (as n→∞) as that of the length of the maximal interval with right endpoint t/s in which the zero-one k-law holds.     

Universal Cycle Packings and Coverings for <Emphasis Type="Italic">k</Emphasis>-Subsets of an <Emphasis Type="Italic">n</Emphasis>-Set

A cyclic sequence of elements of [n] is an (n, k)-Ucycle packing (respectively, (n, k)-Ucycle covering) if every k-subset of [n] appears in this sequence at most once (resp. at least once) as a subsequence of consecutive terms. Let \(p_{n,k}\) be the length of a longest (n, k)-Ucycle packing and \(c_{n,k}\) the length of a shortest (n, k)-Ucycle covering. We show that, for a fixed \(k,p_{n,k}={n\atopwithdelims ()k}-O(n^{\lfloor k/2\rfloor })\). Moreover, when k is not fixed, we prove that if \(k=k(n)\le n^{\alpha }\), where \(0<\alpha <1/3\), then \(p_{n,k}={n\atopwithdelims ()k}-o({n\atopwithdelims ()k}^\beta )\) and \(c_{n,k}={n\atopwithdelims ()k}+o({n\atopwithdelims ()k}^\beta )\), for some \(\beta <1\). Finally, we show that if \(k=o(n)\), then \(p_{n,k}={n\atopwithdelims ()k}(1-o(1))\).     

On (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-absorbing ideals of commutative rings

Let R be a commutative ring with 1 ≠ 0 and U(R) be the set of all unit elements of R. Let m, n be positive integers such that m > n. In this article, we study a generalization of n-absorbing ideals. A proper ideal I of R is called an (m, n)-absorbing ideal if whenever a ₁?a _m ∈I for a ₁,…, a _m ∈R?U(R), then there are n of the a _i ’s whose product is in I. We investigate the stability of (m, n)-absorbing ideals with respect to various ring theoretic constructions and study (m, n)-absorbing ideals in several commutative rings. For example, in a Bézout ring or a Boolean ring, an ideal is an (m, n)-absorbing ideal if and only if it is an n-absorbing ideal, and in an almost Dedekind domain every (m, n)-absorbing ideal is a product of at most m ? 1 maximal ideals.     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

<Emphasis Type="Italic">X</Emphasis>-decomposable finite groups for <Emphasis Type="Italic">X</Emphasis>={1, <Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">m</Emphasis> + 1, <Emphasis Type="Italic">m</Emphasis> + 2}

A normal subgroup N of a finite group G is called n-decomposable in G if N is the union of n distinct G-conjugacy classes. We study the structure of nonperfect groups in which every proper nontrivial normal subgroup is m-decomposable, m+1-decomposable, or m+2-decomposable for some positive integer m. Furthermore, we give classification for the soluble case.     

On the Second Parameter of an (<Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">p</Emphasis>)-Isometry

A bounded linear operator T on a Banach space X is called an (m, p)-isometry if it satisfies the equation \({\sum_{k=0}^{m}(-1)^{k} {m \choose k}\|T^{k}x\|^{p}=0}\) , for all \({x \in X}\) . In this paper we study the structure which underlies the second parameter of (m, p)-isometric operators. We concentrate on determining when an (m, p)-isometry is a (μ, q)-isometry for some pair (μ, q). We also extend the definition of (m, p)-isometry, to include p = ∞ and study basic properties of these (m, ∞)-isometries.