Program
The booklet of CSD8 (containing the abstracts and other information) is still available for download here. Below, you can access to the list of talks and abstracts. For most of the talks, you will find also the slides. List of plenary talks (click on a title to show / hide an abstract)
Many of my scientific discoveries would have been impossible without the help of computers.
During this presentation, I will present three of them, showing for each one how computers have
been a supportive partner for proving new theorems or characterizing graph families. I will first consider carbon chemistry. Alkanes are organic compounds which are exclusively
composed of carbon and hydrogen atoms. They can be represented by a carbon graph where each
carbon atom is a vertex, and chemical bonds are represented by edges. Chemists are interested in
determining which alkanes optimize Adriatic indices. Using my brains, I could prove necessary
and sufficient conditions for the existence of a carbon graph with given numbers mij of edges
with end-degrees i and j. These conditions can be formulated using a linear integer program.
Computers are therefore helpful to optimize Adriatic indices under the aforementioned conditions,
and this allowed me to characterize, for example, which alkanes have a minimum Randić index. The second result in on forbidden subgraph characterizations (FSC). Given a class of graphs F,
an FSC is a set of graphs H such that a graph G belongs to F if and only if no graph
of H is isomorphic to an induced subgraph of G. I will show how it is possible to automate
the generation of conjectures on FSCs. With this technique, using computers, I could generate conjectures
on the domination, independence and irredundance of graphs. Using my humain brains, I could then prove
the correctness of these conjectures. With the help of computer systems having interactive functions that allow to add or remove vertices
or edges, while indicating the impact on the value of graph invariants, it is possible to come up with
conjectures stating that among a family H of graphs, H* contains all those that minimize
a given invariant. In order to prove the correctness of such conjectures, one can use a proof technique
called proof by transformation. It consists in defining a set of transformations and in showing
that for each graph G in H which is not in H*, there exists at least one of these
transformations which allows to obtain a new graph G' in H with a better value of the considered
invariant. I will illustrate this proof technique with several examples.
Tait conjectured in 1884 that each cubic planar graph contains a
Hamilton cycle. Had the conjecture been true, it would have implied
the Four Color Theorem. However, it was disproved by Tutte in 1946.
Later on, other counterexamples with different structural properties
were found. On the other hand, for several subclasses of cubic planar
graphs hamiltonicity was proven. In general, the problem of founding a
Hamilton cycle in a cubic planar graph turned out to be NP-complete. All known conterexamples to Tait's conjecture contain (i) odd cycles
and (ii) faces of large size. That's why Barnette formulated in the
60s two conjectures in the form of sufficient conditions for the
hamiltonicity of cubic planar graphs: He conjectured that bipartite
cubic planar graphs, as well as cubic planar graphs with faces of size
at most 6, are hamiltonian. We will present results, methods and ideas
leading to a computer-assisted proof of the latter. The direct detection by the LIGO/Virgo collaboration of the gravitational waves
emitted by three coalescing black hole binaries (GW150914, GW151226 and
GW170401) has marked the beginning of gravitational wave (GW) astronomy.
The correct identification of these gravitational signals and the deduction of
the physical properties of the two objects as well as of the final black hole crucially
relies on gravitational waveform models. In this talk I will outline the complementarity
between numerical relativity (supercomputer) simulations and analytical waveform
models (based on the effective-one-body description of the two-body problem in
Einstein's general theory of relativity) to compute the (many thousands of)
analytical waveform templates needed for the actual LIGO/Virgo data analysis. Ramsey theory is often regarded as the study of how order emerges
from randomness. While originated in mathematical logic, it has
applications in geometry, number theory, game theory, information
theory, approximation algorithms, and other areas of mathematics
and theoretical computer science. Ramsey theory studies the conditions of when a combinatorial object
necessarily contains some smaller given objects. The central concept
in Ramsey theory is that of arrowing, which in the case of graphs
describes when colorings of larger graphs necessarily contain
monochromatic copies of given smaller graphs. The role of Ramsey
numbers is to quantify some of the general existential theorems
in Ramsey theory, always involving arrowing. The determination
of whether this arrowing holds is notoriously difficult, and thus
it leads to numerous computational challenges concerning various
types of Ramsey numbers and closely related Folkman numbers. This talk will overview how computers are increasingly used to
study the bounds on Ramsey and Folkman numbers, and properties
of Ramsey arrowing in general. This is happening in the area
where traditional approaches typically call for classical
computer-free proofs. It is evident that now we understand
Ramsey theory much better than a few decades ago, increasingly
due to computations. Further, more such progress and new
insights based on computations should be anticipated. A complete description of the state of a system requires in quantum mechanics measuring a complete set of observables. Typically this is prohibitive but we will discuss how it can be implemented in two experimental set ups where only a finite number of levels are accessible (i) Optically in 2Dimensional Photon-Echo Spectroscopy which allows resolving dynamical pathways on electronic and vibrational molecular quantum states. (ii) Electrically by addressing the electronic states of dopant structures in Si using voltage pulses. In both cases, the physical interaction between the perturbation and the state of the system is binary which is thus a natural setting for implementing bilinear logic. The logic operations that can be implemented are molecular decision trees and logic function decomposition, logic operations where all possible values of inputs are processed in parallel and the outputs are read simultaneously.
We will discuss the implementation of these logic operations both optically and electrically. Optically by probing the laser-induced dynamics of populations and coherences in a Rhodamine dye mounted on a short DNA duplex. The inputs are provided by the bilinear interactions between the molecule and the laser pulses, and the output values are read from the 2Dimensionnal molecular response at specific frequencies. We will then discuss the implementation of logic function decomposition on dopant molecules embedded in Si using electric addressing by pulses of gate voltages and reading the output by scanning tunneling spectroscopy. A set of n lines, spanned by the unit vectors v1,
v2, ..., vn in the d-dimensional
Euclidean space Rd is called equiangular, if there is a
common angle α ≥ such that for all i ≠ j we have
|⟨ vi, vj ⟩ | = α.
The concept of equiangular lines was introduced by J. Haantjes, and its basic
theory was developed by J.J. Seidel and his coauthors during the 1970s.
The problem of determining the maximum number of equiangular lines in dimension d,
denoted by N(d) was a central problem in the past, and has received considerable
attention also recently. In the 1970s it was already observed by Gerzon that N(d)
grows at most quadratically in d, in particular, N(d) ≤ d(d+1)/2; but it took
nearly 30 years until D. de Caen come up with the first quadratic lower bound on
N(d) in early 2000. B. Bukh in a breakthrough paper proved a linear bound on the
number of lines when the common angle α is fixed (i.e. when it does not
depend on d). While the problem has now been settled in the asymptotic sense, the exact value of
N(d) is only known for a few relatively small values of d. For years
there has been a consensus within the community that the cases d ≤ 18 are
completely understood, however, certain recently discovered gaps in the literature
revealed that several cases thought to be solved earlier are in fact actually open.
The following table summarizes to the best of my current knowledge the situation for d ≤ 23:
In this talk I will give an overview on some of these exciting new developments,
and as a case study I will explain how computer-aided experiments lead to the recent
rather surprising discovery of a system of 54 equiangular lines in R18.
List of contributed talks (click on a title to show / hide an abstract) We describe a search for plane-filling curves traversing all edges of a grid once.
The curves are given by Lindenmayer systems with only one non-constant letter.
All such curves for small orders on three grids have been found.
For all uniform grids we show how curves traversing all points once can be obtained from the curves found.
Curves traversing all edges once are described for the four uniform grids where they exist. Local operations on polyhedra that preserve the symmetries of the
polyhedron have a long history. If you e.g. consider the Archimedean
solids, already their names -- e.g. truncated cube or snub
dodecahedron -- say how they were obtained: by applying an operation
to a Platonic solid. Nevertheless it is not quite clear whether the
names date back to Archimedes or were introduced by Keppler, who
rediscovered the Archimedean solids. When asked what a "local symmetry
preserving operation" is, a typical answer would not be a definition,
but "for example truncation". Without a proper definition properties
of the class of such operations cannot be studied of course. In this
talk we will describe approaches of Goldberg, Caspar, Klug and Coxeter
to decorate polyhedra, show that the famous Goldberg/Coxeter operation
was in fact first proposed by Caspar and Klug, show that the often
cited paper by Goldberg has an -- obvious -- error and finally use the
(corrected) approach by Goldberg for a formal approach to local
operations on polyhedra that preserve symmetries. Studying invariants depending on graphs and induced subgraphs is currently a
growing research topic. Indeed, perfect graphs are well-known examples since the
chromatic number and the size of the largest clique must be equal in every induced
subgraph. However, some authors investigated particular classes of graphs determined by a characterization
of the induced subgraphs. For instance, cograph is a graph such that the path on 4 vertices is not
one of its induced subgraph. In this talk, we present a new computer software dedicated to the study of graphs and
their induced subgraphs, called GraphsInGraphs. We explain the structure of our system and
how it works. In the second part of the talk, some applications of the software are presented. (With Gilles Caporossi) When distances in graphs are involved, geodesic distance is usually considered.
If it is certainly the easiest to compute and to study, it turns out that other
distance measures are worth being considered. Klein and Randic (1993) proposed the resistance distance which is based upon an analogy
between the graph and a system of resistors.
From a technical point of view, this distance involves the laplacian of the graph (also named Kirchhoff matrix), and its pseudo inverse.
The properties of the pseudo inverse of the laplacian makes it a good candidate for spacial representation of graphs. Random walks through a graph is a process associated to the same mathematical model, (Stephenson and Zelen, 1989; Newman, 2005)
and may be used for another distance definition, the expected random walk distance (Camby et al., 2016). In this talk, we will explore various distance measures in graphs derived from different contexts that are
meaningful in the context of complex networks analysis and some of their respective porperties are discussed.
Finally, some conjectures obtained by AutoGraphiX-III will be proposed concerning their bounds and the graphs
for which they are attained. (With Eglantine Camby)
The proposed talk is a follow-up to a former presentation at CSD7 in Richmond in 2015, where the chemical interpretation of the matching (acyclic) polynomial of a chemical graph serving to define the topological resonance energy of its cycles, namely their quantitative aromaticity, was developed.
Within this context, the nth algebra of the Cayley-Dickson process, 𝔸n, of vectorial dimension 2n, is formally associated with the class of polycyclic graphs Gn with n fundamental circuits: 2n is the number of hyper-generalized circuits in Gn (including the empty circuit). Indeed, 𝔸n is multiplicatively generated from the canonical basis set of 𝔸n-1 and a new hyper-complex element associated to the fundamental circuit added to Gn-1 to define Gn. The canonical basis set of 𝔸n contains 1 = e0 and 2n-1 hyper-complex numbers er, r = 1,…, 2n –1 such that er2 = -1 (more generally, the multiplication table of the canonical basis elements and their negative shows that they constitute an a loop Ln). The generating set of this basis contains only n of the hyper-complex numbers er, r = 0,…, n–1. For examples: The hyper-complex number er is actually the normalized edge-weighting coefficient allowing "acyclization" of circuits containing the edge of Gn weighted by er, with all the other edges weighted by +1 (or –1). Edge weighting by -1 corresponds to the Moebius-twisting of circuits containing this edge. The process is a generalization of a method proposed by A. Graovac et al. for bicyclic graphs with quaternionic weights. All the partial matching polynomials of Gn are found to be calculated from the corresponding formal secular determinants by assuming that the standard multiplication rules (commutativity, associativity, existence of an iso-normed inverse) apply to those particular canonical elements of the algebra (which however quickly becomes non-commutative for n ≥ 2, not associative for n ≥ 3...). Though related to the loop structure of Ln, the numerical observation is not proven in the general case, but its generalization is proposed as a conjecture. In several markets, such as the electricity market, spot prices are determined via a bidding system involving an oligopoly of producers and a system operator. Once time-dependent price-quantity bids are placed by each producer for its production units, the system operator determines a production schedule that meets demand at minimal cost. The spot price charged to the customers is then set to the marginal production cost. Fampa et al. have considered the problem faced by a profit-maximizing producer, whose bids depend on the behaviour of the system operator, as well as the stochastic nature of final demand, and that can be cast within the framework of stochastic bilevel programming. In this presentation, we consider an enhanced model that embeds two key features, namely the uncertainty related to competitors' bids, as well as the impact of spot prices on demand. Our aim is to develop efficient solution algorithms for addressing instances involving a large number of scenarios. Under the assumptions that production costs are linear and that demand is piecewise constant, the bilevel model can be reformulated as a large mixed integer program. Although this problem becomes numerically intractable as the number of scenarios increases, it becomes much simpler when producers are allowed to place different price-quantity bids for a given generator. This relaxation of the original problem can than be solved in polynomial time by a dynamic programming algorithm. This algorithm can then be adapted to heuristically solve the original problem, yielding very quickly feasible solutions characterized by small optimality gaps. The performance of the method has been tested on instances inspired from the Brazilian Electric System National Operator. (With Martine Labbé, Etienne Marcotte, Patrice Marcotte and Gilles Savard)
Over the years, several softwares and tools have appeared in order to help in to
find conjectures in Extremal Graph Theory. One of these tools is PHOEG which is
currently being developed in our team as a sucessor to GraPHedron. The conjectures
usually consist in the definition of a class of graphs, called extremal graphs,
that realize a bound for some graph invariant given some constraints. These
constraints can vary from fixing the value of another invariant to restricting
the graphs to a specific class. An example of a graph invariant is the average eccentricity. Let G = (V,E) be
a graph and v in V be a vertex of G, we define the eccentricity of v as
the maximal distance between v and any other vertex of G. The average
eccentricity as well as the average distance are used in a conjecture
(Aouchiche, PhD Thesis, 2006) stating that among all connected graphs on n
vertices, the graph that maximizes the difference between the average
eccentricity and the average distance is the path on n vertices. This conjecture is one among many others generated by the existing tools.
Indeed, while some of them provide support to filter trivial or false
conjectures, they still produce an important number of non trivial ones. To help researchers in handling this quantity of conjectures, we develop a
PHOEG module called Transproof. This module enables its users to study graph
transformations. These transformations can then be used in proving the
extremality of a class of graphs. This is done by proving that any non extremal
graph concerned by the conjecture can be transformed into a new graph whose
value for the studied invariant is strictly closer to the conjectured bound.
Such a proof technique is called a proof by transformation and is widely used in
Extremal Graph Theory. Transproof uses a graph database to store graph transformations in the form of
a metagraph with graphs as its vertices and applications of transformations as
its arcs. It uses an exact approach on small graphs and provides the researchers
with means to explore graph transformations as well as to test ideas to prove
the conjectures. In this talk, we explain the difficulties encountered when building and
exploiting this data and the ideas used to handle them. Using the conjecture
explained above, we also illustrate how Transproof can help to raise ideas in
the design of a proof by transformation.
(With Pierre Hauweele and Hadrien Mélot) In the simple Hückel version of Ernzerhof’s Source-and-Sink Potential (SSP) model of molecular conduction, the transmission of electrons through an unsaturated organic molecule is calculated by modifying the adjacency matrix of the molecular graph, G. Two extra vertices, the source and the sink, are connected to the graph, and carry complex weights that embody the scattering-type boundary conditions of the conduction problem. In the formulation that we use, a general solution for the transmission as a function of energy can be obtained in terms of four characteristic polynomials, of G itself and three subgraphs. Use of these polynomials and their spectral decompositions allows formulation of selection rules for conduction, and definition of generic classes of molecular conductors and insulators in terms of graph nullity. Progress will also be reported on adding the effects of electron interaction to the Hückel ‘empty molecule’ picture, in particular on the construction of a model that accounts for the statistical effect of the Pauli Exclusion Principle on electron flow through occupied orbitals. (With Barry Pickup, Irene Sciriha and Martha Borg) A novel matching based heuristic algorithm designed to detect specially formulated
infeasible {0,1} IPs is presented. It either detects an infeasible IP or exits undecided.
It does not solve an IP. We call it the triple overlay matching based closure algorithm.
Input to the algorithm is a set of nested doubly stochastic subsystems and a set E of instance
defining variables set at zero level. We view the set of all solutions of the IP as an n2 x n2
block permutation matrix Q whose components are {0,1} variables. Each n x n block (u,i) is n x n
permutation matrix P where block (u,i) contains pu,i in position (u,i). Individual solutions
are n2 x n2 block permutation matrices, each with block structure P. The algorithm deduces
additional variables at zero level until either a constraint is violated and the IP is infeasible,
or no more variables can be deduced at zero level and the IP is undecided. All feasible IPs, and
all infeasible IPs that fail to be detected infeasible are undecided. The algorithm is successfully
applied to small test set of specially formulated infeasible {0,1} IP instances of the
Hamilton cycle decision problem. Models of both the graph and subgraph isomorphism decision
problems are also presented. They help illustrate ease of applicability. The algorithm is also
easy to modify. Increased levels of nested doubly stochastic subsystems can be implemented dynamically.
The algorithm is designed for parallel processing and inclusion of techniques in addition to matching. (With Edward Swart) We will present a new algorithm to generate all non-isomorphic hypohamiltonian
graphs of a given order. (A graph G is hypohamiltonian if G is non-hamiltonian and G-v
is hamiltonian for every v ∈ V(G)). Using this algorithm, we were able to generate complete lists of hypohamiltonian graphs of
much larger orders than what was previously possible. This allowed us amongst others to find
the smallest hypohamiltonian graph of girth 6 and to show that the smallest planar
hypohamiltonian graph has order at least 23. (With Carol Zamfirescu) Cubic polyhedra with icosahedral symmetry where all faces are pentagons or hexagons have been studied in chemistry and biology as well as mathematics. Parameterized operations to construct all such polyhedra were first described by Goldberg in 1937. But the idea of applying operations to seed polyhedra goes much further back, to Euclid, Kepler, and others. Some of these operations are classified by Conway's polyhedron notation. We generalized Goldberg's approach to a systematic one encompassing all local symmetry-preserving operations on polyhedra. This can be further expanded in order to allow operations that only preserve orientation-preserving symmetries, including all of Goldberg's and Conway's operations. Using this new framework, we can generate all of these operations, and answer several questions which were previously impossible to ask.
Extremal graph theory aims to determine bounds for graph invariants as well as
the graphs that attain those bounds. For example, one can study the eccentric
connectivity index, ECI, a discriminating topological descriptor in
biochemistry. The eccentric connectivity index of a given simple, undirected,
connected, graph G, is defined as the sum (among all vertices) of the product of the degree and the eccentricity of each vertex. Some invariants (including ECI) may be hard to compute for a human
and it might be difficult for one to develop intuitions about how they
meld with graph structure. There is thus a need for tools to help researchers explore the intricacies
of these invariants. This talk will present some aspects of the PHOEG system,
an ecosystem of tools we are currently developing to help us with our research
in Extremal Graph Theory. We will focus on the feature of querying a "big"
database of graphs in order to check conjectures or infer new ones. It can be
used to quickly confirm/infirm/obtain a conjecture on the problem of maximizing
ECI under the constraints of fixing the graphs order and size, as well
as quickly lighten or kill ideas in the process of seeking a proof for it.
(With Gauvain Devillez and Hadrien Mélot) Over the last ten years, the culture of medical data sharing has been widely expanded to constitute databases enough representative. This worthy initiative encouraged researchers from various fields of expertise to consider medical issues, and notably, to provide clinicians with support in making a diagnosis. Accessible online, the open medical datasets may include, for each subject, clinical data (e.g. age, gender), images (e.g. magnetic resonance images), signals (e.g. electrocardiography, electroencephalography) and/or other biological data (e.g. genotypes). In particular, for children mental disorders, there is a lack of pathophysiological bases universally recognized. Hence, the diagnosis is based on subjective observations collected from the environment of the children (parents, teachers, etc.). Moreover, kids’ disorders present common features, making these troubles difficult to dissociate. Incidentally, on a given trouble diagnosis, the agreement among practitioners, measured by the Kappa statistics, may still be improved. The development of predictive models based on physiological data could help the clinical neuroscience to make assessments more objective. To that end, several studies considered the application of Data Mining techniques on medical data. Yet beyond a simple data analysis, it is critically important to integrate the questioning and requirements specific to the medical domain in the process of Data Mining. The foremost requirement of practitioners is to be able to justify and validate the diagnosis based on the recommendation provided by Data Mining. Besides, the predictive model should be able, on a per-patient basis, to provide a readable relationship between the input data and the diagnosis through a decision chain. For such purposes, the recommendation must be based on an interpretable (and preferably, interpreted) model. Thus, it remains essential to set the properties of interpretability in the sense of medical Data Mining. Furthermore, in case of a neurological diagnosis, should predictive models make errors, it must be ensured that these wrong predictions have the lowest impact on patients. Indeed, a model having a low ability to detect healthy patients is far from being cautious, in the sense that they are exposed to the risk of being prescribed an unnecessary medication. The opposite situation is less restrictive: if a model has a low ability to detect pathological patients, the detection of the trouble may be just delayed in time. Finally, medical data include several sources of heterogeneities, e.g. the harmonization of protocols is missing; cultural and social factors influence the etiology and epidemiology of troubles. In view of these specifics of medical Data Mining, we propose a critical consideration on learning schemes, algorithms and features that should be used to provide the most appropriate aid-in-diagnosis models for neurological disorders. (With Fabian Lecron and Philippe Fortemps) The study of fullerenes is an important part within Chemistry.
Fullerenes are carbon molecules that can be modelled by a 3-regular plane
graph where all faces are pentagons or hexagons. From Euler's formula it can
be proven that fullerenes have exactly 12 pentagons. Nanotubes are a type of
fullerene where the 12 pentagons are distributed over two patches with 6 pentagons
each. Those patches are called nanocaps and they are connected by a long tube of hexagons. In a fullerene, where outside of the caps you have only hexagons, the boundary of the caps
has the same structure. Nanojoins are structures that connect two or even more caps with
(possibly) different parameters with each other. These structures also contain heptagons and possibly extra pentagons. This talk will describe an algorithm that was developed to generate the possible structures
of these nanojoins. It takes as input the cap parameters and generates all possible structures
with a given amount of heptagons up to a certain size.
The curvature at a vertex v of an embedding is defined to be
1 - deg(v)/2 + the sum over the faces f incident at v of 1/size(f).
Prisms and anti-prisms are polyhedra that can be arbitrarily
large with strictly positive curvature at every vertex.
A PCC-graph is a graph embedded in the plane that is not a
prism or an anti-prism that has strictly positive curvature
at every vertex. One open question is to determine the maximum
number of vertices in a PCC-graph. We present some
new results for this problem. (With Patrick Fowler and Paul Oldridge) We present a branch-and-price framework for solving the b-coloring problem, i.e. a vertex coloring problem where each color class contains at least one vertex, called b-vertex, adjacent to every other color. We suggest an approach based on an integer programming formulation, called independent set formulation, that involves an exponential number of variables. In order to deal with them, we solve the problem via column generation, where variables are dynamically introduced into the model by iteratively solving a pricing problem. We took advantage of the structure of the problem to reformulate the pricing problem as a generic version of the weighted independent dominating set problem. We exploit the fact we can decompose our pricing problem in many small subproblems in order to accelerate the solution methods, instead of solving a unique large problem. Although requiring the solution of a difficult subproblem as well as needing sophisticated branching rules, this approach based on a Dantzig-Wolfe decomposition scheme, provides tighter LP relaxation and eliminates the symmetry that usually affects the formulation of the b-coloring. We also developed a compact formulation for the b-coloring based on the representatives formulation introduced by Campêlo et al. by adding constraints that ensure the b-coloring property, in order to compare the quality of our approach in terms of elapsed time to solve the problem and time to find a feasible solution.
Despite the importance of the problem, to date, there exist in literature no contributions concerning exact methods exploiting a column generation paradigm embedded in a Branch-and-Bound scheme (i.e. a Branch-and-Price algorithm) to solve the b-Coloring problem.
We show that such approach appears efficient to solve moderate to big scale instances and it turns out to be useful for obtaining good lower bounds that can be used to speed up the procedure.
Some implementation details and computational experience are presented. (With Marcio Costa Santos, Martine Labbé and Bernard Fortz) The Wiener index W(G) of a simple connected graph G is defined as
the sum of distances over all pairs of vertices in a graph. We denote by W[Tn]
the set of all values of Wiener index for a graph from the class Tn of trees on n vertices.
The largest interval of contiguous integers contained in W[Tn] is denoted by Wint[Tn].
The following conjectures were posed in literature regarding the cardinality of sets W[Tn] and Wint[Tn]. Conjecture 1. (Knor, Skrekovski and Tepeh, 2016) The cardinality of W[Tn] equals (1/6)n3 + O(n2). Conjecture 2. (Krnc and Skrekovski, 2016) The cardinality of Wint[Tn] equals O(n3). We first prove that the value of the Wiener index of a tree for odd n must be even number.
Given the upper and lower bound for Wiener index on Tn (the value for path and star respectively),
this result implies that in the case of odd n the set Wint[Tn] has to be redefined as the largest
interval of contiguous even integers contained in W[Tn] and that Conjecture 1 has to be reformulated
by stating that in the case of odd n the cardinality of W[Tn] equals (1/12)n3 +O(n2). Given these
reformulations we prove that both conjectures are true. Moreover, we prove the strongest
version of Conjecture 2 in terms of O(n3). The Curie symmetry principle, which asserts that the symmetries of the
cause must also be contained in the effects, no longer holds in
general for non-linear partial differential equations (PDE) with
possibly infinitely many solutions.
In this context, one has to restrict to “low energy” solutions.
Solutions with the lowest energy (ground states) usually — though not
always — possess all the symmetries of the problem.
For solutions with the lowest energy among sign-changing ones,
only part of the symmetries is preserved.
In this talk, I will consider the simple problem
-Δ u = |u|p-2 u with zero Dirichlet boundary conditions on a
square domain and show how numerical computations
help to discover the residual symmetry of the least-energy
sign-changing solutions as well as to prove that
what the simulation tells is rigorously valid. By Euler's formula, there are k-regular 3-connected planar graphs for three
values of k: 3, 4, or 5. Denote by ck, resp. pk, the order of the smallest
non-hamiltonian, resp. non-traceable, k-regular 3-connected planar graph. Tait conjectured in 1884 that every 3-regular 3-connected planar graph is hamiltonian.
This conjecture became famous because it implied the Four Colour Theorem (which at that
time was still the Four Colour Problem). However, Tait's conjecture turned out to be false
and the first to construct a counterexample was Tutte in 1946. The smallest counterexample
is due to Lederberg (and independently, Bosák and Barnette) and has order 38. That this is
indeed the smallest possible counterexample was shown by Holton and McKay after a long series
of papers by various authors, e.g., Butler, Barnette and Wegner, and Okamura. This settles that
c3=38. Combining work of Knorr and T. Zamfirescu, it has been shown that 54 ≤ p3 ≤ 88. Non-hamiltonian 4-regular 3-connected planar graphs have been known for a long time.
Following work of Walther and Sachs, Zaks proved that there exists a non-hamiltonian 4-regular
3-connected planar graph of order 209. Applying a technique by Sachs to transform a non-hamiltonian
3-regular 3-connected planar graph into a non-hamiltonian 4-regular 3-connected planar graph,
Bosák showed that c4 ≤ 171. Using the same technique by Sachs and the non-traceable 3-regular
3-connected planar graph on 88 vertices by T. Zamfirescu, it can be shown that p4 ≤ 396. Zaks showed for the 5-regular case that c5 ≤ 532 and that p5 ≤ 1232. Owens strongly
improved these bounds for non-hamiltonian and non-traceable 5-regular 3-connected planar graphs.
More specifically, he showed that c5 ≤ 76 and that p5 ≤ 128. The main focus of the talk will be the 4-regular case for which we show that there exists
a non-hamiltonian 4-regular 3-connected planar graph with 39 vertices. We also present the
result of computations that show that every non-hamiltonian 4-regular 3-connected planar graph
has at least 33 vertices. This implies that 33 ≤ c_4 ≤ 39. Using similar building blocks,
we also construct a non-traceable 4-regular 3-connected planar graph on 90 vertices which improves
the upper bound of p4 to p4 ≤ 90. Furthermore, we discuss a small improvement to the 5-regular
non-traceble case by showing that p5 ≤ 108. For the 3-regular case, we turn our attention
towards cyclically-4-edge-connected planar graphs. (With Carol Zamfirescu)
[Download slides]
Computers versus human brains : a cooperative game for scientific discoveries
Hamilton cycles in cubic planar graphs
Gravitational waves from binary black hole coalescence: interfacing supercomputer calculations with analytical methods
[Download slides]
Computers in Ramsey Theory
[Download slides]
Optical and electrical parallel molecular and nanoscale computing
[Download slides]
New Results on Equiangular Lines
d
2
3-4
5
6
7-13
14
15
16
17
18
19
20
21
22
23
N(d)
3
6
10
16
28
28-29
36
40-41
48-50
54-60
72-75
90-95
126
176
276
[Download slides] [Download paper]
Plane-filling curves on all uniform grids
[Download slides]
Goldberg operations as a formal approach to operations on polyhedra
[Download slides]
The software GraphsInGraphs and applications
Exploration of distances in graphs
[Download slides]
Total and partial matching polynomials of polycyclic graphs:
canonic hyper-complex numbers of Cayley-Dickson algebra
in the quantification of chemical aromaticity
Dynamic programming approach for bidding problems on day-ahead markets
[Download slides]
Transproof : Computer assisted graph transformations
Models for molecular conduction
Using Matching to Detect Infeasibility of Some Integer Programs
[Download slides]
Generation of hypohamiltonian graphs
[Download slides]
Local Symmetry-preserving Operations
[Download slides]
PHOEG Helps Obtaining Extremal Graphs
Specifics of Medical Data Mining for Neurological Diagnosis Prediction
[Download slides]
The generation of nanojoins
Polyhedra with Positive Combinatorial Curvature
A Column Generation Approach for the b-Coloring problem in graphs
Wiener index and the inverse interval problem for trees
[Download slides]
A computer assisted proof of the symmetry of solutions to a PDE
[Download slides]
Non-Hamiltonian and Non-Traceable Regular 3-Connected Planar Graphs