Elementary Abelian <Emphasis Type="Italic">p</Emphasis>-groups of rank greater than or equal to 4<Emphasis Type="Italic">p</Emphasis>−2 are not CI-groups

In this paper we prove that an elementary Abelian p-group of rank 4p−2 is not a CI⁽²⁾-group, i.e. there exists a 2-closed transitive permutation group containing two non-conjugate regular elementary Abelian p-subgroups of rank 4p−2, see Hirasaka and Muzychuk (J. Comb. Theory Ser. A 94(2), 339–362, 2001). It was shown in Hirasaka and Muzychuk (loc cit) and Muzychuk (Discrete Math. 264(1–3), 167–185, 2003) that this is related to the problem of determining whether an elementary Abelian p-group of rank n is a CI-group. As a strengthening of this result we prove that an elementary Abelian p-group E of rank greater or equal to 4p−2 is not a CI-group, i.e. there exist two isomorphic Cayley digraphs over E whose corresponding connection sets are not conjugate in Aut E. This research was supported by a fellowship from the Pacific Institute for the Mathematical Sciences.     

Jensen’s functional equation on the symmetric group S<Subscript>n</Subscript>

Two natural extensions of Jensen’s functional equation on the real line are the equations f(xy) + f(xy ⁻¹) =  2f(x) and f(xy) + f(y ⁻¹ x) =  2f(x), where f is a map from a multiplicative group G into an abelian additive group H. In a series of papers (see Ng in Aequationes Math 39:85–99, 1990; Ng in Aequationes Math 58:311–320, 1999; Ng in Aequationes Math 62:143–159, 2001), Ng solved these functional equations for the case where G is a free group and the linear group GL_n(R), R=\mathbbZ,\mathbbR{{GL_n(R), R=\mathbb{Z},\mathbb{R}}} , is a quadratically closed field or a finite field. He also mentioned, without a detailed proof, in the above papers and in (see Ng in Aequationes Math 70:131–153, 2005) that when G is the symmetric group S _n , the group of all solutions of these functional equations coincides with the group of all homomorphisms from (S _n , ·) to (H, + ). The aim of this paper is to give an elementary and direct proof of this fact.     

Reciprocal Polynomials and p-Group Cohomology

Let p be a prime and let G be a finite p-group. In a recent paper (Woodcock, J Pure Appl Algebra 210:193–199, 2007) we introduced a commutative graded ?-algebra R _G . This classifies, for each commutative ring R with identity element, the G-invariant commutative R-algebra multiplications on the group algebra R[G] which are cocycles (in fact coboundaries) with respect to the standard “direct sum” multiplication and have the same identity element. We show here that, up to inseparable isogeny, the “graded-commutative” mod p cohomology ring $H^\ast(G, \mathbb{F}_p)Let p be a prime and let G be a finite p-group. In a recent paper (Woodcock, J Pure Appl Algebra 210:193–199, 2007) we introduced a commutative graded ℤ-algebra R _G . This classifies, for each commutative ring R with identity element, the G-invariant commutative R-algebra multiplications on the group algebra R[G] which are cocycles (in fact coboundaries) with respect to the standard “direct sum” multiplication and have the same identity element. We show here that, up to inseparable isogeny, the “graded-commutative” mod p cohomology ring H^*(G, \mathbbF_p)H^\ast(G, \mathbb{F}_p) of G has the same spectrum as the ring of invariants of R _G mod p (R_G ?_\mathbbZ \mathbbF_p)^G(R_G \otimes_{\mathbb{Z}} \mathbb{F}_p)^G where the action of G is induced by conjugation.     

An algorithmic approach to Ramanujan’s congruences

In this paper we present an algorithm that takes as input a generating function of the form $\prod_{\delta|M}\prod_{n=1}^{\infty}(1-q^{\delta n})^{r_{\delta}}=\sum_{n=0}^{\infty}a(n)q^{n}In this paper we present an algorithm that takes as input a generating function of the form ?_d|M?_n=1^￥(1-q^dn)^r_d=?_n=0^￥a(n)qⁿ\prod_{\delta|M}\prod_{n=1}^{\infty}(1-q^{\delta n})^{r_{\delta}}=\sum_{n=0}^{\infty}a(n)q^{n} and three positive integers m,t,p, and which returns true if a(mn+t) o 0 mod p,n 3 0a(mn+t)\equiv0\pmod{p},n\geq0, or false otherwise. Our method builds on work by Rademacher (Trans. Am. Math. Soc. 51(3):609–636, 1942), Kolberg (Math. Scand. 5:77–92, 1957), Sturm (Lecture Notes in Mathematics, pp. 275–280, Springer, Berlin/Heidelberg, 1987), Eichhorn and Ono (Proceedings for a Conference in Honor of Heini Halberstam, pp. 309–321, 1996).     

The negative cycles polyhedron and hardness of checking some polyhedral properties

Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron in ℝ ⁿ within a factor of 12/n.     

Optimal Partition Trees

We revisit one of the most fundamental classes of data structure problems in computational geometry: range searching. Matoušek (Discrete Comput. Geom. 10:157–182, 1993) gave a partition tree method for d-dimensional simplex range searching achieving O(n) space and O(n ^1−1/d ) query time. Although this method is generally believed to be optimal, it is complicated and requires O(n ^1+ε ) preprocessing time for any fixed ε>0. An earlier method by Matoušek (Discrete Comput. Geom. 8:315–334, 1992) requires O(nlogn) preprocessing time but O(n ^1−1/d log ^O(1) n) query time. We give a new method that achieves simultaneously O(nlogn) preprocessing time, O(n) space, and O(n ^1−1/d ) query time with high probability. Our method has several advantages:

Swan-like results for binomials and trinomials over finite fields of odd characteristic

Swan (Pac. J. Math. 12:1099–1106, 1962) gives conditions under which the trinomial x ⁿ + x ^k + 1 over \mathbbF₂{\mathbb{F}_{2}} is reducible. Vishne (Finite Fields Appl. 3:370–377, 1997) extends this result to trinomials over extensions of \mathbbF₂{\mathbb{F}_{2}}. In this work we determine the parity of the number of irreducible factors of all binomials and some trinomials over the finite field \mathbbF_q{\mathbb{F}_{q}}, where q is a power of an odd prime.     

Distance and fractional isomorphism in Steiner triple systems

In [8], Quattrochi and Rinaldi introduced the idea ofn ⁻¹-isomorphism between Steiner systems. In this paper we study this concept in the context of Steiner triple systems. The main result is that for any positive integerN, there existsv ₀(N) such that for all admissiblev≥v ₀(N) and for each STS(v) (sayS), there exists an STS(v) (sayS′) such that for somen>N, S is strictlyn ⁻¹-isomorphic toS′. We also prove that for all admissiblev≥13, there exist two STS(v)s which are strictly 2⁻¹-isomorphic. Define the distance between two Steiner triple systemsS andS′ of the same order to be the minimum volume of a tradeT which transformsS into a system isomorphic toS′. We determine the distance between any two Steiner triple systems of order 15 and, further, give a complete classification of strictly 2⁻¹-isomorphic and 3⁻¹-isomorphic pairs of STS(15)s.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

Domination Number of Graphs Without Small Cycles

It has been shown (J. Harant and D. Rautenbach, Domination in bipartite graphs. Discrete Math. 309:113–122, 2009) that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 nor 13 is at most \frac3n8{\frac{3n}{8}}. They believed that the assumption that the graphs do not contain cycles of length 10 might be replaced by the exclusion of finitely many exceptional graphs. In this paper, we positively answer that if G is a connected graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5 nor 7 and is not one of three exceptional graphs, then the domination number of G is at most \frac3n8{\frac{3n}{8}}.     

Conjugacy classes and finite p-groups

Let G be a finite p-group, where p is a prime number, and a ∈ G. Denote by Cl(a) = {gag⁻¹| g ∈ G} the conjugacy class of a in G. Assume that |Cl(a)| = pⁿ. Then Cl(a) Cl(a⁻¹) = {xy | x ∈ Cl(a), y ∈ Cl(a⁻¹)} is the union of at least n(p − 1) + 1 distinct conjugacy classes of G. Received: 16 December 2004     

A Hilbert Transform for Matrix Functions on Fractal Domains

We consider H?lder continuous circulant (2 × 2) matrix functions G¹₂{{\bf G}^1_2} defined on the fractal boundary Γ of a Jordan domain Ω in \mathbbR²ⁿ{\mathbb{R}^{2n}}. The main goal is to establish a Hilbert transform for such functions, within the framework of Hermitian Clifford analysis. This is a higher dimensional function theory centered around the simultaneous null solutions of two first order vector valued differential operators, called Hermitian Dirac operators. In Brackx et al. (Bull Braz Math Soc 40(3): 395–416, 2009) a Hermitian Cauchy integral was constructed by means of a matrix approach using circulant (2 × 2) matrix functions, from which a Hilbert transform was derived in Brackx et al. (J Math Anal Appl 344: 1068–1078, 2008) for the case of domains with smooth boundary. However, crucial parts of the method are not extendable to the case where the boundary of the considered domain is fractal. At present we propose an alternative approach which will enable us to define a new Hermitian Hilbert transform in that case. As a consequence, we give necessary and sufficient conditions for the Hermitian monogenicity of a circulant matrix function G¹₂{{\bf G}^1_2} in the interior and exterior of Ω, in terms of its boundary value g¹₂=G¹₂|_G{{\bf g}^1_2={\bf G}^1_2|_\Gamma}, extending in this way also results of Abreu Blaya et al. (Bound. Value Probl. 2008: 2008) (article ID 425256), (article ID 385874), where Γ is required to be Ahlfors–David regular.     

A Note on L（2, 1）-labelling of Trees

An L(2,1)-labelling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) f(v)| ≥ 2 if d G (u,v)=1 and |f(u) f(v)| ≥ 1 if d G (u,v)=2.The L(2,1)-labelling problem is to find the smallest number,denoted by λ(G),such that there exists an L(2,1)-labelling function with no label greater than it.In this paper,we study this problem for trees.Our results improve the result of Wang [The L(2,1)-labelling of trees,Discrete Appl.Math.154 (2006) 598-603].     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

On the Perfect Matchings of Near Regular Graphs

Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least ?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1.     

Large Newforms of the Quantized Cat Map Revisited

We study the eigenfunctions of the quantized cat map, desymmetrized by Hecke operators. In the papers (Olofsson in Ann Henri Poincaré 10(6):1111–1139, 2009; Math Phys 286(3):1051–1072, 2009) it was observed that when the inverse of Planck’s constant is a prime exponent N = p ⁿ , with n > 2, half of these eigenfunctions become large at some points, and half remains small for all points. In this paper we study the large eigenfunctions more carefully. In particular, we answer the question of for which q the L ^q norms remain bounded as N goes to infinity. The answer is q ≤ 4.     

A direct approach to the weighted admissibility of observation operators for bounded analytic semigroups

In this note we adopt the approach in Bonnit et al. (Czechoslov. Math. J. 60(2):527–539, 2010) to give a direct proof of some recent results in Haak and Le Merdy (Houst. J. Math., 2005) and Haak and Kunstmann (SIAM J. Control Optim. 45:2094–2118, 2007) which characterizes the L ^p -admissibility of type α depending on p of unbounded observation operators for bounded analytic semigroups.     

The augmentation ideal in group near-rings

The definition of the group near-ring R[G] of the near-ring R over the group G as a near-ring of mappings from R ^(G) to itself is due to Le Riche et al. (Arch Math 52:132–139, 1989). In this paper we consider the augmentation ideal Δ of R[G]. If the exponent of G is not 2, then the structure of ΔR ^(G) is determined in terms of commutators and distributors. This is then used to show that Δ is nilpotent if and only if R is weakly distributive, has characteristic p ⁿ for some prime p and G is a finite p-group for the same prime p.      

Feynman’s Operational Calculi: Disentangling Away from the Origin

In this paper we develop a method of forming functions of noncommuting operators (or disentangling) using functions that are not necessarily analytic at the origin in ℂ ⁿ . The method of disentangling follows Feynman’s heuristic rules from in (Feynman in Phys. Rev. 84:18–128, 1951) a mathematically rigorous fashion, generalizing the work of Jefferies and Johnson and the present author in (Jefferies and Johnson in Russ. J. Math. 8:153–181, 2001) and (Jefferies et al. in J. Korean Math. Soc. 38:193–226, 2001). In fact, the work in (Jefferies and Johnson in Russ. J. Math. 8:153–181, 2001) and (Jefferies et al. in J. Korean Math. Soc. 38:193–226, 2001) allow only functions analytic in a polydisk centered at the origin in ℂ ⁿ while the method introduced in this paper enable functions that are not analytic at the origin to be used. It is shown that the disentangling formalism introduced here reduces to that of (Jefferies and Johnson in Russ. J. Math. 8:153–181, 2001) and (Jefferies et al. in J. Korean Math. Soc. 38:193–226, 2001) under the appropriate assumptions. A basic commutativity theorem is also established.