Szemerédi's partition and quasirandomness

In this paper we shall investigate the connection between the Szemerédi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (G_n) is quasirandom if and only if in the Szemerédi partitions of G_n almost all densities are ½ + o(l).     

Infinitely many pairs of cospectral integral regular graphs

A graph G is called integral if all the eigenvalues of the adjacency matrix A(G) of G are integers. In this paper, the graphs G ₄(a, b) and G ₅(a, b) with 2a+6b vertices are defined. We give their characteristic polynomials from matrix theory and prove that the (n+2)-regular graphs G ₄(n, n+2) and G ₅(n, n+2) are a pair of non-isomorphic connected cospectral integral regular graphs for any positive integer n.     

Closure Concepts: A Survey

In this paper we survey results of the following type (known as closure results). Let P be a graph property, and let C(u,v) be a condition on two nonadjacent vertices u and v of a graph G. Then G+uv has property P if and only if G has property P. The first and now well-known result of this type was established by Bondy and Chvátal in a paper published in 1976: If u and v are two nonadjacent vertices with degree sum n in a graph G on n vertices, then G+uv is hamiltonian if and only if G is hamiltonian. Based on this result, they defined the n-closure cl_n (G) of a graph G on n vertices as the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree sum n until no such pair remains. They showed that cl_n(G) is well-defined, and that G is hamiltonian if and only if cl_n(G) is hamiltonian. Moreover, they showed that cl_n(G) can be obtained by a polynomial algorithm, and that a Hamilton cycle in cl_n(G) can be transformed into a Hamilton cycle of G by a polynomial algorithm. As a consequence, for any graph G with cl_n(G)=K _n (and n≥3), a Hamilton cycle can be found in polynomial time, whereas this problem is NP-hard for general graphs. All classic sufficient degree conditions for hamiltonicity imply a complete n-closure, so the closure result yields a common generalization as well as an easy proof for these conditions. In their first paper on closures, Bondy and Chvátal gave similar closure results based on degree sum conditions for nonadjacent vertices for other graph properties. Inspired by their first results, many authors developed other closure concepts for a variety of graph properties, or used closure techniques as a tool for obtaining deeper sufficiency results with respect to these properties. Our aim is to survey this progress on closures made in the past (more than) twenty years. Revised: September 27, 1999     

On the abelianizations of congruence subgroups of Aut(<Emphasis Type="Italic">F</Emphasis><Subscript>2</Subscript>)

Let F _n be the free group of rank n, and let Aut⁺(F _n ) be its special automorphism group. For an epimorphism π : F _n → G of the free group F _n onto a finite group G we call the standard congruence subgroup of Aut⁺(F _n ) associated to G and π. In the case n = 2 we fully describe the abelianization of Γ⁺(G, π) for finite abelian groups G. Moreover, we show that if G is a finite non-perfect group, then Γ⁺(G, π) ≤ Aut⁺(F ₂) has infinite abelianization.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

Reorienting regularn-gons

Imagine that randomly oriented objects in the shape of a regularn-sided polygon are moving on a conveyor. Our aim is to specify sequences composed of two different rigid motions which, when performed on these objects, will reposition them in all possible ways. We call such sequencesfacing sequences. (Expressed in group theoretical terms, a facing sequence in a groupG is a sequence of elementsa ₁,a ₂, ...,a _n fromG such thatG={e,a ₁,a ₁ a ₂, ...,a ₁ a ₂ ...a _n }). In this paper we classify various kinds of facing sequences and determine some of their properties. The arguments are group theoretical and combinatorial in nature.     

Hamiltonian cycles in n‐extendable graphs

A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg_G x+deg_G y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002     

The Augmentation Quotients of the Groups of Order 25, II

We have described the structure of Q _n (G) = Δ ⁿ (G)/Δ ⁿ⁺¹(G) for 35 particular classes of groups G with order 2⁵ in the previous article. In this article, the structure of Q _n (G) for all the remaining classes of groups G with order 2⁵ are presented.     

Graphs of difference operators for p-ary sequences

For a given prime p and positive integer n, we consider the graph G _n of the difference operator acting on p-ary sequences of length n. We suggest new proofs of some results of V.I. Arnold on the graph G _n and the complexity of sequences and obtain new results for the length of a maximal cycle in the general case of p-ary sequences. We also provide estimates for the number of complicated sequences.      

Extraspecial 2-groups and mod-2 cohomology lengths

Let G₀ (respectively G₁,G₂) be the extraspecial 2-group of real (respectively complex, quaternion) type of order 2²ⁿ⁺³ (respectively 2²ⁿ⁺²,2²ⁿ⁺¹). The purpose of this paper is to investigate the cohomology lengths chl(G_i) with i=1,2 (the case i=0 was settled up by Yalçın). We prove that chl(G₀)chl(G₁)chl(G₂)>2ⁿ, and the equalities chl(G₀)=chl(G₁)=chl(G₂) hold for n3. This disproves a conjecture of Yalçın telling that chl(G_i)=s(G_i), i=1,2, with s(G_i) the minimum cardinality of a representing set of G_i.     

Homogeneous Embeddings of Cycles in Graphs

If G and H are vertex-transitive graphs, then the framing number fr(G,H) of G and H is defined as the minimum order of a graph every vertex of which belongs to an induced G and an induced H. This paper investigates fr(C _m,C _n) for m<n. We show first that fr(C _m,C _n)≥n+2 and determine when equality occurs. Thereafter we establish general lower and upper bounds which show that fr(C _m,C _n) is approximately the minimum of and n+n/m. Received: June 12, 1996 / Revised: June 2, 1997     

On Rosa-type labelings and cyclic graph decompositions

A labeling (or valuation) of a graph G is an assignment of integers to the vertices of G subject to certain conditions. A hierarchy of graph labelings was introduced by Rosa in the late 1960s. Rosa showed that certain basic labelings of a graph G with n edges yielded cyclic G-decompositions of K _2n+1 while other stricter labelings yielded cyclic G-decompositions of K _2nx+1 for all natural numbers x. Rosa-type labelings are labelings with applications to cyclic graph decompositions. We survey various Rosa-type labelings and summarize some of the related results. (Communicated by Peter Horák)     

Dimension and lower central subgroups

In [7] Passi proved that for a finite p-group, p ≠ 2, one has G₄ = D₄. We generalize this to say that G_n = D_n as long as n?p + 1. We also generalize a theorem of Quillen [8], using entirely different methods from his, and give his result as a corollary. In order to do this, we construct natural algorithms (spectral sequences) which compute the graded Lie algebra ?_iG_i/G_i+1 and the graded algebra ? Iⁱ(G)/Iⁱ⁺¹(G) respectively, for any group G, in terms of a presentation. A natural transformation between these spectral sequences exists, and analysing its properties by some new combinatorial methods yields the results.     

The higher lower central series

The Baer invariants Γ _n (G) of a group are central extensions of the elementsγ _n (G) of the lower central series. We show that the inclusionsγ _n +1 ⊂γ _n can be lifted to functor morphisms Γ _n+1→Γ _n and a canonical Lie algebra, analogous to Lazard’s Lie algebra, can be constructed which is explicitly computable. This is applied in various ways.     

Torus quotients of homogeneous spaces of the general linear group and the standard representation of certain symmetric groups

We give a stratification of the GIT quotient of the Grassmannian G _2,n modulo the normaliser of a maximal torus of SL _n (k) with respect to the ample generator of the Picard group of G _2,n . We also prove that the flag variety GL _n (k)/B _n can be obtained as a GIT quotient of GL _n+1(k)/B _n+1 modulo a maximal torus of SL _n+1(k) for a suitable choice of an ample line bundle on GL _n+1(k)/B _n+1. Dedicated to Professor C De Concini on the occasion of his 60th birthday     

The Augmentation Quotients of the Groups of Order 25, I

In this article we present the nth power Δ ⁿ (G) of the augmentation ideal Δ(G) and describe the structure of Q _n (G) = Δ ⁿ (G)/Δ ⁿ⁺¹(G) for 35 particular groups G of order 2⁵. The structure of Q _n (G) for all the remaining groups of order 2⁵ will be determined in a forthcoming article.     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

On a Function Related to Multinomial Coefficients (I)

Let F _p,t (n) denote the number of the coefficients of (x ₁+1x ₂+...+x _t ) ^j , 0 ≤j≤n− 1, which are not divisible by the prime p. Define G _p,t (n) = F _p,t /n ^θ and β(p,t) = lim infF _p,t )(n)/n ^θ, where θ = (log)/(log p). In this paper, we mainly prove that G _p,t can be extended to a continuous function on ℝ⁺, and the function G _p,t is nowhere monotonic. Both the set of differential points of the function G _p,t and the set of non-differential points of the function G _p,t are dense in ℝ⁺. Received February 18, 2000, Accepted December 7, 2000     

Retracts of box products with odd‐angulated factors

Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G□ H is S□T where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G□ H is S□T where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gⁿ is a core for all positive integers n, or the core of Gⁿ is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gⁿ is a core for any positive integer n. On the other hand, let G_i be a (2κ_i+1)‐angulated core for 1 ≤ i≤ n where κ₁ < κ₂ < … < κ_n. If G_i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n‐1, or G_i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n‐1, then □_i=1ⁿ G_i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C_2l+1 is a core for any integers l ≥ r ≥ 2. It is open whether K(r,2r+1) □ C_2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

A property of trees in terms of unique connected subgraphs

The following theorem is proved: Let G be a graph with p ≥ 3 points such that for some n, 3 ≤ n ≤ p, any n points lie on a unique smallest connected subgraph. Then G = C_n+1 or G is a tree, and conversely.