Representation (mathematics)

In mathematics, a representation is a very general relationship that expresses similarities (or equivalences) between mathematical objects or structures.[1] Roughly speaking, a collection Y of mathematical objects may be said to represent another collection X of objects, provided that the properties and relationships existing among the representing objects yi conform, in some consistent way, to those existing among the corresponding represented objects xi. More specifically, given a set Π of properties and relations, a Π-representation of some structure X is a structure Y that is the image of X under a homomorphism that preserves Π. The label representation is sometimes also applied to the homomorphism itself (such as group homomorphism in group theory).[2][3]

Representation theory[edit]

Perhaps the most well-developed example of this general notion is the subfield of abstract algebra called representation theory, which studies the representing of elements of algebraic structures by linear transformations of vector spaces.[3]

Other examples[edit]

Although the term representation theory is well established in the algebraic sense discussed above, there are many other uses of the term representation throughout mathematics.

Graph theory[edit]

An active area of graph theory is the exploration of isomorphisms between graphs and other structures. A key class of such problems stems from the fact that, like adjacency in undirected graphs, intersection of sets (or, more precisely, non-disjointness) is a symmetric relation. This gives rise to the study of intersection graphs for innumerable families of sets.[4] One foundational result here, due to Paul Erdős and his colleagues, is that every n-vertex graph may be represented in terms of intersection among subsets of a set of size no more than n2/4.[5]

Representing a graph by such algebraic structures as its adjacency matrix and Laplacian matrix gives rise to the field of spectral graph theory.[6]

Order theory[edit]

Dual to the observation above that every graph is an intersection graph is the fact that every partially ordered set (a.k.a., poset) is isomorphic to a collection of sets ordered by the containment (or inclusion) relation ⊆. Some posets that arise as the containment orders for natural classes of objects include the Boolean lattices and the orders of dimension n.[7]

Many partial orders arise from (and thus can be represented by) collections of geometric objects. Among them are the n-ball orders. The 1-ball orders are the interval-containment orders, and the 2-ball orders are the so-called circle orders—the posets representable in terms of containment among disks in the plane. A particularly nice result in this field is the characterization of the planar graphs, as those graphs whose vertex-edge incidence relations are circle orders.[8]

There are also geometric representations that are not based on containment. Indeed, one of the best studied classes among these are the interval orders,[9] which represent the partial order in terms of what might be called disjoint precedence of intervals on the real line: each element x of the poset is represented by an interval [x1, x2], such that for any y and z in the poset, y is below z if and only if y2 < z1.

Polysemy[edit]

Under certain circumstances, a single function f : XY is at once an isomorphism from several mathematical structures on X. Since each of those structures may be thought of, intuitively, as a meaning of the image Y (one of the things that Y is trying to tell us), this phenomenon is called polysemy—a term borrowed from linguistics. Some examples of polysemy include:

  • intersection polysemy—pairs of graphs G1 and G2 on a common vertex set V that can be simultaneously represented by a single collection of sets Sv, such that any distinct vertices u and w in V are adjacent in G1, if and only if their corresponding sets intersect ( SuSw ≠ Ø ), and are adjacent in G2 if and only if the complements do ( SuCSwC ≠ Ø ).[10]
  • competition polysemy—motivated by the study of ecological food webs, in which pairs of species may have prey in common or have predators in common. A pair of graphs G1 and G2 on one vertex set is competition polysemic, if and only if there exists a single directed graph D on the same vertex set, such that any distinct vertices u and v are adjacent in G1, if and only if there is a vertex w such that both uw and vw are arcs in D, and are adjacent in G2, if and only if there is a vertex w such that both wu and wv are arcs in D.[11]
  • interval polysemy—pairs of posets P1 and P2 on a common ground set that can be simultaneously represented by a single collection of real intervals, that is an interval-order representation of P1 and an interval-containment representation of P2.[12]

See also[edit]

References[edit]

  1. ^ "The Definitive Glossary of Higher Mathematical Jargon — Mathematical Representation". Math Vault. 2019-08-01. Retrieved 2019-12-07.
  2. ^ Weisstein, Eric W. "Group Representation". mathworld.wolfram.com. Retrieved 2019-12-07.
  3. ^ a b Teleman, Constantin. "Representation Theory" (PDF). math.berkeley.edu. Retrieved 2019-12-07.
  4. ^ *McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia: Society for Industrial and Applied Mathematics, doi:10.1137/1.9780898719802, ISBN 978-0-89871-430-2, MR 1672910
  5. ^ Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections", Canadian Journal of Mathematics, 18 (1): 106–112, CiteSeerX 10.1.1.210.6950, doi:10.4153/cjm-1966-014-3, MR 0186575
  6. ^ *Biggs, Norman (1994), Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, ISBN 978-0-521-45897-9, MR 1271140
  7. ^ *Trotter, William T. (1992), Combinatorics and Partially Ordered Sets: Dimension Theory, Johns Hopkins Series in the Mathematical Sciences, Baltimore: The Johns Hopkins University Press, ISBN 978-0-8018-4425-6, MR 1169299
  8. ^ *Scheinerman, Edward (1991), "A note on planar graphs and circle orders", SIAM Journal on Discrete Mathematics, 4 (3): 448–451, doi:10.1137/0404040, MR 1105950
  9. ^ *Fishburn, Peter C. (1985), Interval Orders and Interval Graphs: A Study of Partially Ordered Sets, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, ISBN 978-0-471-81284-5, MR 0776781
  10. ^ *Tanenbaum, Paul J. (1999), "Simultaneous intersection representation of pairs of graphs", Journal of Graph Theory, 32 (2): 171–190, doi:10.1002/(SICI)1097-0118(199910)32:2<171::AID-JGT7>3.0.CO;2-N, MR 1709659
  11. ^ *Fischermann, Miranca; Knoben, Werner; Kremer, Dirk; Rautenbachh, Dieter (2004), "Competition polysemy", Discrete Mathematics, 282 (1–3): 251–255, doi:10.1016/j.disc.2003.11.014, MR 2059526
  12. ^ *Tanenbaum, Paul J. (1996), "Simultaneous representation of interval and interval-containment orders", Order, 13 (4): 339–350, CiteSeerX 10.1.1.53.8988, doi:10.1007/BF00405593, MR 1452517