<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="en">
	<id>https://en.formulasearchengine.com/w/index.php?action=history&amp;feed=atom&amp;title=Matroid_partitioning</id>
	<title>Matroid partitioning - Revision history</title>
	<link rel="self" type="application/atom+xml" href="https://en.formulasearchengine.com/w/index.php?action=history&amp;feed=atom&amp;title=Matroid_partitioning"/>
	<link rel="alternate" type="text/html" href="https://en.formulasearchengine.com/w/index.php?title=Matroid_partitioning&amp;action=history"/>
	<updated>2026-07-20T02:58:15Z</updated>
	<subtitle>Revision history for this page on the wiki</subtitle>
	<generator>MediaWiki 1.47.0-wmf.7</generator>
	<entry>
		<id>https://en.formulasearchengine.com/w/index.php?title=Matroid_partitioning&amp;diff=28108&amp;oldid=prev</id>
		<title>en&gt;David Eppstein: authorlink Ed Scheinerman</title>
		<link rel="alternate" type="text/html" href="https://en.formulasearchengine.com/w/index.php?title=Matroid_partitioning&amp;diff=28108&amp;oldid=prev"/>
		<updated>2013-07-13T04:18:43Z</updated>

		<summary type="html">&lt;p&gt;authorlink &lt;a href=&quot;/w/index.php?title=Ed_Scheinerman&amp;amp;action=edit&amp;amp;redlink=1&quot; class=&quot;new&quot; title=&quot;Ed Scheinerman (page does not exist)&quot;&gt;Ed Scheinerman&lt;/a&gt;&lt;/p&gt;
&lt;p&gt;&lt;b&gt;New page&lt;/b&gt;&lt;/p&gt;&lt;div&gt;&amp;#039;&amp;#039;&amp;#039;Chemical reaction network theory&amp;#039;&amp;#039;&amp;#039; is an area of [[applied mathematics]] that attempts to [[mathematical model|model]] the behaviour of real world [[chemistry|chemical]] systems. Since its foundation in the 1960s, it has attracted a growing research community, mainly due to its applications in [[biochemistry]] and [[theoretical chemistry]]. It has also attracted interest from [[pure mathematics|pure mathematicians]] due to the interesting problems that arise from the mathematical structures involved.&lt;br /&gt;
&lt;br /&gt;
== History ==&lt;br /&gt;
&lt;br /&gt;
Dynamical properties of reaction networks were studied in chemistry and physics after invention of the [[law of mass action]]. The essential steps in this study were introduction of [[detailed balance]] for the complex chemical reactions by [[Rudolf Wegscheider]] (1901),&amp;lt;ref&amp;gt;Wegscheider, R. (1901) [http://www.springerlink.com/content/q12x76713v015316/ Über simultane Gleichgewichte und die Beziehungen zwischen Thermodynamik und Reactionskinetik homogener Systeme], Monatshefte für Chemie / Chemical Monthly 32(8), 849--906.&amp;lt;/ref&amp;gt; development of the quantitative theory of chemical chain reactions by [[Nikolay Semyonov]] (1934),&amp;lt;ref&amp;gt;Semyonov&amp;#039;s  Nobel Lecture [http://nobelprize.org/nobel_prizes/chemistry/laureates/1956/semenov-lecture.html Some Problems Relating to Chain Reactions and to the Theory of Combustion]&amp;lt;/ref&amp;gt; development of kinetics of catalytic reactions by  [[Cyril Norman Hinshelwood]],&amp;lt;ref&amp;gt;Hinshelwood&amp;#039;s  Nobel Lecture [http://nobelprize.org/nobel_prizes/chemistry/laureates/1956/hinshelwood-lecture.html Chemical Kinetics in the Past Few Decades]&amp;lt;/ref&amp;gt; and many other results.&lt;br /&gt;
&lt;br /&gt;
The mathematical discipline &amp;quot;chemical reaction network theory&amp;quot; was originated by [[Rutherford Aris]], a famous expert in chemical engineering, with support of [[Clifford Truesdell]], the founder and editor-in-chief of the journal &amp;#039;&amp;#039;[[Archive for Rational Mechanics and Analysis]]&amp;#039;&amp;#039;. The paper of R. Aris in this journal  &amp;lt;ref&amp;gt;R. Aris, Prolegomena to the rational analysis of systems of chemical reactions, Archive for Rational Mechanics and Analysis, 1965, Volume 19, Issue 2, pp 81-99.&amp;lt;/ref&amp;gt; was communicated to the journal by C. Truesdell. It opened the series of papers of other authors (which were communicated already by R Aris).  The well known papers of this series are the works of Frederick J. Krambeck,&amp;lt;ref&amp;gt;F.J. Krambeck, The mathematical structure of chemical kinetics in homogeneous single-phase systems, Archive for Rational Mechanics and Analysis, 1970, Volume 38, Issue 5, pp 317-347,&amp;lt;/ref&amp;gt; Roy Jackson, Friedrich Josef Maria Horn,&amp;lt;ref&amp;gt;F. J. M. Horn and R. Jackson, &amp;quot;General Mass Action Kinetics&amp;quot;, &amp;#039;&amp;#039;Archive Rational Mech.&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;47&amp;#039;&amp;#039;&amp;#039;:81, 1972.&amp;lt;/ref&amp;gt; [[Martin Feinberg]]&amp;lt;ref&amp;gt;M. Feinberg, &amp;quot;Complex balancing in general kinetic systems&amp;quot;, &amp;#039;&amp;#039;[[Archive for Rational Mechanics and Analysis|Arch. Rational Mech. Anal.]]&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;49&amp;#039;&amp;#039;&amp;#039;:187–194, 1972.&amp;lt;/ref&amp;gt; and others, published in the 1970s. In his second &amp;quot;prolegomena&amp;quot; paper,&amp;lt;ref&amp;gt;R. Aris, Prolegomena to the rational analysis of systems of chemical reactions II. Some addenda, Archive for Rational Mechanics and Analysis, 1968, Volume 27, Issue 5, pp 356-364&amp;lt;/ref&amp;gt; R. Aris mentioned the work of N.Z. Shapiro, L.S. Shapley (1965),&amp;lt;ref&amp;gt;N.Z. Shapiro, L.S. Shapley, Mass action law and the Gibbs free energy function, SIAM J. Appl. Math. 16 (1965) 353–375.&amp;lt;/ref&amp;gt; where an important part of his scientific program was realized.&lt;br /&gt;
&lt;br /&gt;
Since then, the chemical reaction network theory has been further developed by a large number of researchers internationally.&amp;lt;ref&amp;gt;P. Érdi and J. Tóth, &amp;quot;Mathematical models of chemical reactions&amp;quot;, &amp;#039;&amp;#039;[[Manchester University Press]]&amp;#039;&amp;#039;, 1989.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;H. Kunze and D. Siegel, &amp;quot;Monotonicity properties of chemical reactions with a single initial bimolecular step&amp;quot;, &amp;#039;&amp;#039;J. Math. Chem.&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;31&amp;#039;&amp;#039;&amp;#039;(4):339–344, 2002.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;M. Mincheva and D. Siegel, &amp;quot;Nonnegativity and positiveness of solutions to mass action reaction–diffusion systems&amp;quot;, &amp;#039;&amp;#039;J. Math. Chem.&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;42&amp;#039;&amp;#039;&amp;#039;:1135–1145, 2007.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;P. De Leenheer, D. Angeli and E. D. Sontag, [http://www.mit.edu/~esontag/FTP_DIR/leenheer-angeli-sontag-JMathChem07.pdf &amp;quot;Monotone chemical reaction networks&amp;quot;], &amp;#039;&amp;#039;J. Math. Chem.&amp;#039;, 41(3):295–314, 2007.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;M. Banaji, P. Donnell and S. Baigent, &amp;quot;[[P-matrix|&amp;#039;&amp;#039;P&amp;#039;&amp;#039; matrix]] properties, injectivity and stability in chemical reaction systems&amp;quot;, &amp;#039;&amp;#039;[[Society for Industrial and Applied Mathematics|SIAM]] J. Appl. Math.&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;67&amp;#039;&amp;#039;&amp;#039;(6):1523–1547, 2007.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;G. Craciun and C. Pantea, &amp;quot;Identifiability of chemical reaction networks&amp;quot;, &amp;#039;&amp;#039;J. Math. Chem.&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;44&amp;#039;&amp;#039;&amp;#039;:1, 2008.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;M. Domijan and M. Kirkilionis, &amp;quot;Bistability and oscillations in chemical reaction networks&amp;quot;, &amp;#039;&amp;#039;[[Journal of Mathematical Biology|J. Math. Biol.]]&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;59&amp;#039;&amp;#039;&amp;#039;(4):467–501, 2009.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;A. N. Gorban and G. S. [[Grigoriy Yablonsky|Yablonsky]], [http://www.math.le.ac.uk/people/ag153/homepage/GorbanYablonskiiCES2011.pdf &amp;quot;Extended detailed balance for systems with irreversible reactions&amp;quot;], &amp;#039;&amp;#039;Chemical Engineering Science&amp;#039;&amp;#039;, &amp;#039;&amp;#039;&amp;#039;66&amp;#039;&amp;#039;&amp;#039;:5388–5399, 2011.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;E. Feliu, M. Knudsen and C. Wiuf., &amp;quot;Signaling cascades: Consequences of varying substrate and phosphatase levels&amp;quot;, &amp;#039;&amp;#039;[[Advances in Experimental Medicine and Biology|Adv. Exp. Med. Biol.]]&amp;#039;&amp;#039; (Adv Syst Biol), &amp;#039;&amp;#039;&amp;#039;736&amp;#039;&amp;#039;&amp;#039;:81–94, 2012.&amp;lt;/ref&amp;gt;&lt;br /&gt;
&lt;br /&gt;
== Overview ==&lt;br /&gt;
&lt;br /&gt;
A chemical reaction network (often abbreviated to &amp;#039;&amp;#039;&amp;#039;CRN&amp;#039;&amp;#039;&amp;#039;) comprises a [[set (mathematics)|set]] of [[reagent|reactants]], a set of products (often [[intersection (set theory)|intersecting]] the set of reactants), and a set of [[chemical reaction|reactions]]. For example, the pair of [[combustion]] reactions&lt;br /&gt;
&lt;br /&gt;
: &amp;lt;math&amp;gt;&lt;br /&gt;
\begin{array}{rcl}&lt;br /&gt;
2 H_2 + O_2 &amp;amp; \rightarrow &amp;amp; 2 H_2 O \\&lt;br /&gt;
C + O_2 &amp;amp; \rightarrow &amp;amp; C O_2&lt;br /&gt;
\end{array}&lt;br /&gt;
&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
form a reaction network. The reactions are represented by the arrows. The reactants appear to the left of the arrows, in this example they are &amp;lt;math&amp;gt;H_2&amp;lt;/math&amp;gt; ([[hydrogen]]), &amp;lt;math&amp;gt;O_2&amp;lt;/math&amp;gt; ([[oxygen]]) and &amp;lt;math&amp;gt;C&amp;lt;/math&amp;gt; ([[carbon]]). The products appear to the right of the arrows, here they are &amp;lt;math&amp;gt;H_2 O&amp;lt;/math&amp;gt; ([[water]]) and &amp;lt;math&amp;gt;C O_2&amp;lt;/math&amp;gt; ([[carbon dioxide]]). In this example, since the reactions are [[reversible reaction|irreversible]] and neither of the products are used up in the reactions, the set of reactants and the set of products are [[disjoint sets|disjoint]].&lt;br /&gt;
&lt;br /&gt;
Mathematical modelling of chemical reaction networks usually focuses on what happens to the concentrations of the various chemicals involved as time passes. Following the example above, let &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; represent the [[concentration]] of &amp;lt;math&amp;gt;H_2&amp;lt;/math&amp;gt; in the surrounding air, &amp;lt;math&amp;gt;b&amp;lt;/math&amp;gt; represent the concentration of &amp;lt;math&amp;gt;O_2&amp;lt;/math&amp;gt;, &amp;lt;math&amp;gt;c&amp;lt;/math&amp;gt; represent the concentration of &amp;lt;math&amp;gt;H_2 O&amp;lt;/math&amp;gt;, and so on. Since all of these concentrations will not in general remain constant, they can be written as a function of time e.g. &amp;lt;math&amp;gt;a(t), b(t)&amp;lt;/math&amp;gt;, etc.&lt;br /&gt;
&lt;br /&gt;
These variables can then be combined into a vector&lt;br /&gt;
&lt;br /&gt;
: &amp;lt;math&amp;gt;x(t) = \left(\begin{array}{c} a(t) \\ b(t) \\ c(t) \\ \vdots \end{array}\right)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
and their evolution with time can be written&lt;br /&gt;
&lt;br /&gt;
: &amp;lt;math&amp;gt;\dot{x} \equiv \frac{dx}{dt} = \left(\begin{array}{c} \frac{da}{dt} \\[6pt] \frac{db}{dt} \\[6pt] \frac{dc}{dt} \\[6pt] \vdots \end{array}\right).&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
This is an example of a [[continuous function|continuous]] [[autonomous system (mathematics)|autonomous]] [[dynamical system]], commonly written in the form &amp;lt;math&amp;gt;\dot{x} = f(x)&amp;lt;/math&amp;gt;. The number of molecules of each reactant used up each a reaction occurs is constant, as is the number of molecules produced of each product. These numbers are referred to as the [[stoichiometry]] of the reaction, and the difference between the two (i.e. the overall number of molecules used up or produced) is the &amp;#039;&amp;#039;&amp;#039;net stoichiometry&amp;#039;&amp;#039;&amp;#039;. This means that the equation representing the chemical reaction network can be rewritten as&lt;br /&gt;
&lt;br /&gt;
: &amp;lt;math&amp;gt;\dot{x} = \Gamma V(x)&amp;lt;/math&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Here, each column of the [[constant (mathematics)|constant]] [[matrix (mathematics)|matrix]] &amp;lt;math&amp;gt;\Gamma&amp;lt;/math&amp;gt; represents the net stoichiometry of a reaction, and so &amp;lt;math&amp;gt;\Gamma&amp;lt;/math&amp;gt; is called the &amp;#039;&amp;#039;&amp;#039;stoichiometry matrix&amp;#039;&amp;#039;&amp;#039;. &amp;lt;math&amp;gt;V(x)&amp;lt;/math&amp;gt; is a [[vector-valued function]] where each output value represents a reaction rate, referred to as the [[chemical kinetics|kinetics]].&lt;br /&gt;
&lt;br /&gt;
== Common assumptions ==&lt;br /&gt;
&lt;br /&gt;
For physical reasons, it is usually assumed that reactant concentrations cannot be negative, and that each reaction only takes place if all its reactants are present, i.e. all have non-zero concentration. For mathematical reasons, it is usually assumed that &amp;lt;math&amp;gt;V(x)&amp;lt;/math&amp;gt; is [[smooth function|continuously differentiable]].&lt;br /&gt;
&lt;br /&gt;
It is also commonly assumed that no reaction features the same chemical as both a reactant and a product (i.e. no [[catalysis]] or [[autocatalysis]]), and that increasing the concentration of a reactant increases the rate of any reactions that use it up. This second assumption is compatible with all physically reasonable kinetics, including [[law of mass action|mass action]], [[Michaelis–Menten kinetics|Michaelis–Menten]] and [[Hill equation (biochemistry)|Hill]] kinetics. Sometimes further assumptions are made about reaction rates, e.g. that all reactions obey mass action kinetics.&lt;br /&gt;
&lt;br /&gt;
Other assumptions include [[mass balance]], constant [[temperature]], constant [[pressure]], [[homogeneous (chemistry)|spatially uniform]] concentration of reactants, and so on.&lt;br /&gt;
&lt;br /&gt;
== Types of results ==&lt;br /&gt;
&lt;br /&gt;
As chemical reaction network theory is a diverse and well-established area of research, there is a significant variety of results. Some key areas are outlined below.&lt;br /&gt;
&lt;br /&gt;
=== Number of  steady states ===&lt;br /&gt;
&lt;br /&gt;
These results relate to whether a chemical reaction network can produce significantly different behaviour depending on the initial concentrations of its constituent reactants. This has applications in e.g. modelling [[biology|biological]] switches &amp;amp;mdash; a high concentration of a key chemical at steady state could represent a biological process being &amp;quot;switched on&amp;quot; whereas a low concentration would represent being &amp;quot;switched off&amp;quot;.&lt;br /&gt;
&lt;br /&gt;
For example, the catalytic [[trigger]] is a simplest catalytic reaction without [[autocatalysis]] that allows multiplicity of steady states(1976):&amp;lt;ref&amp;gt;M.G. Slin&amp;#039;ko, V.I. Bykov, G.S. [[Grigoriy Yablonsky|Yablonskii]], T.A. Akramov, &amp;quot;Multiplicity of the Steady State in Heterogeneous Catalytic Reactions&amp;quot;, &amp;#039;&amp;#039;Dokl. Akad. Nauk SSSR&amp;#039;&amp;#039; &amp;#039;&amp;#039;&amp;#039;226&amp;#039;&amp;#039;&amp;#039; (4) (1976), 876.&amp;lt;/ref&amp;gt;&amp;lt;ref&amp;gt;V.I. Bykov, V.I. Elokhin, G.S. [[Grigoriy Yablonsky|Yablonskii]], [http://dx.doi.org/10.1007/BF02061998  &amp;quot;The simplest catalytic mechanism permitting several steady states of the surface&amp;quot;], &amp;#039;&amp;#039;React. Kinet. Catal. Lett.&amp;#039;&amp;#039; &amp;#039;&amp;#039;&amp;#039;4&amp;#039;&amp;#039;&amp;#039; (2) (1976), 191–198.&amp;lt;/ref&amp;gt;&lt;br /&gt;
# &amp;lt;math&amp;gt;A_2+2 Z \rightleftharpoons 2 AZ&amp;lt;/math&amp;gt;&lt;br /&gt;
# &amp;lt;math&amp;gt;B+Z \rightleftharpoons BZ &amp;lt;/math&amp;gt;&lt;br /&gt;
# &amp;lt;math&amp;gt;AZ+BZ \to AB+2 Z &amp;lt;/math&amp;gt;&lt;br /&gt;
This is the classical [[Langmuir–Hinshelwood kinetics|adsorption mechanism]] of catalytic oxidation. &lt;br /&gt;
&lt;br /&gt;
Here, &amp;lt;math&amp;gt;A_2, B&amp;lt;/math&amp;gt; and AB  are gases (for example, &amp;lt;math&amp;gt;O_2&amp;lt;/math&amp;gt;, &amp;#039;&amp;#039;CO&amp;#039;&amp;#039; and &amp;lt;math&amp;gt;CO_2&amp;lt;/math&amp;gt;), &amp;#039;&amp;#039;Z&amp;#039;&amp;#039; iz the &amp;quot;adsorption place&amp;quot; on the surface of the solid catalyst (for example, Pt), &amp;#039;&amp;#039;AZ&amp;#039;&amp;#039; and &amp;#039;&amp;#039;BZ&amp;#039;&amp;#039; are the intermediates on the surface (adatoms, adsorbed molecules or radicals).&lt;br /&gt;
This system may have two stable steady states of the surface for the same concentrations of the gaseous components.&lt;br /&gt;
&lt;br /&gt;
===  Stability of steady states ===&lt;br /&gt;
&lt;br /&gt;
Stability determines whether a given steady state solution is likely to be observed in reality. Since real systems (unlike [[deterministic system|deterministic]] models) tend to be subject to random background noise, an unstable steady state solution is unlikely be observed in practice. Instead of them, stable oscillations or other types of [[attractor]]s may appear.&lt;br /&gt;
&lt;br /&gt;
=== Persistence ===&lt;br /&gt;
&lt;br /&gt;
Persistence has its roots in [[population dynamics]]. A non-persistent [[species]] in population dynamics can go extinct for some (or all) initial conditions. Similar questions are of interests to chemists and biochemists, i.e. if a given reactant was present to start with, can it ever be completely used up?&lt;br /&gt;
&lt;br /&gt;
=== Existence of stable  periodic solutions ===&lt;br /&gt;
&lt;br /&gt;
Results regarding stable periodic solutions attempt to rule out &amp;quot;unusual&amp;quot; behaviour. If a given chemical reaction network admits a stable periodic solution, then some initial conditions will converge to an infinite cycle of oscillating reactant concentrations. For some parameter values it may even exhibit [[quasiperiodic motion|quasiperiodic]] or [[chaos theory#Chaotic dynamics|chaotic]] behaviour. While stable periodic solutions are unusual in real-world chemical reaction networks, well known examples exist, such as the [[Belousov–Zhabotinsky reaction]]s. The simplest catalytic oscillator (nonlinear self-oscillations without authocatalisys)&lt;br /&gt;
can be produced from the catalytic trigger by addind a &amp;quot;buffer&amp;quot; step.&amp;lt;ref&amp;gt;V.I. Bykov, G.S. Yablonskii, V.F. Kim, &amp;quot;On the simple model of kinetic self-oscillations in catalytic reaction of CO oxidation&amp;quot;, &amp;#039;&amp;#039;Doklady AN USSR&amp;#039;&amp;#039; (Chemistry)  &amp;#039;&amp;#039;&amp;#039;242&amp;#039;&amp;#039;&amp;#039; (3) (1978), 637–639.&amp;lt;/ref&amp;gt; &lt;br /&gt;
:4. &amp;lt;math&amp;gt;B + Z \rightleftharpoons (BZ)&amp;lt;/math&amp;gt;&lt;br /&gt;
where (BZ) is an intermediate that does not participate in the main reaction.&lt;br /&gt;
&lt;br /&gt;
== References ==&lt;br /&gt;
{{Reflist}}&lt;br /&gt;
&lt;br /&gt;
== External links ==&lt;br /&gt;
* [http://reaction-networks.net/ Specialist wiki on the mathematics of reaction networks]&lt;br /&gt;
&lt;br /&gt;
[[Category:Mathematical chemistry]]&lt;/div&gt;</summary>
		<author><name>en&gt;David Eppstein</name></author>
	</entry>
</feed>