Asymptotic packing and the random greedy algorithm

Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for each vertex xϵ V(H) and deg(x, y) = o(D) for each pair of vertices x, y ϵ V(H), where D → infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n/r(1 − o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via “nibbles.” Further, let T_α be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [n/r · (1 − α)]. We show that almost surely T_α ∼ (1/α)^r−1 · n/r(r − 1) as α → 0⁺ holds. © 1996 John Wiley & Sons, Inc.     

The Degree and Regularity of Vanishing Ideals of Algebraic Toric Sets Over Finite Fields

Let X* be a subset of an affine space 𝔸 ^s , over a finite field K, which is parameterized by the edges of a clutter. Let X and Y be the images of X* under the maps x → [x] and x → [(x, 1)], respectively, where [x] and [(x, 1)] are points in the projective spaces ? ^s?1 and ? ^s , respectively. For certain clutters and for connected graphs, we were able to relate the algebraic invariants and properties of the vanishing ideals I(X) and I(Y). In a number of interesting cases, we compute its degree and regularity. For Hamiltonian bipartite graphs, we show the Eisenbud–Goto regularity conjecture. We give optimal bounds for the regularity when the graph is bipartite. It is shown that X* is an affine torus if and only if I(Y) is a complete intersection. We present some applications to coding theory and show some bounds for the minimum distance of parameterized linear codes for connected bipartite graphs.     

On the determination of the impulsive Sturm–Liouville operator with the eigenparameter-dependent boundary conditions

In the present work, we consider the inverse problem for the impulsive Sturm–Liouville equations with eigenparameter-dependent boundary conditions on the whole interval (0,π) from interior spectral data. We prove two uniqueness theorems on the potential q(x) and boundary conditions for the interior inverse problem, and using the Weyl function technique, we show that if coefficients of the first boundary condition, that is, h₁,h₂, are known, then the potential function q(x) and coefficients of the second boundary condition, that is, H₁,H₂, are uniquely determined by information about the eigenfunctions at the midpoint of the interval and one spectrum or partial information on the eigenfunctions at some internal points and some of two spectra.     

A lower bound on the independence number of arbitrary hypergraphs

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d(v) = (d₁(v), d₂(v), …) where d_m(v) is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ Σ_v∈V f(d(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999     

Weak Cayley Table Groups II: Alternating Groups and Finite Coxeter Groups

A weak Cayley table isomorphism is a bijection φ: G → H of groups such that φ(xy) ～ φ(x)φ(y) for all x, y ∈ G. Here ～denotes conjugacy. When G = H the set of all weak Cayley table isomorphisms φ: G → G forms a group 𝒲(G) that contains the automorphism group Aut(G) and the inverse map I: G → G, x → x ^?1. Let 𝒲₀(G) = ?Aut(G), I? ≤ 𝒲(G) and say that G has trivial weak Cayley table group if 𝒲(G) = 𝒲₀(G). We show that all finite irreducible Coxeter groups (except possibly E ₈) have trivial weak Cayley table group, as well as most alternating groups. We also consider some sporadic simple groups.     

Existence of subgraph with orthogonal (g,f)-factorization

Simple graphs are considered. Let G be a graph andg(x) andf(x) integer-valued functions defined on V(G) withg(x)⩽f(x) for everyxɛV(G). For a subgraphH ofG and a factorizationF=|F ₁,F ₂,⃛,F ₁| ofG, if |E(H)∩E(F ₁)|=1,1⩽i⩽j, then we say thatF orthogonal toH. It is proved that for an (mg(x)+k,mf(x) -k)-graphG, there exists a subgraphR ofG such that for any subgraphH ofG with |E(H)|=k,R has a (g,f)-factorization orthogonal toH, where 1⩽k<m andg(x)⩾1 orf(x)⩾5 for everyxɛV(G). Project supported by the Chitia Postdoctoral Science Foundation and Chuang Xin Foundation of the Chinese Academy of Sciences.     

Stanley depth of monomial ideals with small number of generators

For a monomial ideal I ⊂ S = K[x ₁...,x _n ], we show that sdepth(S/I) ≥ n − g(I), where g(I) is the number of the minimal monomial generators of I. If I =νI′, where ν ∈ S is a monomial, then we see that sdepth(S/I) = sdepth(S/I′). We prove that if I is a monomial ideal I ⊂ S minimally generated by three monomials, then I and S/I satisfy the Stanley conjecture. Given a saturated monomial ideal I ⊂ K[x ₁,x ₂,x ₃] we show that sdepth(I) = 2. As a consequence, sdepth(I) ≥ sdepth(K[x ₁,x ₂,x ₃]//I) +1 for any monomial ideal in I ⊂ K[x ₁,x ₂,x ₃].     

Some Remarks on the Graph Γ I (R)

Let R be a commutative ring with nonzero identity and Z(R) its set of zero-divisors. The zero-divisor graph of R is Γ(R), with vertices Z(R)?{0} and distinct vertices x and y are adjacent if and only if xy = 0. For a proper ideal I of R, the ideal-based zero-divisor graph of R is Γ _I (R), with vertices {x ∈ R?I | xy ∈ I for some y ∈ R?I} and distinct vertices x and y are adjacent if and only if xy ∈ I. In this article, we study the relationship between the two graphs Γ(R) and Γ _I (R). We also determine when Γ _I (R) is either a complete graph or a complete bipartite graph and investigate when Γ _I (R) ? Γ(S) for some commutative ring S.     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

A partition approach to Vizing's conjecture

In 1963, Vizing [Vichysl.Sistemy 9 (1963), 30–43] conjectured that γ(G × H) ≥ γ(G)γ(H), where G × H denotes the cartesian product of graphs, and γ(G) is the domination number. In this paper we define the extraction number x(G) and we prove that P₂(G) ≤ x(G), and γ(G × H) ≥ x(G)γ(H), where P₂(G) is the 2-packing number of G. Though the equality x(G) = γ(G) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ(G × H) ≥ γ(G)P₂(H) + P₂(G)(γ(H) − P₂(H)). © 1996 John Wiley & Sons, Inc.     

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

Inverse problem for a perturbed stratified strip in two dimensions

We consider the divergence form elliptic operator A=??_x,z·(c²(x,z) ?_x,z) in the strip Ω=?× [0,H]. The velocity c(x,z) describes the multistratification of Ω: a horizontal stratification with a compact perturbation K, the velocity in K is a L^∞(K) function. We suppose that the position of the perturbation is known and we prove uniqueness for identification of the perturbation from one generalized eigenfunction pattern in the neighbourhood of K. Copyright © 2004 John Wiley & Sons, Ltd.     

The Instability of Nonmonotonic Wave Solutions of Parabolic Equations

We consider the class of equations u_t=f(u_xx, u_x, u) under the restriction that for all a,b,c. We first consider this equation over the unbounded domain ? ∞ < x < + ∞, and we show that very nearly every bounded nonmonotonic solution of the form u(t, x)=?(x?ct) is unstable to all nonnegative and all nonpositive perturbations. We then extend these results to nonmonotonic plane wave solutions u(t, x, y)=?(x?ct) of u_t = F(u_xx, u_xy, u_x, u_y, u). Finally, we consider the class of equations u_t=f(u_xx, u_x, u) over the bounded domain 0 < x < 1 with the boundary conditions u(t, x)=A at x=0 and u(t, x)=B at x=1, and we find the stability of all steady solutions u(t, x)=?(x).     

Existence of Solutions for Some Quasilinear Degenerate Elliptic Inclusions in Weighted Sobolev Spaces

We consider the Dirichlet problem for a class of quasilinear degenerate elliptic inclusions of the form ?div(𝒜(x, u, ?u)) + f(x)g(u) ∈ H(x, u, ?u), where 𝒜(x, u, ?u) is allowed to be degenerate. Without the general assumption that the multivalued nonlinearity is characterized by Clarke's generalized gradient of some locally Lipschitz functions, we prove the existence of bounded solutions in weighed Sobolev space with the superlinear growth imposed on the nonlinearity g and the multifunction H(x, u, ?u) by using the Leray-Schauder fixed point theorem. Furthermore, we investigate the existence of extremal solutions and prove that they are dense in the solutions of the original system. Subsequently, a quasilinear degenerate elliptic control problem is considered and the existence theorem based on the proven results is obtained.     

On the Range of Possible Integrities of Graphs G(n, k)

We discuss the range of values for the integrity of a graphs G(n, k) where G(n, k) denotes a simple graph with n vertices and k edges. Let I _max(n, k) and I _min(n, k) be the maximal and minimal value for the integrity of all possible G(n, k) graphs and let the difference be D(n, k) = I _max(n, k) − I _min(n, k). In this paper we give some exact values and several lower bounds of D(n, k) for various values of n and k. For some special values of n and for s < n ^1/4 we construct examples of graphs G _n  = G _n (n, n + s) with a maximal integrity of I(G _n ) = I(C _n ) + s where C _n is the cycle with n vertices. We show that for k = n ²/6 the value of D(n, n ²/6) is at least \frac?6-13n{\frac{\sqrt{6}-1}{3}n} for large n.     

Coloring some classes of mixed graphs

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [x_i,x_j], c(x_i)≠c(x_j) and for every arc (x_p,x_q), c(x_p)<c(x_q). We will analyse the complexity status of this problem for some special classes of graphs.     

CHAOS EXPANSION OF LOCAL TIME OF FRACTIONAL BROWNIAN MOTIONS

We find the chaos expansion of local time ? _T ^(H)(x,·) of fractional Brownian motion with Hurst coefficient H∈(0,1) at a point x∈R ^d . As an application we show that when H ₀ d<1 then ? _T ^(H)(x,·)∈L ²(μ). Here μ denotes the probability law of B ^(H) and H ₀=max{H ₁,…,H _d }. In particular, we show that when d=1 then ? _T ^(H)(x,·)∈L ²(μ) for all H∈(0,1).     

On the Comparison of Rees's Valuations Over a Quasi-Unmixed Local Ring

In this paper, we will show that if (R, 𝔪) is a quasi-unmixed local ring, I an 𝔪-primary ideal of R and ?𝒱(I) is the set of Rees valuations of I, then the number of minimal prime ideals in the 𝔪-adic completion of R equals exactly the number of equivalence classes on the set ?𝒱(I) under the equivalence relation ～defined by: ν₁ ～ ν₂ if there exist a constant c ≥ 1 such that for all x ∈ R, ν₁(x) ≤ cν₂(x) and ν₂(x) ≤ cν₁(x).