Variants of the Andrews-Gordon Identities

The object of this paper is to propose and prove a new generalization of the Andrews-Gordon Identities, extending a recent result of Garrett, Ismail and Stanton. We also give a combinatorial discussion of the finite form of their result which appeared in the work of Andrews, Knopfmacher, and Paule.     

Locally finite graphs with ends: A topological approach, II. Applications

This paper is the second of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [20]. They are complemented by a third part [31], which looks at the theory from an algebraic-topological point of view.The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. This second part of the survey concentrates on these applications, many of which solve problems or extend earlier work of Thomassen on infinite graphs. Numerous new problems are suggested.     

关于Thompson猜想与AAM猜想

本文研究了有限(几乎)单群的非交换图刻画问题.利用有限几乎单群的阶分量理论,证明了对于具有非连通素图的有限单群,AAM猜想成立,同时也证明了某砦几乎单群也能被其非交换图刻画.上述结果推广了文献f131的结果.

Abstract：

In this article,we discuss the characterization of some finite(almost)simple groups by their non-commuting graphs.By using the theory of order components of finite almost simple groups,we prove that AAM's conjecture is true for all finite simple groups with non-connected prime graphs.Moreover,we prove that some almost simple groups can be also characterized by their non-commuting graphs.All the above results generalize those results in[13].     

KNOPFMACHER EXPANSIONS IN NUMBER THEORY

Abstract

Dedicated to the memory of John Knopfmacher (1937–1999)

We survey in this paper J. Knopfmacher results on number theoretical expansions as they arised from our common collaboration.     

Minimal asymmetric graphs of induced length 4

Continuing the program, which was started in [4], of determining all minimal asymmetric graphs, it is shown that there are exactly seven finite minimal asymmetric graphs of induced length 4, and that these are at the same time the only finite minimal involution-free graphs of induced length 4. Contrary to the situation for minimal asymmetric/involution-free graphs of induced length >4, the assumption of finiteness is essential.     

Some notes on graphs whose second largest eigenvalue is less than (√5-1)/2

It is well known in spectral graph theory that all (connected) graphs except complete graphs and complete multi-partite graphs have second largest eigenvalue greater than 0. Graphs whose second larges eigenvalue does not exceed 1/3 are characterized in [2]. Some characterizations of graphs whose second largest eigenvalue does not exceed (√5-1)/2 are given in [9]. In this paper we prove that graphs whose second largest eigenvalue is less than (√5-1)/2 can be characterized by a finite collection of forbidden (induced) subgraphs.     

Natural dualities for three classes of relational structures

Motivated by the work of Hofmann [14] and Davey [7] on dualities for structures, we will construct natural dualities for the classes of quasi-ordered sets, equivalence-relationed sets, and reflexive (undirected) graphs. We describe the dual structures by giving finite sets of quasi-equations that axiomatise the dual categories. We also show that there is a natural connection between the duality we construct for finite quasi-ordered sets and Birkhoff’s representation theorem for finite ordered sets [2], and between the dualities constructed for quasi-ordered sets and equivalence-relationed sets.     

On a Problem of Cameron’s on Inexhaustible Graphs

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.The authors gratefully acknowledge support from the Natural Science and Engineering Research Council of Canada (NSERC).     

q-ENGEL SERIES EXPANSIONS AND SLATER'S IDENTITIES

Abstract

Dedicated to the memory of John Knopfmacher (1937–1999)

We describe the q-Engel series expansion for Laurent series discovered by John Knopfmacher and use this algorithm to shed new light on partition identities related to two entries from Slater's list. In our study Al-Salam/Ismail and Santos polynomials play a crucial r?ole.     

Context-free pairs of groups II - Cuts, tree sets, and random walks

This is a continuation of the study, begun by Ceccherini-Silberstein and Woess (2009) [5], of context-free pairs of groups and the related context-free graphs in the sense of Muller and Schupp (1985) [22]. The graphs under consideration are Schreier graphs of a subgroup of some finitely generated group, and context-freeness relates to a tree-like structure of those graphs. Instead of the cones of Muller and Schupp (1985) [22] (connected components resulting from deletion of finite balls with respect to the graph metric), a more general approach to context-free graphs is proposed via tree sets consisting of cuts of the graph, and associated structure trees. The existence of tree sets with certain "good" properties is studied. With a tree set, a natural context-free grammar is associated. These investigations of the structure of context free pairs, resp. graphs are then applied to study random walk asymptotics via complex analysis. In particular, a complete proof of the local limit theorem for return probabilities on any virtually free group is given, as well as on Schreier graphs of a finitely generated subgoup of a free group. This extends, respectively completes, the significant work of Lalley (1993, 2001) [18,20].     

Global gradient estimate on graph and its applications

Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results.     

Locally finite homogeneous graphs

A connected graph G is said to be z-homogeneous if any isomorphism between finite connected induced subgraphs of G extends to an automorphism of G. Finite z-homogeneous graphs were classified in [17]. We show that z-homogeneity is equivalent to finite-transitivity on the class of infinite locally finite graphs. Moreover, we classify the graphs satisfying these properties. Our study of bipartite z-homogeneous graphs leads to a new characterization for hypercubes.     

Pseudo q-Engel expansions and Rogers-Ramanujan type identities

Abstract

Andrews, Knopfmacher and Knopfmacher have used the Schur polynomials to consider the celebrated Rogers-Ramanujan identities in the context of q-Engel expansions. We extend this view using similar polynomials, provided by Sills, in the context of Slater's list of 130 Rogers-Ramanujan type identities.     

Metric Properties and Exceptional Sets of the Oppenheim Expansions over the Field of Laurent Series

We investigate metric properties of the polynomial digits occurring in a large class of Oppenheim expansions of Laurent series, including Lüroth, Engel, and Sylvester expansions of Laurent series and Cantor infinite products of Laurent series. The obtained results cover those for special cases of Lüroth and Engel expansions obtained by Grabner, A. Knopfmacher, and J. Knopfmacher. Our results applied in the cases of Sylvester expansions and Cantor infinite products are original. We also calculate the Hausdorff dimensions of different exceptional sets on which the above-mentioned metric properties fail to hold.     

Gaps in samples of geometric random variables

In this note we continue the study of gaps in samples of geometric random variables originated in Hitczenko and Knopfmacher [Gap-free compositions and gap-free samples of geometric random variables. Discrete Math. 294 (2005) 225-239] and continued in Louchard and Prodinger [The number of gaps in sequences of geometrically distributed random variables, Preprint available at 〈http://www.ulb.ac.be/di/mcs/louchard/〉 (number 81 on the list) or at 〈http://math.sun.ac.za/∼ prodinger/pdffiles/gapsAPRIL27.pdf.〉] In particular, since the notion of a gap differs in these two papers, we derive some of the results obtained in Louchard and Prodinger [The number of gaps in sequences of geometrically distributed random variables, Preprint available at 〈http://www.ulb.ac.be/di/mcs/louchard/〉 (number 81 on the list) or at 〈http://math.sun.ac.za/∼prodinger/pdffiles/gapsAPRIL27.pdf.〉] for gaps as defined in Hitczenko and Knopfmacher [Gap-free compositions and gap-free samples of geometric random variables. Discrete Math. 294 (2005) 225-239].     

The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.     

Strongly regular Cayley graphs,skew Hadamard difference sets,and rationality of relative Gauss sums

In this paper, we give constructions of strongly regular Cayley graphs and skew Hadamard difference sets. Both constructions are based on choosing cyclotomic classes in finite fields. Our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White (2002) [23] and several subfield examples into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

Lifting constructions of strongly regular Cayley graphs

We give two “lifting” constructions of strongly regular Cayley graphs. In the first construction we “lift” a cyclotomic strongly regular graph by using a subdifference set of the Singer difference sets. The second construction uses quadratic forms over finite fields and it is a common generalization of the construction of the affine polar graphs [7] and a construction of strongly regular Cayley graphs given in [15]. The two constructions are related in the following way: the second construction can be viewed as a recursive construction, and the strongly regular Cayley graphs obtained from the first construction can serve as starters for the second construction. We also obtain association schemes from the second construction.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.