Novel techniques for automorphism group computation

Graph automorphism (GA) is a classical problem, in which the objective is to compute the automorphism group of an input graph. In this work we propose four novel techniques to speed up algorithms that solve the GA problem by exploring a search tree. They increase the performance of the algorithm by allowing to reduce the depth of the search tree, and by effectively pruning it. We formally prove that a GA algorithm that uses these techniques correctly computes the automorphism group of the input graph. We also describe how the techniques have been incorporated into the GA algorithm conauto, as conauto-2.03, with at most an additive polynomial increase in its asymptotic time complexity. We have experimentally evaluated the impact of each of the above techniques with several graph families. We have observed that each of the techniques by itself significantly reduces the number of processed nodes of the search tree in some subset of graphs, which justifies the use of each of them. Then, when they are applied together, their effect is combined, leading to reductions in the number of processed nodes in most graphs. This is also reflected in a reduction of the running time, which is substantial in some graph families.

The automorphism group of a free-by-cyclic group in rank 2

Vegeu el resum a l'inici del document del fitxer adjunt

Maximal compactness, min- imal Hausdor ness and reversibility of frames and a study on automorphism group of frames

One can do research in pointfree topology in two ways. The rst is the contravariant way where research is done in the category Frm but the ultimate objective is to obtain results in Loc. The other way is the covariant way to carry out research in the category Loc itself directly. According to Johnstone [23], \frame theory is lattice theory applied to topology whereas locale theory is topology itself". The most part of this thesis is written according to the rst view. In this thesis, we make an attempt to study about 1. the frame counterparts of maximal compactness, minimal Hausdor - ness and reversibility, 2. the automorphism groups of a nite frame and its relation with the subgroups of the permutation group on the generator set of the frame

On the Closure of the Tame Automorphism Group of Affine Three-Space

We provide explicit families of tame automorphisms of the complex affine three-space which degenerate to wild automorphisms. This shows that the tame subgroup of the group of polynomial automorphisms of C3 is not closed, when the latter is seen as an infinite-dimensional algebraic group.

On the automorphism group of a reduced automaton /

"Supported in part jointly by the Atomic Energy Commission and the Advanced Research Projects Agency under AEC Contract AT(11-1)-1018."

The automorphism group of a strongly connected automaton and its quotient automata /

"February 14, 1966."

The Automorphism Group of the Free Algebra of Rank Two

The theorem of Czerniakiewicz and Makar-Limanov, that all the automorphisms of a free algebra of rank two are tame is proved here by showing that the group of these automorphisms is the free product of two groups (amalgamating their intersection), the group of all affine automorphisms and the group of all triangular automorphisms. The method consists in finding a bipolar structure. As a consequence every finite subgroup of automorphisms (in characteristic zero) is shown to be conjugate to a group of linear automorphisms.

Algorithms for Finding Unitals and Maximal Arcs in Projective Planes of Order 16

The paper has been presented at the International Conference Pioneers of Bulgarian Mathematics, Dedicated to Nikola Obreshkoff and Lubomir Tschakalo ff , Sofia, July, 2006.

Automorphism Groups of Generalized (Binary) Icosahedral, Tetrahedral and Octahedral Groups

Let G be any of the (binary) icosahedral, generalized octahedral (tetrahedral) groups or their quotients by the center. We calculate the automorphism group Aut(G).

Flexible varieties and automorphism groups

Given an irreducible affine algebraic variety X of dimension n≥2 , we let SAut(X) denote the special automorphism group of X , that is, the subgroup of the full automorphism group Aut(X) generated by all one-parameter unipotent subgroups. We show that if SAut(X) is transitive on the smooth locus X reg , then it is infinitely transitive on X reg . In turn, the transitivity is equivalent to the flexibility of X . The latter means that for every smooth point x∈X reg the tangent space T x X is spanned by the velocity vectors at x of one-parameter unipotent subgroups of Aut(X) . We also provide various modifications and applications.

Holomorphic Automorphisms of Danielewski Surfaces II: Structure of the Overshear Group

We apply Nevanlinna theory for algebraic varieties to Danielewski surfaces and investigate their group of holomorphic automorphisms. Our main result states that the overshear group, which is known to be dense in the identity component of the holomorphic automorphism group, is a free product.

New Symmetric (61,16,4) Designs Invariant Under the Dihedral Group of Order 10

∗ This work has been partially supported by the Bulgarian NSF under Contract No. I-506/1995.

Polynomial automorphisms over finite fields: Mimicking tame maps by the Derksen group

2010 Mathematics Subject Classification: 14L99, 14R10, 20B27.

Homological and Hodge-theoretic aspects of matroids and polymatroids

In the first part of this thesis, we study the action of the automorphism group of a matroid on the homology space of the co-independent complex. This representation turns out to be isomorphic, up to tensoring with the sign representation, with that on the homology space associated with the lattice of flats. In the case of the cographic matroid of the complete graph, this result has application in algebraic geometry: indeed De Cataldo, Heinloth and Migliorini use this outcome to study the Hitchin fibration. In the second part, on the other hand, we use ideas from algebraic geometry to prove a purely combinatorial result. We construct a Leray model for a discrete polymatroid with arbitrary building set and we prove a generalized Goresky-MacPherson formula. The first row of the model is the Chow ring of the polymatroid; we prove Poincaré duality, Hard-Lefschetz theorem and Hodge-Riemann relations for the Chow ring.

A spectral clustering algorithm for manufacturing cell formation

A graph clustering algorithm constructs groups of closely related parts and machines separately. After they are matched for the least intercell moves, a refining process runs on the initial cell formation to decrease the number of intercell moves. A simple modification of this main approach can deal with some practical constraints, such as the popular constraint of bounding the maximum number of machines in a cell. Our approach makes a big improvement in the computational time. More importantly, improvement is seen in the number of intercell moves when the computational results were compared with best known solutions from the literature. (C) 2009 Elsevier Ltd. All rights reserved.