Computers in Scientific Discovery 5 - Abstracts
Quick selection
Keynote Talks
4- and 6-regular analogs of fullerenes
Michel DezaEcole Normale Supérieure, Paris, France
An ({a,b},k)-sphere is a k-regular plane graph whose faces have size a or b only, for given 1 ≤ a < b ≤ 6. The ({5,6},3)-spheres are (geometric) fullerenes.
We consider 8 possible infinite families of such spheres.
This is joint work with Mathieu Dutour Sikiric.
(Download the slides of the talk here)
A Graph Theoretic Approach to Atomic Displacements in Fullerenes
Ernesto EstradaDepartment of Mathematics and Statistics, Department of Physics, Institute of Complex Systems
University of Strathclyde, UK
We consider a classical mechanics approach to atomic displacements in fullerene molecules. The problem is reduced to the study of the graph Laplacian spectra by deriving an analytical expression for the atomic displacement due to thermal vibrations/oscillations. We then use the concepts of graph isoperimetric constant and graph expansion to prove that "among all graphs on n nodes, those with good expansion properties display the smallest topological displacements of their nodes." Consequently, fullerenes with the property of being Ramanujan graphs, i.e., Ramafullerenes, are those that exhibit the smallest atomic displacements due to thermal movement. We show that fullerenes with the smallest atomic perturbations due to thermal effects are the most stable ones. Then, relationships between atomic displacements, spectral gap, and energy are presented for different families of fullerenes.
(Download the slides of the talk here)
Generation of pharmacophore hypotheses using multiobjective optimisation
Val GilletDepartment of Information Studies
University of Sheffield, UK
Pharmacophore elucidation is a difficult problem involving the determination of the 3D description of ligand-protein interactions in the absence of the protein receptor. Given a set of ligands, the problem is to find their common regions of interaction with a protein partner without crystal structures for either the protein or the ligands in their binding modes. The task is difficult because there are many plausible ways to overlay ligands and there are many possible ligand conformations. A further issue which has hampered the development of pharmacophore programs is a lack of suitable test cases. We describe an approach to pharmacophore elucidation which is based on multiobjective optimisation techniques and which approaches the uncertainty in pharmacophore elucidation by searching for a family of plausible hypotheses. We have also developed a new high-quality test set for evaluating pharmacophore hypotheses consisting of test cases of increasing difficulty and we describe the performance of our method on the test set.
This is joint work with Jason Cole, Eleanor Gardiner and Robin Taylor.
Fullerene Features Great and Small
Jack GraverDepartment of Mathematics
Syracuse University, US
We present an overview of what is known about some of the graph theoretical parameters of fullerenes such as the vertex and face independence numbers. Then we consider local substructures (patches) and look at how simple changes in a patch affect the global structure and, in particular, the effects they may have on these parameters.
(Download the slides of the talk here)
Swinging from Tree to Tree: Rearrangement Operations and their Metrics
Stefan GrünewaldCAS-MPG PICB Shanghai, China
Phylogenetic trees are used in computational biology to show the evolutionary relationships within a collection of species or other taxonomic units. For a number of reasons, such as incomplete or corrupted data or reticulate evolution, there may be more than one tree that is hypothesised to display the evolution of a given set of taxa. In these circumstances, it may be useful to quantify the level of similarity between two different trees. One common way to do this is using tree rearrangement operations such as subtree prune and regraft (SPR) and tree bisection and reconnection (TBR). For example, SPR operations have been used to estimate the number of lateral gene transfers to explain a given data set, and to escape from local optima when searching the tree space for a maximum likelihood tree. The number of operations needed to transfer one tree into the other defines a metric on the set of all trees with a given taxa set. However, little is known about the distribution of these metrics and the computation of the distance between two trees is hard. I will present some recent results on the diameter of both metrics and on the SPR chain reduction conjecture. The latter conjecture claims that long chains of pendant leaves that occur in both trees can be reduced to chains of length three without altering the distance. The reduction is already used in practice but a proof of the conjecture is still missing.
(Download the slides of the talk here)
Structural Properties of Fullerenes
Klavdija KutnarFaculty of Mathematics, Natural Sciences and Information Technologies
University of Primorska, Slovenia
In this talk I will present results about structural properties of fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons. In particular, cyclic edge-connectivity, the existence of Hamilton cycles, the existence of semiregular automorphisms and other similar graph theoretic concepts in the framework of fullerenes will be discussed.
(Download the slides of the talk here)
The Story of Zagreb Indices
Sonja NikolićDepartment of Physical Chemistry
Rugjer Bošković Institute, Zagreb, Croatia
The original Zagreb indices and some of their variants, such as the modified Zagreb indices, variable Zagreb indices, reformulated original Zagreb indices, reformulated modified Zagreb indices, Zagreb indices as complexity indices, general Zagreb indices, Zagreb indices for heterocyclic systems, Zagreb coindices, are outlined. Some interesting properties of the Zagreb indices, depending on the structure of molecular (chemical) graphs, are mentioned. Zagreb indices of line graphs and their connection with certain walks on graphs are discussed. The relationships between the Zagreb indices and some of the earliest molecular descriptors such as the Platt index (introduced in 1947) and Gordon-Scantlebury index (introduced in 1964) are presented. So called Zagreb co-indices are briefly mentioned. Analytical formulas for computing Zagreb indices of several homologous structures are also given.
This is joint work with Nenad Trinajstić and Ante Miličević.
(Download the slides of the talk here)
Switching Combinatorial Objects
Patric ÖstergårdDepartment of Communications and Networking
Aalto University, Finland
Switching is a local transformation that when applied to a combinatorial object gives another object with the same parameters. Switching provides a means for constructing new objects with given parameters as well as for understanding the reasons behind the multitude of isomorphism classes for certain types of objects.
Switching has been considered to some extent for virtually all kinds of combinatorial objects. We shall here make an attempt to tie together most of these results -- in particular for codes and designs -- by unifying a central type of switching. The discussion starts from the case of binary error-correcting codes and proceeds via constant weight codes and Steiner systems to t-designs and various other related types of objects.
Some specific recent results regarding switching will also be mentioned. For example, it has been shown that any two Steiner triple systems of order 19 are connected to each other via a sequence of switches. As a computational challenge, this is about proving connectedness of a certain implicit graph with just over 11 billion vertices and estimated 370 billion edges.
This is in part joint work with Petteri Kaski, Veli Mäkinen and Olli Pottonen.
(Download the slides of the talk here)
HOMO-LUMO Maps and Golden Graphs
Tomaž PisanskiDepartment of Theoretical Computer Science
University of Ljubljana, Slovenia
Recently, we introduced a graphical tool for investigating spectral properties of graps that we called HOMO-LUMO maps. On a HOMO-LUMO map, a graph G is represented by point with (λh, λl) coordinates, where, roughly speaking λh and λl are the two middle eigenvalues of G. The difference (λh - λl) is the well-known HOMO-LUMO gap in Hückel theory. Therefore it is surprising that although the middle eigenvalues have clear significance in mathematical chemistry, not much attention has been paid to them in spectral graph theory. It turns our that the HOMO-LUMO maps are well suited for investigating families of graphs, such as chemical trees, fullerenes, etc., where extremal points or emerging patterns raise interesting questions. For instance, for small molecular graphs the HOMO-LUMO plot clearly shows that the vertical line λh = 1 / ϕ, where ϕ is the golden ratio, is heavily populated. We call graphs with λh = 1 / ϕ golden graphs. We present some results and raise some questions that have resulted from the study of HOMO-LUMO maps.
[1] P.W. Fowler, T. Pisanski, HOMO-LUMO maps for chemical graphs, MATCH Commun. Math. Comput. Chem., 64 (2010) 373-390.
[2] P.W. Fowler, T. Pisanski, HOMO-LUMO maps for fullerenes, Acta Chim. Slov., In press, 2010.
(Download the slides of the talk here)
Similarity methods for ligand-based virtual screening
Peter WillettDepartment of Information Studies
University of Sheffield, UK
Similarity searching is one of most common methods for ligand-based virtual screening, with recent work in Sheffield focussing on the use of data fusion and fragment weighting methods to search the MDDR, WOMBAT and MUV databases. Data fusion involves the combination of multiple similarity searches. The overlap between multiple searches is shown to follow a Zipf-like, power law distribution, with very few molecules (or active molecules) common to multiple searches; and a comparison of a large number of different fusion algorithms shows that one based on molecules' inverse rank positions is the most effective of those tested. Information about the frequencies with which fragments occur in molecules can be used in two ways to increase search effectiveness (when compared with using just the presence or absence of fragments in molecules): using functions of the frequencies of fragment occurrences in individual molecules, and using inverse functions of the frequency of fragment occurrences in the database as a whole.
This is joint work with Shereen Arif, John Holliday, Nurul Malim and Christoph Muëller.
(Download the slides of the talk here)
Go to top
Contributed Talks
Clar Sextet Theory for low-dimensional carbon nanostructures: an efficient approach based on chemical criteria
Matteo BaldoniFachbereich Chemie
Technische Universität Dresden, Germany
Recently, the properties of nanostructured carbon materials, such as carbon nanotubes (CNTs) and graphene, have been the subject of in-depth investigations in view of their potential use in nanotechnology. Most of the interest concerning nanostructured carbon materials is related to the peculiarities of their electronic structure, which is constituted mainly by a complex network of π-conjugated bonds. Details of the electronic structure play a crucial role in the application of such materials as nanostructured building-blocks for molecular electronics and in functionalization processes, where the CNTs and graphenes undergo chemical reactions. However, the particular structural and electronic features of nanostructured carbon poses significant problems to computational modeling. Recent work has indicated the extension of classical organic chemistry concepts, like the “Clar Sextet Theory”, to the case of low-dimensional nanostructured carbon materials as a successful approach to obtain an accurate and consistent description of the electronic structure of the hexagonal carbon atom network. In this work we apply state-of-the-art numerical techniques to investigations on the stability and on electronic and chemical properties of nanotubes and graphenes and related compounds. Our approach is based on the definition of suitable models of the system under study starting from chemical considerations. Results indicate unprecedented accuracy in the prediction of properties for a large variety of systems, obtained at a relatively cheap computational cost.
This is joint work with F. Mercuri and G. Seifert.
(Download the slides of the talk here)
Mining patterns and subgraphs as potential toxicophores, to predict contextual ecotoxicity
Ryan Bissell-SidersDepartment of Mathematics and Statistics
Université de Caen, France
We present work on the study of the toxicity of molecules for two types of application, to assist researchers in chemistry make choices in molecular synthesis, and to aid enforcement of the REACH regulations. Within this framework, we have developed new computational methods designed for automatic extraction (discovery) of new knowledge concerning toxicity. From the informatics point of view, these activities rely principally on data mining, graph algorithms, and automatic learning. We will present two new notions of informatics related to the treatment of chemical information: frequent graph emerging patterns, and stimulation of a pattern. Moreover, we have developed two kinds of automatic classification methods: one based on "graph kernels" and one based on "implication rules".
This is joint work with Guillaume Poezevara, Bertrand Cuissart and Bruno Crémilleux.
Computational results on the α-deficit
Gunnar BrinkmannDepartment of Applied Mathematics and Computer Science
Ghent University, Belgium
A labeling of the vertices of a tree with n vertices is an assignment of values 1,..., n to the vertices. The induced label of an edge is defined as the absolute difference of its endvertices. If the induced edge labels have all possible values 1,..., n-1 a labeling is called graceful. A labeling is bipartite if the vertices are labeled in a way that in every bipartitionclass the vertex labels are successive. So a bipartitionclass with n1 vertices either gets labels 1,..., n1 or n - n1 + 1,..., n. A bipartite graceful labeling is called an α-labeling.
It is well known that not all trees allow an α-labeling and in this talk we give results of a computer search about how many induced edge labels must be missing for some trees. The minimal number of labels missing for every bipartite labeling of a tree T is called the α-deficit of T. The computer search shows some astonishing patterns and is a good example of how computer generated results can suggest conjectures.
This is joint work with H. Mélot (Mons, Belgium) and E. Steffen (Paderborn, Germany).
(Download the slides of the talk here)
The helical structure of xylose-DNA
Arnout CeulemansDepartment of Chemistry and Institute for Nanoscale Physics and Chemistry
Katholieke Universiteit Leuven, Belgium
Synthetic biology demonstrates a growing interest in modified nucleotides to achieve an enzymatically stable artificial nucleic acid. A potential candidate system is xylose-DNA, in which the 2'-deoxy-β-D-ribo-furanose is substituted by 2'-deoxy-β-D-xylo-furanose. We present a computational study [1] of the helical structure of xylose-DNA on the basis of 35ns Molecular Dynamics simulations of a 29-base-pair DNA duplex. Starting from a right-handed xylose-DNA helix, a remarkable conformational transition takes place from right- to left-handed helix. The left-handed xylose-DNA is highly dynamic, involving screwing and unscrewing motion of the helix. The sugar pucker induced helical changes influence the backbone to adopt the characteristic backbone angles for xylose-DNA while retaining the Watson-Crick base pairing and stacking interactions. The results demonstrate the chiral orthogonality of the ribose and xylose based episomes.
The incorporation of these results in mathematical spin-models of double-helix structure and dynamics is discussed.
[1] A. Ramaswamy, M. Froeyen, P. Herdewijn, A. Ceulemans, J. Am. Chem. Soc., 132, 587-595 (2010)
The minimal perimeter for N deformable bubbles of equal area
Simon CoxInstitute of Mathematics and Physics
Aberystwyth University, UK
A two-dimensional foam, such as can be formed between two closely-spaced parallel plates, minimizes its total perimeter subject to area constraints on the individual bubbles. I will describe conjectured least-perimeter partitions of various polygonal shapes into N planar connected equal-area regions for N ≤ 42 and discuss them in the context of the energetic groundstate of a two-dimensional monodisperse foam. The partitions can be classified according to the number and position of the topological defects, that is non-hexagonal regions (bubbles). The optimal partitions of an equilateral triangle (but no other polygon) are conjectured to follow a pattern based on the position of no more than one defect pair.
I will also describe the enumeration of candidates to the least perimeter partition of the surface of the sphere into N connected equal-area regions. For small N the candidates can be related to simple polyhedra while for N ≥ 14 they consist of 12 pentagons and N - 12 hexagons and can be related to fullerenes. It is an open question as to whether a similar enumeration procedure can be used to improve the partitions in the planar cases.
(Download the slides of the talk here)
A Communication Network for the GPS III system
Simon CrevalsDepartment of Applied Mathematics and Computer Science
Ghent University, Belgium
For the communication network of the upcoming GPS III system, Lockheed Martin is interested in finding the best connection graph between the satellites. A connection graph has to be a 4-regular subgraph of the graph with all possible connections. Satellites that are too close to each other or have the earth between them at any point in time cannot be connected. For each satellite s and a given set of 4 neighbours there is also a number, called the uredop value, a function of the angles between the satellites connected to s that indicates the precision with which s can determine its own position based on the satellites to which it is connected. Smaller uredop values represent a better quality solution.
The aim is to find connection graphs with diameter 3, which is the theoretical lower bound. Furthermore the maximum uredop value over all its satellites should be as small as possible. Having fulfilled these requirements it would be nice if the diameter of G would be 4 when one of its connections fails, which we prove to be the lower bound.
We translate our problem to an independent set problem and present a specialized program for our independent set problem that efficiently generates all independent sets corresponding to connection graphs with a given maximum allowed uredop value. This allowed us to find the best connection graphs.
(Download the slides of the talk here)
Conjugated molecules described in terms of the Dirac equation
Matthias ErnzerhofDepartment of Chemistry
University of Montreal, Canada
Starting from the Hückel Hamiltonian of finite, unsaturated hydrocarbon chains (ethylene, allyl radical, butadiene, pentadienyl radical, hexatriene, etc.), we perform [1] a simple unitary transformation and obtain a Dirac matrix Hamiltonian. Thus already these small systems are described exactly in terms of the Dirac equation, the continuum limit of which yields the one-dimensional Dirac Hamiltonian. Using the Source-sink potential method [2,3], complex potentials are introduced into the Dirac Hamiltonian to model the effect of infinite metal contacts. The electron-transport properties are then calculated and interpreted in terms of the Dirac Hamiltonian. Furthermore, we illustrate how the findings for short hydrocarbon chains carry over to a certain class of rectangular graphene sheets.
[1] M. Ernzerhof, F. Goyer, JCTC, in press.
[2] F. Goyer, M. Ernzerhof, M. Zhuang, J. Chem. Phys. 126, 144104 (2007).
[3] M. Ernzerhof, J. Chem. Phys. 127, 204709 (2007).
(Download the slides of the talk here)
A new twist to the theory of conduction
Patrick FowlerDepartment of Chemistry
University of Sheffield, UK
Putting a half-twist into a molecule or carbon network can have a dramatic effect on the conduction properties. One way to rationalise these changes is with the graph theoretical version of the source-and-sink-potential model [1] in which transmission properties can be expressed in terms of characteristic polynomials of molecular graphs and vertex-deleted subgraphs [2].
Factorisation relationships for the polynomials of cycles, ladders and related chemical graphs are used to identify the special conduction signature of the Möbius topology in twisted π- and σ-bonded systems. This leads us to a simple 'cut-and-paste' approach to the understanding of the transmission functions of Möbius nanostructures.
This is joint work with Barry Pickup and Tsanka Todorova.
[1] F. Goyer, M. Ernzerhof, and M. Zhuang, J. Chem. Phys. 126 (2007) 144104.
[2] B.T. Pickup and P.W. Fowler, Chem. Phys. Lett. 459 (2008) 198.
Fast Generation of Cubic Graphs
Jan GoedgebeurDepartment of Applied Mathematics and Computer Science
Ghent University, Belgium
Cubic graphs are a very important graph family, because for a lot of interesting problems it can be proved that the smallest possible counterexample would be a cubic graph. Therefore a lot of researchers have been working on the generation of (simple) cubic graphs. The first list of cubic graphs was published in the late 1800's. We will describe how the graphs are constructed and how isomorphic copies are avoided. The methods to reject isomorphic copies are based on McKay's canonical construction path method. We will provide details on how to efficiently implement these methods for simple cubic graphs and give some optimizations. The generator presented here is more than twice as fast as former generators for cubic graphs with girth at least 3 or at least 4.
This is joint work with Gunnar Brinkmann.
(Download the slides of the talk here)
Ambiguous Fullerene Patches
Christina GravesDepartment of Mathematics
University of Texas, US
A fullerene patch is the graph obtained by taking a simple closed curve in a fullerene and deleting all vertices on one side. Such a patch is ambiguous if there is another fullerene patch with the same boundary but different interior. A fullerene patch with at least 6 pentagons has an infinite number of different interiors, but a fullerene patch with fewer than 6 pentagons has a finite number of interiors that can all be described.
(Download the slides of the talk here)
Face Independence Numbers of Fullerenes
Elizabeth HartungDepartment of Mathematics
Syracuse University, US
Leap Frog Fullerenes have been found to admit a perfect face independent set and hence a perfect Kekule structure. We will discuss the face independence numbers for other types of fullerenes, particularly a class of fullerenes representing nanotubes.
(Download the slides of the talk here)
Distributed search engine Wowd
Aleksandar IlićFaculty of Sciences and Mathematics
University of Niš, Serbia
Wowd is a real-time engine for search and discovery. The attention frontier (what people are looking at on the internet right now) is gathered, mined and indexed in real-time using a fully distributed index. Many specialized algorithms were developed or used for achieving speed, reliability, quality and other goals. In particular, we deal with large graphs with special structures that also appear in bioinformatics and chemistry. For connecting all nodes, in order to get minimal latency and maximal reliability, an algorithm for construction of a dynamic routable graph with minimal diameter is developed. In addition, we improved the PageRank spectrum-based algorithm for ranking, and achieved better performance.
(Download the slides of the talk here)
An algorithm for determining the most stable vacancy clusters in diamond lattice
Istvan LaszloDepartment of Theoretical Physics
Budapest University of Technology, Hungary
In diamond more than 500 electronic and more than 150 vibrational optical centers have been documented. Many of them are due to Vn vacancy centers, arising from the absence of n neighbouring carbon atoms from the diamond lattice. The number of all possible Vn vacancy clusters increases more than exponentially as a function of the missing number n of carbon atoms. The number of possible cases are respectively 1, 1, 88, 8112, 937194 for the values of n = 1, 3, 7, 10, 13.
We present an algorithm for generating all of the possible Vn vacancy structures up to n = 7 and we calculated also their relaxed geometries. For n = 8 through n = 14 we selectively generated a large number of vacancy clusters and obtained high stable structures and their energies. Calculations for larger clusters are in progress.
This is joint work with Miklos Kertesz and Brad Slepetz.
(Download the slides of the talk here)
Coset Graphs for LDPC Codes
Josef LauriDepartment of Mathematics
University of Malta, Malta
We show that a popular way of constructing quasi-cyclic LDPC codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes which have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv + 1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distribution of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.
This is joint work with C.J. Tjhai.
(Download the slides of the talk here)
Moiré patterns in double layer graphenic systems
Erwin LijnenDepartment of Chemistry and Institute for Nanoscale Physics and Chemistry
Katholieke Universiteit Leuven, Belgium
Moiré patterns are interference patterns which originate when two lattices are superimposed. They arise for instance when the two lattices are identical but have an angular mismatch or when their lattice parameters are slightly different. In both cases the combined system will exhibit long-range quasi-periodic patterns. Experimentally such patterns can be observed in STM (scanning tunneling microscope) experiments on graphitic surfaces or DWNT’s (double-walled nanotubes). The quasi-periodic nature of these systems however seriously hampers their theoretical investigation. One way to circumvent this is by searching for those conditions which create commensurable structures and are therefore easier to investigate.
We will discuss a general procedure for finding all possible commensurable twisted bilayer graphenic systems. Building further on these results, a more general model will be constructed which also allows for changes in the lattice parameters. We will show how this latter model can be successfully applied to classify and interpret the experimentally observed Moiré patterns in DWNT’s.
Crosscovers
Aleksander MalničInstitute of Mathematics, Physics and Mechanics
University of Ljubljana, Slovenia
To each unoriented edge e of a connected graph X assign an element ζe from a given abelian group Γ. The graph X(Γ,ζ) with V(X) * Γ as the vertex set, where (u,g) and (v,h) are adjacent whenever there is an edge e = uv in X and g+h = ζe, is called a crosscover. Crosscovers, an obvious generalization of Cayley plus graphs, are a special kind of covers. Some basic facts like regularity/irregularity, connectedness, and lifting automorphisms will be discussed.
This is joint work with Steve Wilson.
(Download the slides of the talk here)
Accelerated DVR methods for use in chemical physics
Anthony MeijerDepartment of Chemistry
University of Sheffield, UK
A time-dependent quantum dynamics program spends most of the computational time on the following operation to propagate the wave packet in time (assuming orthogonal coordinates):
HΨ = (T + V)Ψ = (∑i..n Ti + V)Ψ (1)
where H is the Hamiltonian matrix, T the total kinetic energy matrix, and V the potential energy matrix. Because there are no cross-terms in the kinetic energy operator we can write T as a sum over kinetic energy matrices for each of the degrees-of-freedom separately, Ti.
To evaluate the fundamental TiΨ operation, one often uses a suitable discrete variable representation of the kinetic energy operator. In this basis, the second derivative of the wave function Ψ(xi) at point xi is:
Ψ''(xi) = Ψ(xi)Δ0 + ∑j=1..N (Ψ(xi + jh) + Ψ(xi - jh))Δj (2)
where Δj are the DVR weights, which take the usual forms for e.g. a sinc-DVR [1] or a Gauss-Legendre DVR [2]. N is the size of the basis and h is the grid spacing.
In order to be able to tackle larger systems than currently possible, we have been investigating ways to turn a full N × N sinc-DVR matrix, which is used in Eq. 2 in case of scattering or vibrational coordinates, into a banded matrix with a band width 2n+1 << N. Within the confines of a DVR-based method most promising in this regard are methods, which effectively restrict the calculation to a subset of the full momentum space. A number of related methods based on sinc-DVRs have been reported on in the literature [3-5].
We have found a number of additional ways to obtain an appropriate subset of the full momentum space, thereby greatly extending this family of accelerated DVR methods. We have compared and contrasted the performance of all members of this family for a number of scattering and bound-state problems [6]. Some of our new methods are found to perform significantly better in both types of calculation.
This is joint work with Dean Morgan.
[1] Colbert, D.T., Miller, W.H. J. Chem. Phys. 1992, 96(3), 1982.
[2] Choi, S.E., Light, J.C. J. Chem. Phys. 1989, 90, 2593.
[3] Boyd, J.P. Comput. Methods. Appl. Mech. Eng. 1994, 103, 1.
[4] Mazziotti, D.A. J. Chem. Phys. 2002, 117(6), 2455.
[5] Gray, S.K., Goldfield, E.M. J. Chem. Phys. 2001, 115(18), 8331.
[6] Morgan, D., Meijer, A. J. H.M., Doyle, R.J. J. Chem. Phys. 2009, 130, 084114.
House of Graphs: what are interesting graphs?
Hadrien MélotDepartment of Computer Science
Université de Mons, Belgium
Several books gather examples and counterexamples of graphs that appear frequently or play a special role in graph theory. Also conjecture- making systems in graph theory such as GrInvIn, AutoGraphiX, Graffiti or GraPHedron allow the identification of some particular graphs that appear to be interesting (or relevant) for a given problem (e.g., as extremal graphs or as counterexamples). We start from the hypothesis that there are only a few such interesting graphs amongst the huge number of graphs. In other words, we believe that a few graphs or classes of graphs appear very frequently in numerous different problems of extremal graph theory.
We propose a framework to identify an initial set of interesting graphs by generating and solving a set of problems in an automated way, using the GraPHedron system. Also, we have designed a prototype of a web-based tool for researchers, called the House of Graphs. It can be seen as a repository of interesting graphs and complete lists for some graph classes, as well as an interface for obtaining and sharing information about them.
This is joint work with Gunnar Brinkmann, Kris Coolsaet and Jan Goedgebeur.
(Download the slides of the talk here)
The new version of newGRAPH
Marko MiloševićFaculty of Science and Mathematics
University of Niš, Serbia
newGRAPH is a fully integrated environment used for improving the research process in graph theory. Its purpose is to help a researcher pose, verify or disprove conjectures, and to enable computational experiments on graphs. It can also be a valuable tool in education in graph theory education. The new version presents several new features, such as an improved user interface, support for directed and weighted graphs, and calculation of some new invariants.
Density functional theory of many-particle systems
Barry PickupDepartment of Chemistry
University of Sheffield, UK
In 1965, Hohenberg and Kohn proved a remarkable theorem applying to the non- degenerate ground state wave function of a quantised many-particle system. The theorem states that the ground-state wave-function, and its expectation values, are unique functionals of the particle density. This simplifying discovery led to the DFT (density functional theory) methods which are widely used in quantum chemistry and solid state physics for calculations of electronic structure. These methods, however, are essentially "semi- empirical", since after 55 years of further research, the exact way in which quantities such as the total electronic energy depends upon the density is not known.
(Download the slides of the talk here)
Weavings of the cube and other polyhedra
Tibor TarnaiDepartment of Structural Mechanics
Budapest University of Technology and Economics, Hungary
The simplest weaving for the plane is the 2-fold, 2-way weave. It is of double thickness, with strands running in two directions crossing at right angles and passing alternately over and under at crossings to make a check pattern. The same basic ideas can be applied to a weaving of a closed basket on the surface of the cube. However, the strands are now of finite length, may have self-intersections, and give a check pattern that is necessarily disrupted at vertices. The strands of closed, 2-fold, 2-way weavings of the cube correspond to the central circuits of a 4-regular polyhedral graph with square and triangular faces, called an octahedrite by Deza and Shtogrin. Through dualisation, octahedrite graphs generate an infinite family of weavable polyhedra. We examine geometrical and combinatorial properties of these weavings on the cube, on other octahedrite duals and on a wider class of polyhedra, find a classification that echoes standard schemes for classification of viruses, fullerenes and geodesic domes, and show pictures of physical models of the woven polyhedra.
This is joint work with F. Kovács, Patrick W. Fowler and Simon D. Guest.
(Download the slides of the talk here)
Generation of generalized classes of cubic graphs
Nico Van CleemputDepartment of Applied Mathematics and Computer Science
Ghent University, Belgium
In this talk we describe a generator for more general classes of cubic graphs, like cubic graphs with loops, cubic multigraphs, cubic graphs with semi-edges (i.e. dangling edges) and any combination of these. The generator is based on a generator for simple cubic graphs presented in another talk. We will describe how the graphs can be constructed from simple graphs and will describe the isomorphism rejection methods which are based on McKay's canonical construction path method and the homomorphism principle. The problem is first translated to the generation of (multi)graphs with degree 1 and 3. In a later phase the vertices with degree 1 give rise to the loops and/or the semi-edges. We will also present the results of our generation.
This is joint work with Gunnar Brinkmann.
(Download the slides of the talk here)
Go to top