On the Constructive Inverse Problem in Differential Galois Theory#

We give sufficient conditions for a differential equation to have a given semisimple group as its Galois group. For any group G with G ⁰ = G ₁ · ··· · G _r , where each G _i is a simple group of type A_?, C_?, D_?, E₆, or E₇, we construct a differential equation over C(x) having Galois group G.     

Coloring graphs from lists with bounded size of their union

A graph G is k‐choosable if its vertices can be colored from any lists L(ν) of colors with |L(ν)| ≥ k for all ν ∈ V(G). A graph G is said to be (k,?)‐choosable if its vertices can be colored from any lists L(ν) with |L(ν)| ≥k, for all ν∈ V(G), and with . For each 3 ≤ k ≤ ?, we construct a graph G that is (k,?)‐choosable but not (k,? + 1)‐choosable. On the other hand, it is proven that each (k,2k ? 1)‐choosable graph G is O(k · ln k · 2^4k)‐choosable. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Groups,group actions and fields definable in first‐order topological structures

Given a group (G, ·), G?M^m, definable in a first‐order structure $\mathcal {M}=(M,\ldots )Given a group (G, ·), G?M^m, definable in a first‐order structure $\mathcal {M}=(M,\ldots )$ equipped with a dimension function and a topology satisfying certain natural conditions, we find a large open definable subset V?G and define a new topology τ on G with which (G, ·) becomes a topological group. Moreover, τ restricted to V coincides with the topology of V inherited from M^m. Likewise we topologize transitive group actions and fields definable in $\mathcal {M}$. These results require a series of preparatory facts concerning dimension functions, some of which might be of independent interest.     

Some Results on p-Nilpotence and Supersolvability of Finite Groups

Let G be a finite group. A subgroup K of a group G is called an ?-subgroup of G if N _G (K) ∩ K ^x  ≦ K for all x ? G. The set of all ?-subgroups of G will be denoted by ?(G). Let P be a nontrivial p-group. A chain of subgroups 1 = P ₀ ? P ₁ ? ··· ? P _n  = P is called a maximal chain of P provided that |P _i : P _i?1| = p, i = 1, 2, ···, n. A nontrivial p-subgroup P of G is called weakly supersolvably embedded in G if P has a maximal chain 1 = P ₀ ? P ₁ ? ··· ? P _i  ? ··· ? P _n  = P such that P _i  ? ?(G) for i = 1, 2, ···, n. Using the concept of weakly supersolvably embedded, we obtain new characterizations of p-nilpotent and supersolvable finite groups.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Crossing numbers of imbalanced graphs

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. According to the Crossing Lemma of M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi, Theory and Practice of Combinatorics, North‐Holland, Amsterdam, New York, 1982, pp. 9–12 and F. T. Leighton, Complexity Issues in VLSI, MIT Press, Cambridge, 1983, the crossing number of any graph with n vertices and e>4n edges is at least constant times e³/n². Apart from the value of the constant, this bound cannot be improved. We establish some stronger lower bounds under the assumption that the distribution of the degrees of the vertices is irregular. In particular, we show that if the degrees of the vertices are d₁?d₂?···?d_n, then the crossing number satisfies \begin{eqnarray*}{\rm{cr}}(G)\geq \frac{c_{1}}{n}\end{eqnarray*} with \begin{eqnarray*}{\textstyle\sum\nolimits_{{{i}}={{{1}}}}^{{{n}}}}{{id}}_{{{i}}}^{{{3}}}-{{c}}_{{{2}}}{{n}}^{{{2}}}\end{eqnarray*}, and that this bound is tight apart from the values of the constants c₁, c₂>0. Some applications are also presented. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 12–21, 2010     

On (2<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript> + 1)-variable symmetric Boolean functions with submaximum algebraic immunity 2<Superscript><Emphasis Type="Italic">m</Emphasis>−1</Superscript>

All (2 ^m + 1)-variable symmetric Boolean functions with submaximal algebraic immunity 2 ^m−1 are described and constructed. The total number of such Boolean functions is 3² · 2^2m−3 +3 ^m−2 · 2⁴ − 2 for m ⩾ 2. This work was supported by the Major State Basic Research Development Program of China (Grant No. 2004CB3180004) and National Natural Science Foundation of China (Grant No. 60433050)     

Characterization of 3-Rewritable Finite Nilpotent Groups

Let n be an integer greater than 1. A group G is said to be “ n-rewritable” whenever for every n elements x ₁,…,x _n of G, there exist distinct permutations τ, σ on the set {1,2,…, n} such that x _τ(1) ··· x _τ(n) = x _{σ (1)} ··· x _{σ (n)}. In this article, we complete the classification of 3-rewritable finite nilpotent groups and prove that a finite nilpotent group G is 3-rewritable if and only if G has an abelian subgroup of index 2 or the derived subgroup has order < 6.     

The total chromatic number of regular graphs of high degree

The total chromatic number χT (G) of a graph G is the minimum number of colors needed to color the edges and the vertices of G so that incident or adjacent elements have distinct colors. We show that if G is a regular graph and d(G) 32 |V (G)| + 263 , where d(G) denotes the degree of a vertex in G, then χT (G) d(G) + 2.     

On the number of colorings of a snark minus an edge

For a given snark G and a given edge e of G, let ψ(G, e) denote the nonnegative integer such that for a cubic graph conformal to G – {e}, the number of Tait colorings with three given colors is 18 · ψ(G, e). If two snarks G₁ and G₂ are combined in certain well‐known simple ways to form a snark G, there are some connections between ψ (G₁, e₁), ψ (G₂, e₂), and ψ(G, e) for appropriate edges e₁, e₂, and e of G₁, G₂, and G. As a consequence, if j and k are each a nonnegative integer, then there exists a snark G with an edge e such that ψ(G, e) = 2^j · 3^k. © 2005 Wiley Periodicals, Inc.     

Joint ergodicity and mixing

The study of jointly ergodic measure preserving transformations of probability spaces, begun in [1], is continued, and notions of joint weak and strong mixing are introduced. Various properties of ergodic and mixing transformations are shown to admit analogues for several transformations. The case of endomorphisms of compact abelian groups is particularly emphasized. The main result is that, given such commuting endomorphisms σ₁σ₂,...,σ, ofG, the sequence ((1/N)Σ _n=0 ^N−1 σ ₁ ⁿ f ¹·σ ₂ ⁿ f ²· ··· · σ _s ⁿ f ^sconverges inL ²(G) for everyf ₁,f ₂,…,f _s∈L ^∞(G). If, moreover, the endomorphisms are jointly ergodic, i.e., if the limit of any sequence as above is Π _i=1 ^s ∫ _G f ₁ d μ, where μ is the Haar measure, then the convergence holds also μ-a.e.     

UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE

Abstract

Let G be a graph and let v be a vertex of G. The open neigbourhood N(v) of v is the set of all vertices adjacent with v in G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ρ^° _L(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ρ^°(G), is the maximum cardinality among all open packings of G. It is known (see [7]) that if G is a connected graph of order n ≥3, then ρ^°(G) ≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know that ρ^° _L(G) ≤ 2n/3. In this paper, we improve this bound when G is a tree. We show that if G is a tree of order n with radius 3, then ρ^° _L(G) ≤ n/2 + 2 √n-1, and this bound is sharp, while if G is a tree of order n with radius at least 4, then ρ^° _L(G) is bounded above by 2n/3—O√n).     

Can visibility graphs Be represented compactly?

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graphG, a familyG={G ₁,G ₂,...,G _k } is called aclique cover ofG if (i) eachG _i is a clique or a bipartite clique, and (ii) the union ofG _i isG. The size of the clique coverG is defined as ∑ _i=1 ^k n _i , wheren _i is the number of vertices inG _i . Our main result is that there are visibility graphs ofn nonintersecting line segments in the plane whose smallest clique cover has size Ω(n ²/log² n). An upper bound ofO(n ²/logn) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of sizeO(nlog³ n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n logn). The work by the first author was supported by National Science Foundation Grant CCR-91-06514. The work by the second author was supported by a USA-Israeli BSF grant. The work by the third author was supported by National Science Foundation Grant CCR-92-11541.     

On the power of white pebbles

We construct a family (G _p |p) of directed acyclic graphs such that any black pebble strategy forG _p requiresp ² pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.Supported by the National Science Foundation under contract no. DCR-8407256 and by the office of Naval Research under contract no. N0014-80-0517.     

New upper bounds for the Davenport and for the Erdős–Ginzburg–Ziv constants

Let G be a finite abelian group (written additively) of rank r with invariants n ₁, n ₂, . . . , n _r , where n _r is the exponent of G. In this paper, we prove an upper bound for the Davenport constant D(G) of G as follows; D(G) ≤ n _r + n _r-1 + (c(3) − 1)n _r-2 + (c(4) − 1) n _r-3 + · · · + (c(r) − 1)n ₁ + 1, where c(i) is the Alon–Dubiner constant, which depends only on the rank of the group \mathbb Z_nrⁱ{{\mathbb Z}_{n_r}^i}. Also, we shall give an application of Davenport’s constant to smooth numbers related to the Quadratic sieve.     

Multiple Solutions and Its Morse Index for One-Dimensional Nonlinear Problem

The multiple solutions for one-dimensional cubic nonlinear problem u" u~3=0,u(0)=u(π)=0are computed,on the basis of the eigenpairs of-φ"_k=λ_(kφk),k=1,2,3....There exist two nonzero solutions±u_k corresponding to each k,and their Morse index MI(k) for 1(?)k(?)20 is to be exactly determined.It isshown by the numerical results that MI(k)(?)k.     

Upper bounds on the sum of powers of the degrees of a simple planar graph

For a simple planar graph G and a positive integer k, we prove the upper bound 2(n ? 1)^k + 4^k(n ? 4) + 2·3^k ? 2((δ + 1)^k ? δ^k)(3n ? 6 ? m) on the sum of the kth powers of the degrees of G, where n, m, and δ are the order, the size, and the minimum degree of G, respectively. The bound is tight for all m with 0?3n ? 6 ? m≤?n/2? ? 2 and δ = 3. We also present upper bounds in terms of order, minimum degree, and maximum degree of G. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:112‐123, 2011     

关于216阶群的完全分类

设G为2~3·3~3阶(即216阶)群,本文研究G的同构分类.利用有限群的局部分析法,证明G共有177种互不同构的类型,并获得了G的全部构造.     

A Note on Normality of Cones Over Symmetric Varieties

Let G be a semisimple and simply connected algebraic group, and let H ⁰ be the subgroup of points fixed by an involution of G. Let V be an irreducible representation of G with a nonzero vector v fixed by H ⁰. In this article, we prove a property of the normalization of the coordinate ring of the closure of G·[v] in ?(V).     

On a conjecture of Thomassen and Toft

This article is motivated by a conjecture of Thomassen and Toft on the number s₂(G) of separating vertex sets of cardinality 2 and the number υ₂(G) of vertices of degree 2 in a graph G belonging to the class 𝒢 of all 2-connected graphs without nonseparating induced cycles. Let ‖G‖ denote the number of edges of the graph G. Thomassen and Toft conjectured in [C. Thomassen & B. Toft, J. Combin. Theory B 31 (1981), 199–224] the existence of a positive constant c satisfying s₂(G) + υ₂(G) > c · ‖G‖ for all G ∈ 𝒢. We shall see that this is not true in general. Restricting ourselves to planar graphs, we obtain s₂(G) + υ₂(G) > · ‖G‖ for all planar G ∈ 𝒢, where is best-possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 118–122, 1999