## Science Communication

### Talks by our Members and Guests

Understanding evolutionary relationships, particularly in the context of hybridization and horizontal gene transfer, requires inferring phylogenetic networks rather than traditional trees. Recent methods based on quartet concordance factors have addressed the challenges of inferring such networks, where these factors represent the probabilities of 4-taxon relationships within gene trees. Previous research has shown that certain network topologies and numerical parameters can be identified, however, gaps remain in understanding the full topology of level-1 phylogenetic networks under the network multispecies coalescent model. In this talk, we investigate what level-1 network features are identifiable by studying the ideals defined by quartet concordance factors.

We address both the identifiability of the network, as well as the numerical parameters, and will give answers to a number of identifiability problems related to the 3-cycles of the network.

Joint work with Elizabeth S. Allman, Hector Baños and John A. Rhodes

We address both the identifiability of the network, as well as the numerical parameters, and will give answers to a number of identifiability problems related to the 3-cycles of the network.

Joint work with Elizabeth S. Allman, Hector Baños and John A. Rhodes

**
https://uni-leipzig.zoom-x.de/j/67188613169?pwd=d1lEbzRDWjJkdmxmOW1uYTBPblM2dz09
**

A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue

such that all nonzero kernel eigenvectors have no zero entry.

If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they

are connected, non-bipartite, and have no leaves.

Nut graphs have been established in the literature for quite some time: they were

introduced in 1998 by Sciriha and Gutman. However, only recently important chemical

applications involving this class of graphs were uncovered, which makes them

quite attractive for further investigation and research.

In this talk, we present some symmetry properties of nut graphs. We show that a nut

graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,

edge-transitive nut graphs do not exist. Moreover, we give infinite families of

vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs

with two orbits of vertices and three of edges.

Several constructions for nut graphs from smaller starting graphs are known: double subdivision

of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with

preservation of the degree sequence (the so-called Fowler construction). To these we add

multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).

Finally, we show by construction that every finite group can be represented as the group of

automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required

to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.

This is joint work with Tomaž Pisanski and Patrick W. Fowler.

such that all nonzero kernel eigenvectors have no zero entry.

If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they

are connected, non-bipartite, and have no leaves.

Nut graphs have been established in the literature for quite some time: they were

introduced in 1998 by Sciriha and Gutman. However, only recently important chemical

applications involving this class of graphs were uncovered, which makes them

quite attractive for further investigation and research.

In this talk, we present some symmetry properties of nut graphs. We show that a nut

graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,

edge-transitive nut graphs do not exist. Moreover, we give infinite families of

vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs

with two orbits of vertices and three of edges.

Several constructions for nut graphs from smaller starting graphs are known: double subdivision

of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with

preservation of the degree sequence (the so-called Fowler construction). To these we add

multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).

Finally, we show by construction that every finite group can be represented as the group of

automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required

to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.

This is joint work with Tomaž Pisanski and Patrick W. Fowler.

**
https://uni-leipzig.zoom.us/j/68659155596?pwd=ZzJWVWF1WCtqSndaNi9GVFZ4ZWx2UT09
**

A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue

such that all nonzero kernel eigenvectors have no zero entry.

If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they

are connected, non-bipartite, and have no leaves.

Nut graphs have been established in the literature for quite some time: they were

introduced in 1998 by Sciriha and Gutman. However, only recently important chemical

applications involving this class of graphs were uncovered, which makes them

quite attractive for further investigation and research.

In this talk, we present some symmetry properties of nut graphs. We show that a nut

graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,

edge-transitive nut graphs do not exist. Moreover, we give infinite families of

vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs

with two orbits of vertices and three of edges.

Several constructions for nut graphs from smaller starting graphs are known: double subdivision

of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with

preservation of the degree sequence (the so-called Fowler construction). To these we add

multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).

Finally, we show by construction that every finite group can be represented as the group of

automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required

to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.

This is joint work with Tomaž Pisanski and Patrick W. Fowler.

such that all nonzero kernel eigenvectors have no zero entry.

If the isolated vertex is excluded as trivial, nut graphs have seven or more vertices; they

are connected, non-bipartite, and have no leaves.

Nut graphs have been established in the literature for quite some time: they were

introduced in 1998 by Sciriha and Gutman. However, only recently important chemical

applications involving this class of graphs were uncovered, which makes them

quite attractive for further investigation and research.

In this talk, we present some symmetry properties of nut graphs. We show that a nut

graph $G$ always has at least one more edge orbit than it has vertex orbits. In particular,

edge-transitive nut graphs do not exist. Moreover, we give infinite families of

vertex-transitive nut graphs with two orbits of edges, and infinite families of nut graphs

with two orbits of vertices and three of edges.

Several constructions for nut graphs from smaller starting graphs are known: double subdivision

of a bridge, four-fold subdivision of an edge, a construction for extrusion of a vertex with

preservation of the degree sequence (the so-called Fowler construction). To these we add

multiplier constructions that yield nut graphs from regular graphs (that are not necessarily nut graphs).

Finally, we show by construction that every finite group can be represented as the group of

automorphisms of infinitely many nut graphs. It is further shown that these graphs may be required

to be regular; the cases where the degree is required to be $8, 12, 16, 20$ or $24$ are realised explicitly.

This is joint work with Tomaž Pisanski and Patrick W. Fowler.

Autocatalytic chemical networks are dynamical systems whose

linearization around zero

has a positive Lyapunov exponent; this exponent gives the growth rate

of the system in the diluted regime, i.e. for near-zero

concentrations.

We prove here optimal estimates on the growth rate and on the

corresponding quasi- stationary distribution of species, yielding

their orders of magnitude as a function of kinetic time scales. The

estimates are based on a multi-time scale decomposition algorithm

inspired from field theory, and give accurate predictions for the

collective time behavior of the concentrations. Conversely, it is in

principle possible to reconstruct to a large extent the reaction

network and kinetic time scales from a series of carefully devised

experiments.

linearization around zero

has a positive Lyapunov exponent; this exponent gives the growth rate

of the system in the diluted regime, i.e. for near-zero

concentrations.

We prove here optimal estimates on the growth rate and on the

corresponding quasi- stationary distribution of species, yielding

their orders of magnitude as a function of kinetic time scales. The

estimates are based on a multi-time scale decomposition algorithm

inspired from field theory, and give accurate predictions for the

collective time behavior of the concentrations. Conversely, it is in

principle possible to reconstruct to a large extent the reaction

network and kinetic time scales from a series of carefully devised

experiments.

**
https://uni-leipzig.zoom.us/j/64504129528?pwd=ZmVMTnNlN2ZzK1FRUDAzVTZnZEVVdz09
**

Understanding genomes' evolutionary history is key to comprehending genes' role in species diversification and adaptation. Moreover, identifying ortholog and paralog genes is fundamental for comparative biology studies. Still, detecting orthology through sequence similarity remains challenging and computationally intensive for gene families containing numerous duplications and losses.

In this talk, I will first introduce REvolutionH-tl, a tool designed for orthology prediction and reconstruction of evolutionary histories free of horizontal gene transfers. Furthermore, I show how REvolutionH-tl can be used to estimate the evolution of antibiotic-resistance genes in a selected group of bacteria.

REvolutionH-tl employs a novel graph-based method to identify biologically plausible gene best-matches, as well as determine orthology and paralogy relationships. This information naturally entails knowledge about gene and species tree topology, which is further reconstructed and unified in an evolutionary scenario that explicitly delineates gene evolution across species.

The accuracy of REvolutionH-tl is comparable to competing tools at substantially reduced computational cost. It is freely available at https://pypi.org/project/revolutionhtl/. REvolutionH-tl stands as a potent addition to the toolkit of comparative genomics researchers. Its significance stands out in the age of massive genome sequencing, where efficient methods to organize and make sense of thousands of genes across numerous species are indispensable.

In this talk, I will first introduce REvolutionH-tl, a tool designed for orthology prediction and reconstruction of evolutionary histories free of horizontal gene transfers. Furthermore, I show how REvolutionH-tl can be used to estimate the evolution of antibiotic-resistance genes in a selected group of bacteria.

REvolutionH-tl employs a novel graph-based method to identify biologically plausible gene best-matches, as well as determine orthology and paralogy relationships. This information naturally entails knowledge about gene and species tree topology, which is further reconstructed and unified in an evolutionary scenario that explicitly delineates gene evolution across species.

The accuracy of REvolutionH-tl is comparable to competing tools at substantially reduced computational cost. It is freely available at https://pypi.org/project/revolutionhtl/. REvolutionH-tl stands as a potent addition to the toolkit of comparative genomics researchers. Its significance stands out in the age of massive genome sequencing, where efficient methods to organize and make sense of thousands of genes across numerous species are indispensable.

Chemical reaction networks (CRNs) play a central role in the mathematical modeling of complex systems due to their capacity to capture a wide range of nonlinear phenomena. Autocatalysis is a topological feature with essential consequences for dynamical organization in CRNs for conceptual, theoretical, and practical reasons. In this talk, I will review different definitions of autocatalysis and discuss the polyhedral geometry induced by the minimal autocatalytic subnetworks (MASs) on the stoichiometric subspace. I will discuss linear-programming algorithms for exhaustively enumerating and a scheme for visualizing the list of MASs in a generic CRN. Next, I will introduce a formal paradigm for coarse-graining realistic biochemical reactions using their conservation laws and display the ‘combinatorial explosion’ of MASs in fully connected hypergraphs of CRNs with one conservation law. Finally, I will discuss applications of autocatalysis in understanding the origins of life and economics. (For details, see https://arxiv.org/abs/2303.14238 .)

The modular decomposition (MD) of an undirected graph G is a natural

construction to capture key features of G in terms of a rooted labeled tree

(T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime".

If a graph G does not contain prime modules, then all structural information of G

can be directly derived from its MD tree (T,t). As a consequence, many hard

problems become polynomial-time solvable on graphs without prime modules, since

the MD tree serves as a guide for algorithms to find efficient exact solutions

(e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).

However, the class of graphs without prime modules (aka cographs) is rather

restricted. We introduce here the novel concept of explicit modular decomposition

that aims at replacing "prime" vertices in the MD tree by suitable substructures

to obtain 0/1-labeled networks (N,t). Understanding which graphs can be

explained by which type of network does not only provide novel graph classes but

is crucial to understand which hard problem can be solved on which graph class

efficiently. We will mainly focus on graphs that can be explained by networks

(N,t) whose bi-connected components are simple cycles. These graphs are called

GaTEx, can be recognized in linear-time and are characterized by a set of 25

forbidden induced subgraphs. In particular, GaTEx graphs are closely related to

many other well-known graph classes such as P4-sparse and P4-reducible graphs,

weakly-chordal graphs, perfect graphs with perfect order, comparability and

permutation graphs. As a consequence, one can prove that many hard problems

become linear-time solvable on GaTEx graphs as well.

construction to capture key features of G in terms of a rooted labeled tree

(T,t) whose vertices are labeled as "series" (1), "parallel" (0) or "prime".

If a graph G does not contain prime modules, then all structural information of G

can be directly derived from its MD tree (T,t). As a consequence, many hard

problems become polynomial-time solvable on graphs without prime modules, since

the MD tree serves as a guide for algorithms to find efficient exact solutions

(e.g.\ for optimal colorings, maximum clique, isomorphism test, ... ).

However, the class of graphs without prime modules (aka cographs) is rather

restricted. We introduce here the novel concept of explicit modular decomposition

that aims at replacing "prime" vertices in the MD tree by suitable substructures

to obtain 0/1-labeled networks (N,t). Understanding which graphs can be

explained by which type of network does not only provide novel graph classes but

is crucial to understand which hard problem can be solved on which graph class

efficiently. We will mainly focus on graphs that can be explained by networks

(N,t) whose bi-connected components are simple cycles. These graphs are called

GaTEx, can be recognized in linear-time and are characterized by a set of 25

forbidden induced subgraphs. In particular, GaTEx graphs are closely related to

many other well-known graph classes such as P4-sparse and P4-reducible graphs,

weakly-chordal graphs, perfect graphs with perfect order, comparability and

permutation graphs. As a consequence, one can prove that many hard problems

become linear-time solvable on GaTEx graphs as well.

In this talk, I will give an overview on the relationship between the

structure of a reaction network and the possible dynamics of the

species concentrations. To this aim, I will focus on systems with

sufficiently nonlinear interaction functions (parameter-rich kinetic

models) and address the structure of the Jacobian matrix at a steady

state. Results are of two kinds: “existence” results that assert the

possibility of a dynamical feature for a specific choice of parameter

and “exclusion” results that assert a dynamical feature independently

from any choice of parameters. I will provide examples of both types.

structure of a reaction network and the possible dynamics of the

species concentrations. To this aim, I will focus on systems with

sufficiently nonlinear interaction functions (parameter-rich kinetic

models) and address the structure of the Jacobian matrix at a steady

state. Results are of two kinds: “existence” results that assert the

possibility of a dynamical feature for a specific choice of parameter

and “exclusion” results that assert a dynamical feature independently

from any choice of parameters. I will provide examples of both types.

*What?*

TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create

graphic elements in LaTeX. Not only graphs, but all kind of figures you

might think of.

*When/Where?*

Session 1: Tuesday November 21st, 11am to 1pm, in room 109.

There might be a zoom link to attend remotely, if interest in such an

arrangement is shown. Recording of the sessions will also be considered.

*For who?*

Any LaTeX user (not only graph enthusiasts) interested in creating nice

figures for their papers, posters, presentations...

The first session will introduce the basics. No previous knowledge of TikZ

is required.

TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create

graphic elements in LaTeX. Not only graphs, but all kind of figures you

might think of.

*When/Where?*

Session 1: Tuesday November 21st, 11am to 1pm, in room 109.

There might be a zoom link to attend remotely, if interest in such an

arrangement is shown. Recording of the sessions will also be considered.

*For who?*

Any LaTeX user (not only graph enthusiasts) interested in creating nice

figures for their papers, posters, presentations...

The first session will introduce the basics. No previous knowledge of TikZ

is required.

*What?*

TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create

graphic elements in LaTeX. Not only graphs, but all kind of figures you

might think of.

*When/Where?*

Session 2: Tuesday November 28th, 11am to 1pm, in room 109.

There might be a zoom link to attend remotely, if interest in such an

arrangement is shown. Recording of the sessions will also be considered.

*For who?*

Any LaTeX user (not only graph enthusiasts) interested in creating nice

figures for their papers, posters, presentations...

The second session will present some advanced techniques to draw more

complex figures. Experience with TikZ, or attendance of the first session,

is expected.

TikZ (acronym for "TikZ ist kein Zeichenprogramm")is a tool to create

graphic elements in LaTeX. Not only graphs, but all kind of figures you

might think of.

*When/Where?*

Session 2: Tuesday November 28th, 11am to 1pm, in room 109.

There might be a zoom link to attend remotely, if interest in such an

arrangement is shown. Recording of the sessions will also be considered.

*For who?*

Any LaTeX user (not only graph enthusiasts) interested in creating nice

figures for their papers, posters, presentations...

The second session will present some advanced techniques to draw more

complex figures. Experience with TikZ, or attendance of the first session,

is expected.

Autocatalysis refers to the situation that a chemical

species catalyzes its own formation. A chemical reaction is

autocatalytic whenever one of its educts or reactants catalyzes its

own formation. Autocatalysis combines two features of the essence of

living systems, the ability to survive on an ambient food source and

the fact that each biochemical reaction in the system requires only

reactants and (most often) a catalyst that are provided by other

reactions in the system or are present in the food set. A chemical

reaction network, abbreviated to CRN, comprises a set of chemical

species and a set of chemical reactions. A CRN is represented as a

stoichiometric matrix S in which columns correspond to reactions and

rows correspond to chemical species. CRN can also be naturally

represented as a directed hypergraph H = (V, E) where V is the set of

chemical species and E is the set of chemical reactions.

Unfortunately, it is not easy to characterize the substructures that

define an autocatalytic process in a CRN. We will explore, and analyze

the mutual relations of five concepts regarding autocatalysis, which

are: autocatalytic cycles, Milo flows, autocatalytic cores, Nghe

flows, and strongly connected König digraphs. We will end with some

open questions about the topic and ideas for future research

species catalyzes its own formation. A chemical reaction is

autocatalytic whenever one of its educts or reactants catalyzes its

own formation. Autocatalysis combines two features of the essence of

living systems, the ability to survive on an ambient food source and

the fact that each biochemical reaction in the system requires only

reactants and (most often) a catalyst that are provided by other

reactions in the system or are present in the food set. A chemical

reaction network, abbreviated to CRN, comprises a set of chemical

species and a set of chemical reactions. A CRN is represented as a

stoichiometric matrix S in which columns correspond to reactions and

rows correspond to chemical species. CRN can also be naturally

represented as a directed hypergraph H = (V, E) where V is the set of

chemical species and E is the set of chemical reactions.

Unfortunately, it is not easy to characterize the substructures that

define an autocatalytic process in a CRN. We will explore, and analyze

the mutual relations of five concepts regarding autocatalysis, which

are: autocatalytic cycles, Milo flows, autocatalytic cores, Nghe

flows, and strongly connected König digraphs. We will end with some

open questions about the topic and ideas for future research