The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

First Cohomology Group from the Virasoro-Like Algebra to its Larsson Functor Module

Let 𝒲 be the Virasoro-like algebra, and d ₁, d ₂ be the degree derivations of 𝒲. Set ? = W⊕C d ₁⊕C d ₂. Let F ^α(V) be the ?-module defined by Larsson's functor applied to a finite dimensional sl ₂-module V. In this article, the derivations from ? to ?-modules F ^α(V) and the first cohomology group H ¹(?, F ^α(V)) are given.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

Directed distance in digraphs: Centers and medians

The directed distance d_D(u, v) from a vertex u to a vertex v in a strong digraph D is the length of a shortest (directed) u - v path in D. The eccentricity of a vertex v in D is the directed distance from v to a vertex furthest from v. The distance of a vertex v in D is the sum of the directed distances from v to the vertices of D. The center C(D) of D is the subdigraph induced by those vertices of minimum eccentricity, while the median M(D) of D is the subdigraph induced by those vertices of minimum distance. It is shown that for every two asymmetric digraphs D₁ and D₂, there exists a strong asymmetric digraph H such that C(H) ? D₁ and M(H) ? D₂, and where the directed distance from C(H) to M(H) and from M(H) to C(H) can be arbitrarily prescribed. Furthermore, if K is a nonempty asymmetric digraph isomorphic to an induced subdigraph of both D₁ and D₂, then there exists a strong asymmetric digraph F such that C(F) ? D₁, M(F) ? D₂ and C(F) ∩ M(F) ? K. © 1993 John Wiley & Sons, Inc.     

Zeros of semilinear systems with applications to nonlinear partial difference equations on graphs†

Let Q be a m × m real matrix and f _j  : ? → ?, j = 1, …, m, be some given functions. If x and f(x) are column vectors whose j-coordinates are x _j and f _j (x _j ), respectively, then we apply the finite dimensional version of the mountain pass theorem to provide conditions for the existence of solutions of the semilinear system Qx = f(x) for Q symmetric and positive semi-definite. The arguments we use are a simple adaptation of the ones used by Neuberger. An application of the above concerns partial difference equations on a finite, connected simple graph. A derivation of a graph 𝒢 is just any linear operator D:C ⁰(𝒢) → C ⁰(𝒢), where C ⁰(𝒢) is the real vector space of real maps defined on the vertex set V of the graph. Given a derivation D and a function F:V × ? → ?, one has associated a partial difference equation Dμ = F(v,μ), and one searches for solutions μ ∈ C ⁰(𝒢). Sufficient conditions in order to have non-trivial solutions of partial difference equations on any finite, connected simple graph for D symmetric and positive semi-definite derivation are provided. A metric (or weighted) graph is a pair (𝒢, d), where 𝒢 is a connected finite degree simple graph and d is a positive function on the set of edges of the graph. The metric d permits to consider some classical derivations, such as the Laplacian operator ?₂. In (Neuberger, Elliptic partial difference equations on graphs, Experiment. Math. 15 (2006), pp. 91–107) was considered the nonlinear elliptic partial difference equations ?₂ u = F(u), for the metric d = 1.     

Hadamard matrices constructed from supplementary difference sets in the class ℋ︁1

In this article we give the definition of the class ??₁ and prove: (1) ??₁(v) ≠ ? for v ∈ ?? = ??₁ ∪ ??₂ ∪ ??₃ where (2) there exists 2 ? {2q²; q² ± q, q²;q² ± q} supplementary difference sets for q² ∈ ??; (3) there exists an Hadamard matrix of order 4v for v ∈ ??; (4) if t is an order of T-matrices, there exists an Hadamard matrix of order 4tv for v ∈ ??. © 1994 John Wiley & Sons, Inc.     

The Jacobian conjecture,the <Emphasis Type="Italic">d</Emphasis>-inversion approximation and its natural boundary

Let F ? \mathbbC[ X, Y ]² F \in \mathbb{C}{\left[ {X,\,Y} \right]^2} be an étale map of degree deg F = d. An étale map G ? \mathbbC[ X,Y ]² G \in \mathbb{C}{\left[ {X,Y} \right]^2} is called a d-inverse approximation of F if deg G ≤ d and F ◦ G =(X + A(X, Y), Y + B(X, Y)) and G ◦ F =(X + C(X, Y), Y + D(X, Y)), where the orders of the four polynomials A, B, C, and D are greater than d. It is a well-known result that every \mathbbC² {\mathbb{C}^2} -automorphism F of degree d has a d-inverse approximation, namely, F ⁻¹. In this paper, we prove that if F is a counterexample of degree d to the two-dimensional Jacobian conjecture, then F has no d-inverse approximation. We also give few consequences of this result. Bibliography: 18 titles.     

The Nonexistence of Ternary [38, 6, 23] Codes

It has been shown by Bogdanova and Boukliev [1] that there exist a ternary [38,5,24] code and a ternary [37,5,23] code. But it is unknown whether or not there exist a ternary [39,6,24] code and a ternary [38,6,23] code. The purpose of this paper is to prove that (1) there is no ternary [39,6,24] code and (2) there is no ternary [38,6,23] code using the nonexistence of ternary [39,6,24] codes. Since it is known (cf. Brouwer and Sloane [2] and Hamada and Watamori [14]) that (i) n₃(6,23) = 38> or 39 and d₃(38,6) = 22 or 23 and (ii) n₃(6,24) = 39 or 40 and d₃(39,6) = 23 or 24, this implies that n₃(6,23) = 39, d₃(38,6) = 22, n₃(6,24) = 40 and d₃(39,6) = 23, where n3<>(k,d) and d<>3(n,k) denote the smallest value of n and the largest value of d, respectively, for which there exists an [n,k,d] code over the Galois field GF(3).     

环F3+vF3上的循环码与常循环码

本文研究了环F₃+vF₃上的循环码与常循环码.通过环F₃+vF₃与域F₃上的循环码之间关系,证明了环F₃+vF₃上循环码是由一个多项式生成的.最后,用类似的方法,得到了环F₃+vF₃上v-常循环码也是由一个多项式生成的.     

Existence of T*(3, 4,v)‐codes

A word of length k over an alphabet Q of size v is a vector of length k with coordinates taken from Q. Let Q^*₄ be the set of all words of length 4 over Q. A T^*(3, 4, v)‐code over Q is a subset C^*? Q^*₄ such that every word of length 3 over Q occurs as a subword in exactly one word of C^*. Levenshtein has proved that a T^*(3, 4, vv)‐code exists for all even v. In this paper, the notion of a generalized candelabra t‐system is introduced and used to show that a T^*(3, 4, v)‐code exists for all odd v. Combining this with Levenshtein's result, the existence problem for a T^*(3,4, v)‐code is solved completely. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 42–53, 2005.     

Random walks on the torus with several generators

Given n vectors {_i} ∈ [0, 1)^d, consider a random walk on the d‐dimensional torus ??^d = ?^d/?^d generated by these vectors by successive addition and subtraction. For certain sets of vectors, this walk converges to Haar (uniform) measure on the torus. We show that the discrepancy distance D(Q*^k) between the kth step distribution of the walk and Haar measure is bounded below by D(Q*^k) ≥ C₁k^?n/2, where C₁ = C(n, d) is a constant. If the vectors are badly approximated by rationals (in a sense we will define), then D(Q*^k) ≤ C₂k^?n/2d for C₂ = C(n, d, _j) a constant. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

An Optimal Edge-Robust Identifying Code in the Triangular Lattice

A subset C of vertices in an undirected graph G = (V, E) is called a 1-identifying code if the sets I(v)={u C: d(u,v) 1 }, v V, are non-empty and no two of them are the same set. A 1-identifying code C is called 1-edge-robust 1-identifying if it is 1-identifying in every graph G¹ obtained from G by deleting or adding one edge. It is shown that the optimal density of a 1-edge-robust 1-identifying code in the infinite triangular lattice is 3/7.     

On the number of Galois points for a plane curve in positive characteristic,III

We consider the following problem: For a smooth plane curve C of degree d ≥ 4 in characteristic p > 0, determine the number δ(C) of inner Galois points with respect to C. This problem seems to be open in the case where d ≡ 1 mod p and C is not a Fermat curve F(p ^e  + 1) of degree p ^e  + 1. When p ≠ 2, we completely determine δ(C). If p = 2 (and C is in the open case), then we prove that δ(C) = 0, 1 or d and δ(C) = d only if d−1 is a power of 2, and give an example with δ(C) = d when d = 5. As an application, we characterize a smooth plane curve having both inner and outer Galois points. On the other hand, for Klein quartic curve with suitable coordinates in characteristic two, we prove that the set of outer Galois points coincides with the one of \mathbbF₂{\mathbb{F}_{2}} -rational points in \mathbbP²{\mathbb{P}^{2}}.     

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      15. Perfect matchings in random uniform hypergraphs      Jeong Han Kim 《Random Structures and Algorithms》2003,23(2):111-132 Let ??k(n, p) be the random k‐uniform hypergraph on V = [n] with edge probability p. Motivated by a theorem of Erd?s and Rényi 7 regarding when a random graph G(n, p) = ??2(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(). Then (Erd?s and Rényi 7 proved this for G(n, p).) Assuming d(n, p)/n1/2 → ∞, Schmidt and Shamir 16 were able to prove that ??k(n, p) contains a perfect matching with probability 1 ? o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n1/3 → ∞ was enough. In this paper, we further weaken the condition to A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn?2/3+1/15 of Krivelevich 12 , it is shown that if 3|n and p ? n?2/3+1/18, then © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003      16. Geodesics and almost geodesic cycles in random regular graphs      Itai Benjamini  Carlos Hoppen  Eran Ofek  Paweł Prałat  Nick Wormald 《Journal of Graph Theory》2011,66(2):115-136 A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance dG(u, v) is at least dC(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = logd?1logd?1n+ ω(n) and |C| = 2logd?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011      17. A determinantal version of the frobenius-könig theorem      D. J. Hartfiel  Raphael Loewy 《Linear and Multilinear Algebra》2013,61(1-4):155-165 Let F be a field and let {d 1,…,dk } be a set of independent indeterminates over F. Let A(d 1,…,dk ) be an n × n matrix each of whose entries is an element of F or a sum of an element of F and one of the indeterminates in {d 1,…,dk }. We assume that no d 1 appears twice in A(d 1,…,dk ). We show that if det A(d 1,…,dk ) = 0 then A(d 1,…,dk ) must contain an r × s submatrix B, with entries in F, so that r + s = n + p and rank B ? p ? 1: for some positive integer p.      18. Orbits of the Actions of Odd-Order Solvable Groups      Yong Yang 《代数通讯》2013,41(2):565-574 Suppose that V is a finite faithful irreducible G-module where G is a finite solvable group of odd order. We prove if the action is quasi-primitive, then either F(G) is abelian or G has at least 212 regular orbits on V. As an application, we prove that when V is a finite faithful completely reducible G-module for a solvable group G of odd order, then there exists v ∈ V such that C G (v) ? F 2(G) (where F 2(G) is the 2nd ascending Fitting subgroup of G). We also generalize a result of Espuelas and Navarro. Let G be a group of odd order and let H be a Hall π-subgroup of G. Let V be a faithful G-module over a finite field of characteristic 2, then there exists v ∈ V such that C H (v) ? O π(G).      19. Trialitarian groups and the Hasse principle      R. S. Garibaldi 《manuscripta mathematica》1999,98(1):97-113 Let F be a field of characteristic ≠ 2 such that is of cohomological 2- and 3-dimension ≤ 2. For G a simply connected group of type 3 D 4 or 6 D 4 over F, we show that the natural map where Ω F is the set of orderings of F and F v denotes the completion of F at v, restricts to be injective on the image of H 1(F, Z(G)) in H 1(F, G). For F not formally real, this implies that Serre's “Conjecture II” [Ser.94,III.3.1] holds for such groups if and only if trialitarian groups are classified by their Tits algebras over F. Received: 17 September 1998      20. [a,b]-factorization of a graph      Mikio Kano 《Journal of Graph Theory》1985,9(1):129-146 Let a and b be integers such that 0 ? a ? b. Then a graph G is called an [a, b]-graph if a ? dG(x) ? b for every x ? V(G), and an [a, b]-factor of a graph is defined to be its spanning subgraph F such that a ? dF(x) ? b for every vertex x, where dG(x) and dF(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]-factors then we say that the graph is [2a, 2a]-factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)-factorable if and only if G is a [2am,2bm]-graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]-graph is [1,2]-factorable.

Perfect matchings in random uniform hypergraphs

Let ??_k(n, p) be the random k‐uniform hypergraph on V = [n] with edge probability p. Motivated by a theorem of Erd?s and Rényi 7 regarding when a random graph G(n, p) = ??₂(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(). Then (Erd?s and Rényi 7 proved this for G(n, p).) Assuming d(n, p)/n^1/2 → ∞, Schmidt and Shamir 16 were able to prove that ??_k(n, p) contains a perfect matching with probability 1 ? o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n^1/3 → ∞ was enough. In this paper, we further weaken the condition to A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn^?2/3+1/15 of Krivelevich 12 , it is shown that if 3|n and p ? n^?2/3+1/18, then © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003     

Geodesics and almost geodesic cycles in random regular graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d_G(u, v) is at least d_C(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log_d?1log_d?1n+ ω(n) and |C| = 2log_d?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011     

A determinantal version of the frobenius-könig theorem

Let F be a field and let {d ₁,…,d_k } be a set of independent indeterminates over F. Let A(d ₁,…,d_k ) be an n × n matrix each of whose entries is an element of F or a sum of an element of F and one of the indeterminates in {d ₁,…,d_k }. We assume that no d ¹ appears twice in A(d ₁,…,d_k ). We show that if det A(d ₁,…,d_k ) = 0 then A(d ₁,…,d_k ) must contain an r × s submatrix B, with entries in F, so that r + s = n + p and rank B ? p ? 1: for some positive integer p.     

Orbits of the Actions of Odd-Order Solvable Groups

Suppose that V is a finite faithful irreducible G-module where G is a finite solvable group of odd order. We prove if the action is quasi-primitive, then either F(G) is abelian or G has at least 212 regular orbits on V. As an application, we prove that when V is a finite faithful completely reducible G-module for a solvable group G of odd order, then there exists v ∈ V such that C _G (v) ? F ₂(G) (where F ₂(G) is the 2nd ascending Fitting subgroup of G). We also generalize a result of Espuelas and Navarro. Let G be a group of odd order and let H be a Hall π-subgroup of G. Let V be a faithful G-module over a finite field of characteristic 2, then there exists v ∈ V such that C _H (v) ? O _π(G).     

Trialitarian groups and the Hasse principle

Let F be a field of characteristic ≠ 2 such that is of cohomological 2- and 3-dimension ≤ 2. For G a simply connected group of type ³ D ₄ or ⁶ D ₄ over F, we show that the natural map

[a,b]-factorization of a graph

Let a and b be integers such that 0 ? a ? b. Then a graph G is called an [a, b]-graph if a ? d_G(x) ? b for every x ? V(G), and an [a, b]-factor of a graph is defined to be its spanning subgraph F such that a ? d_F(x) ? b for every vertex x, where d_G(x) and d_F(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]-factors then we say that the graph is [2a, 2a]-factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)-factorable if and only if G is a [2am,2bm]-graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]-graph is [1,2]-factorable.