Author: logancollins

Algebraic Graph Mappings


No Comments

an exploration by Logan Thrasher Collins.

     Algebraic manipulation of mathematical objects provides a rich array of tools for deriving insights about said objects. Graph theory concerns networks of vertices and edges and finds applications in diverse areas such as computer science, quantitative sociology, electrical engineering, and neurobiology. The use of algebraic methods in graph theory has received surprisingly little attention. While mappings are sometimes studied in graph theory, such transformations are often considered in the abstract, without a method for describing the content of any given mapping. Here, I define an algebraic framework for specifying transformations between graphs. This framework might be extended to further capitalize upon the tools of analysis and abstract algebra, leading to potential new paths of investigation.

     Let G and H be simple, labeled graphs. The transformation ϕ(G):𝔾→𝔾 is a mapping which transforms G into H. (Here, 𝔾 represents the set of all simple, labeled graphs). To specify the precise content of this process, I define a general formula for graph mappings. Note that any term may take on either a positive or a negative value. Positive terms indicate the creation of a new vertex or edge within H, while negative terms indicate the removal of an existing vertex or edge from G. In this formula, v∈{V(G),V(H)} and e∈{E(G),E(H)}.

Eq.1

In order for the equation above to be defined, any edge must connect a pair of vertices in H. That is, no edge e can be created without also creating a pair of corresponding vertices that are connected by e. Below, I will provide a specific example of a mapping between graphs to show this formula’s mechanics.

Fig.1

Eq.2

Figure 1 Illustrative example of an algebraic graph mapping ϕ(G)=H and its corresponding labeled graphs.

     The algebraic manipulations enabled by this approach remain somewhat limited since every new vertex and edge and every deleted vertex and edge must be explicitly specified. However, as with manipulations of other mathematical objects, taking advantage of patterns can allow abstraction to larger and more complicated systems. For example, sequences and series are often utilized for such purposes in the field of analysis. To move towards analogous investigations on graphs, I will describe a framework for graph labeling which eases the manipulation of complex networks using my algebraic technique.

     Let 𝒵 represent a set of “potential vertices” equipped with labels corresponding to the integers. It should be noted that this setup allows for infinite isomorphic graphs with different labelings to be constructed. Each point in 𝒵 is labeled as x∈ℤ. The points x∈𝒵 define the set of possible vertices v∈H which might be created when ϕ operates upon G. In this way, symbolic extrapolations to large networks can be made.

Fig.2

Figure 2 (A) The layout of “potential vertices” described by 𝒵 with bounds x∈[-5,5]. (B) An example of a labeled graph defined on 𝒵 with the same bounds.

     Using the labeling scheme 𝒵, functions on ℤ can facilitate the construction of complex networks according to defined rules. Let the variable x take on integer values such that x∈ℤ. To map between graphs on 𝒵, use functions which satisfy F𝒵:ℤ→ℤ to specify the vertices and edges of H. Note that such functions will create infinite graphs unless bounds are defined on x. To facilitate the construction of networks, this scheme will follow three useful rules. (1) If repeated vertices and edges are created, the copies of the repeated vertices and edges will be ignored. (2) If a nonexistent vertex or edge is subtracted, giving a negative vertex or edge, the negative object will be ignored. (3) Any edges or vertices which do not belong to G or H will be ignored.

Fig.3

Eq.3

Figure 3 (A) The graph G consists of a single vertex v(0). (B) The function F𝒵 maps G to a graph H using the labeling scheme 𝒵. Edges are created linking v(3) and the rest of the vertices, all negative-labeled vertices edges incident with v(3) are removed, and then all edges linking v(0) and any existing negative-labeled vertices are created. (C) Isomorphism on H to provide a cleaner visualization of the result.

     Here, I have developed an algebraic toolset for describing mappings between graphs. This toolset allows the creation of new vertices and edges as well as the removal of existing vertices and edges. To allow rapid generation of networks with many vertices and edges, I have provided a method for consistently labeling graphs that works synergistically with the core algebraic technique. This method may provide the basis for more generalized explorations which utilize such mathematical resources as groups and group-like structures. Because the method lends itself to creating infinite graphs, it may also stimulate investigation from the perspective of analysis using concepts like limits and convergence. The relationships between my algebraic graph mappings and matrix-based representations of graphs may also provide new territory. Applied computational fields may benefit from the mapping technique since it provides an alternative set of resources for investigating and modeling networks. Algebraic graph mappings may provide a nucleation point for a myriad of possible research directions.

 

Disclaimer: because I come from a biological background and have very limited formal mathematical training, this text may appear quite rough to more mathematically-experienced individuals. However, I feel that the technique has potential to develop further and be applied to problems in science and engineering. I would welcome any constructive critiques so long as they are presented in a respectful manner.

Notes on Abstract Algebra


1 Comment

Binary Operations

  • Definition: a binary operation is an operation performed between any pair of elements from a set S that maps into the same set S.

Eq.1

  • The mapping must be defined for every pair of elements in S and uniquely assign any pair of elements in S to another element in S. (This does not exclude the elements operated upon).
  • Addition on the set of real numbers is an example of a binary operation since adding any two real numbers will give another real number. Note that the “upside-down A” symbol denotes “for all.”

Eq.2

  • Addition on the set of complex numbers as well as addition on the set of integers are binary operations.
  • Matrix addition on the set of all matrices with real entries is not a binary operation since matrix addition is undefined for matrices with different numbers of rows or columns.
  • However, matrix addition on the set of all 2×2 matrices with real entries is a binary operation since adding any given pair of 2×2 matrices will generate another 2×2 matrix. The same holds for the set of all 2×2 matrices with complex entries.
  • Subtraction on the set of natural numbers (1,2,3,4…) is not a binary operation because some results will fall outside of the natural numbers (for instance, negative values).

Eq.4

  • Binary operations can take more exotic forms. Any operation that fits the definition of a binary operation is a binary operation.

Groups

  • A group G is an algebraic structure consisting of a finite or infinite set and a binary operation which acts between any pair of the elements in that set. Groups have the following properties.
  • Closure: given that a and b are in G, the group operation generates a result c that is also in G. (Note that all binary operations are defined to have closure regardless of whether they belong to a group).

Eq.5

  • Associativity: the group operation is associative.

Eq.6

  • Identity: there is an identity element e such that the relations below hold.

Eq.7

  • Inverse: there must be an inverse of each element.

Eq.8

  • As such, groups are sets equipped with a generalized addition operation.
  • To prove that G is a group, simply demonstrate in general terms (by manipulating symbols rather than specific values) that the properties above hold for all elements of G. Note that the identity element e may need to be algebraically solved for as a separate exercise from the proof itself.
  • Abelian groups are groups for which the group operation is commutative on the set G.

Eq.9

  • Some group-like structures that commonly occur in abstract algebra are given along with their properties in the table below.

Table1

Rings

  • Many number systems (i.e. the set of real numbers, the set of polynomials, etc.) share the binary operations of addition and multiplication.
  • Addition is a binary operation with the properties of closure (by definition of a binary operation), associativity, additive identity a+0=0+a=a, additive inverse a+-a=-a+a=0, and commutativity. Addition forms an Abelian group on a set where it is defined.
  • Multiplication is a binary operation with the properties of closure (by definition of a binary operation), associativity, multiplicative identity a•1=a, multiplicative inverse a•(1/a)=a, and distributivity of multiplication over addition a(b+c)=a•b+a•c and (a+b)•c=a•c+b•c. Multiplication is commutative on some sets (i.e. the reals), but not others (i.e. real 2×2 matrices). Note that when the set contains 0, multiplication cannot form a group because 0 generally has no multiplicative inverse.
  • A ring is a set R equipped with the binary operations of addition and multiplication. Rings have the following properties. Note that the “backwards E” symbol denotes “there exists.” The elements denoted by 1 and 0 are generalized and do not always refer to numbers. 

Eq.10

  • Some examples of rings include the set of real numbers equipped with addition and multiplication, the set of complex numbers equipped with addition and multiplication, the set of rational numbers equipped with addition and multiplication, the set of polynomials R[x] equipped with addition and multiplication, and the set of square matrices equipped with addition and multiplication. Note that, since rings do not require a multiplicative inverse or commutativity with respect to multiplication, they can be defined on a wider variety of sets than would be possible otherwise. This standard type of ring is also known as a noncommutative ring.
  • Commutative rings are rings which have the additional property given below.

Eq.11

Fields

  • Consider a ring R containing an element a ≠ 0 and an element b ≠ 0 The element a is called a zero divisor if either of the formulas below holds.

Eq.12

  • Commutative rings without any zero divisors are called integral domains. Some examples of integral domains include ℝ, ℂ, ℤ, and ℚ.
  • Multiplicative cancellation holds for integral domains. Note that R denotes a ring and not the real numbers.

Eq.13

  • Consider a ring R and a nonzero element a ∈ If there also exists an element b ∈ R such that ab = ba = 1, then the elements a and b are multiplicative inverses of each other and are called invertible. Invertible elements of R are also called units of the ring R.
  • If all the nonzero elements of an integral domain are invertible, then the integral domain is called a field. As such, fields are sets equipped with a division operation as well as addition and multiplication operations.

 

Reference: A Gentle Introduction to Abstract Algebra

Notes on the Drude Model


3 Comments

PDF Version: Notes on the Drude Model

Assumptions of the Drude Model

  • The Drude model provides a classical mechanics approach to describing conductivity in metals. This model makes several key assumptions (some of which are better approximations than others).
  • Electrons in a metal behave much like particles in an ideal gas (no Coulombic interaction and no collisions between particles). This is called the independent electron approximation.
  • Positive charges are located on immobile ions. The electrons do not experience coulombic interaction with the ions, but they do collide with the ions and can change direction and velocity.
  • Electrons reach thermal equilibrium by collisions with the ions. Their mean kinetic energy within the lattice at equilibrium is given below. The mass of an electron is represented as me, the average velocity at a given temperature is vT, the Boltzmann constant is kB, and the temperature in Kelvin is T. At room temperature, vT is about 105 m/s.

Eq.1

  • The average distance of an electron’s free movement between collisions is called the mean free path λ. For metals, the mean free path is typically estimated as 1 nm based on known ionic packing parameters. To calculate the mean time τ between collisions (called the relaxation time), the equation τ=λ/vT is used.

Applying the Drude Model

  • To apply the Drude model, the density of the “gas” formed by the free electrons must be known. This parameter is called the conduction electron density n (the number of free electrons per volume).
  • The conduction electron density is computed by assuming that each atom contributes ZV conducting electrons. ZV represents the number of outer shell electrons for metal atoms in the ionic lattice. For instance, alkaline Earth metals have a ZV value of 2. Given the density ρm in kg/m3 and the atomic mass M in kg per atom, the conduction electron density is ZVρm/M.
  • Given the average time for a collision-free drift τ, the average drift velocity of an electron in a metal can be computed using the equation below. Here, e represents the charge of an electron in Coulombs and is electromotive force in volts (a vector quantity).

Eq.2

  • The number of electrons passing through a given area per unit time Je and the amount of charge passing through a given area per unit time Jc are given below. Here, n is the number of electrons.

Eq.3

Eq.4

  • The current density j is computed by the equation below.

Eq.5

  • This can be used to derive the following expression, which is equivalent to Ohm’s law V=IR.

Eq.6

  • As such, the conductivity σ and the resistivity ρ are given by the equations below.

Eq.7

  • The mobility μ of an electron in a lattice is given below. The mobility can be interpreted as the ratio of the drift velocity to the applied electric field.

Eq.8

  • Using mobility, conductivity and resistivity can be computed by alternative formulas.

Eq.9

Fig.1

The Drude Model and the Hall Effect

  • The Drude model explains the Hall effect, a phenomenon in which an electric field ℇH arises perpendicular to both the current density jx (which points in the direction of electron movement) and the magnetic field Bz.
  • The Hall effect occurs when a current flows through a conductor while under a magnetic field. As a result of the magnetic field, positive charges accumulate on one side of the conductor (and negative charges on the other side).

Fig.2

  • For electrons to pass through the given region, the field ℇH must cancel the Lorenz force which acts in the opposite direction (the Lorenz force is the sum FL=qE+qv×B of the magnetic force and electric force on a moving charged particle). The magnitude of the Hall field is given below. RH is called the Hall coefficient and can be measured experimentally.

Eq.10

  • As the value of RH approaches one, the field ℇH more exactly cancels the Lorenz force. The value of RH varies between types of metals, so some metals are better conductors than others.

The Drude Model and Optical Reflectivity of Metals

  • Light can be described as an electromagnetic wave in the form of a transverse plane.
  • The electric field for light in the propagating in the z direction is given by the equation below. ℇ0 is the amplitude in the xy plane, λ0 is the wavelength in a vacuum, n is the index of refraction, and κ is a parameter that accounts for attenuation of the light’s intensity inside of a given material.

Eq.11

  • Alternatively, the equation for the electric field of light propagating in the z direction can be expressed using the dielectric constant of the given material.

Eq.12

  • An electron within the electric field from an electromagnetic wave moves according to the following equation of motion (derived from F=ma). Note that the charge –e and the exponential are distinct.

Eq.13

  • Solving the differential equation above gives the following result.

Eq.14

  • As a result of the electric field from the electromagnetic wave, the electron undergoes positional displacement in a periodic manner. This leads to a changing dipole moment given by –ex(t).
  • Dielectric functions describe the permittivity of given media over time. Permittivity is the amount of charge needed to generate a single unit of electric flux within the medium. Using the above results and some other known formulas, the dielectric function for a material can be derived.

Eq.15

  • By setting a parameter ωP2 equal to ne2/meε0, the dielectric function can be rewritten as below. Note that ωP is called the plasma frequency.

Eq.16

  • For ω<ωP, the value of ε is real and negative, making the square root of ε purely imaginary. As such, the light does not transmit into the metal in this case. Since energy is conserved, the light is reflected instead.
  • For ω>ωP, the value of ε is real and positive. As such, the light does propagate into the metal in this case.
  • Metals reflect low-frequency light and are transparent for high-frequency light. The transition occurs at the plasma frequency ωP.
  • The plasma frequency can be measured experimentally or calculated using the conduction electron density n.

The Drude Model and the Wiedemann-Franz Law

  • Thermal conductivity is defined by the equation below where Q is the amount of heat transferred per time t, k is the thermal conductivity constant for a given material, A is the cross-sectional area, d is the thickness of the material, and ΔT is the difference in temperature across the material. Note that this definition only describes the simple 1-dimensional case, but analogous formulas can be used for more general situations.

Eq.17

  • The Wiedemann-Franz law states that, for any metal at a given temperature, the ratio of thermal conductivity κ to electrical conductivity σ is a constant L. Furthermore, L is proportional to temperature as temperature varies. L is called the Lorenz number.

Eq.18

  • The ideal gas-related equations from the Drude model can be used to generate an equivalent formula for LT. Despite some minor inconsistencies with experimental data, this theoretical calculation often gives strikingly accurate results.

Eq.19

Shortcomings of the Drude Model

  • The Drude model does not take into account collisions between electrons themselves. It also does not consider electrostatic interactions between the electrons and the lattice ions.
  • The de Broglie wavelengths of electrons with some thermal energy are on the nanometer scale. This means that electrons cannot be treated as classical particles (since they have substantial wave character) under the conditions of the Drude model.
  • As mentioned, the Drude model underestimates conductivity of metals at low temperatures. This is because the assumption of a constant mean free path (based on atomic spacing) is incorrect. The mean free path varies greatly with temperature, particularly in pure crystalline substances.
  • The Drude model cannot explain the conductivity of alloys. Even small impurities can drastically decrease the conductivity of metals in a way which is not predicted by the Drude model.
  • From a classical mechanics perspective, the electrons should contribute greatly to the heat capacity of metals. But this result does not agree with experimental data (and using quantum mechanical models instead resolves the issue).

 

Reference: Hofmann, P. (2015). Solid State Physics: An Introduction. Wiley.

 

 

 

Art: The Octopoid Occupation


No Comments

This piece started as a hand-drawn pencil sketch which I “doodled” during a class (yes, I also paid attention to the lecture). Afterwards, I took a picture of the sketch and cleaned it up using Paint.net, a program similar to Photoshop. I was quite pleased with the result!Octopus_city_sketch