|
Chromatic Symmetric Function
The chromatic symmetric function is a symmetric function invariant of graphs studied in algebraic graph theory, a branch of mathematics. It is the weight generating function for proper graph colorings, and was originally introduced by Richard Stanley as a generalization of the chromatic polynomial of a graph. Definition For a finite graph G=(V,E) with vertex set V=\, a ''vertex coloring'' is a function \kappa:V\to C where C is a set of colors. A vertex coloring is called ''proper'' if all adjacent vertices are assigned distinct colors (i.e., \\in E \implies \kappa(i)\neq\kappa(j)). The chromatic symmetric function denoted X_G(x_1,x_2,\ldots) is defined to be the weight generating function of proper vertex colorings of G:X_G(x_1,x_2,\ldots):=\sum_x_x_\cdots x_ Examples For \lambda a partition, let m_\lambda be the monomial symmetric polynomial associated to \lambda. Example 1: complete graphs Consider the complete graph K_n on n vertices: * There are n! ways to color K_n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ring Of Symmetric Functions
In algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in ''n'' indeterminates, as ''n'' goes to infinity. This ring serves as universal structure in which relations between symmetric polynomials can be expressed in a way independent of the number ''n'' of indeterminates (but its elements are neither polynomials nor functions). Among other things, this ring plays an important role in the representation theory of the symmetric group. The ring of symmetric functions can be given a coproduct and a bilinear form making it into a positive selfadjoint graded Hopf algebra that is both commutative and cocommutative. Symmetric polynomials The study of symmetric functions is based on that of symmetric polynomials. In a polynomial ring in some finite set of indeterminates, a polynomial is called ''symmetric'' if it stays the same whenever the indeterminates are permuted in any way. More forma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Elementary Symmetric Polynomial
In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary symmetric polynomials. That is, any symmetric polynomial is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials. There is one elementary symmetric polynomial of degree in variables for each positive integer , and it is formed by adding together all distinct products of distinct variables. Definition The elementary symmetric polynomials in variables , written for , are defined by :\begin e_1 (X_1, X_2, \dots, X_n) &= \sum_ X_a,\\ e_2 (X_1, X_2, \dots, X_n) &= \sum_ X_a X_b,\\ e_3 (X_1, X_2, \dots, X_n) &= \sum_ X_a X_b X_c,\\ \end and so forth, ending with : e_n (X_1, X_2, \dots,X_n) = X_1 X_2 \cdots X_n. In general, for we define : e_k (X_1 , \ldots , X_n )=\s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deletion–contraction Formula
In graph theory, a deletion-contraction formula / recursion is any formula of the following recursive form: :f(G) = f(G \setminus e) + f(G / e). Here ''G'' is a graph, ''f'' is a function on graphs, ''e'' is any edge of ''G'', ''G'' \ ''e'' denotes edge deletion, and ''G'' / ''e'' denotes contraction. Tutte refers to such a function as a W-function. The formula is sometimes referred to as the fundamental reduction theorem. In this article we abbreviate to DC. R. M. Foster had already observed that the chromatic polynomial is one such function, and Tutte began to discover more, including a function ''f'' = ''t''(''G'') counting the number of spanning trees of a graph (also see Kirchhoff's theorem). It was later found that the flow polynomial is yet another; and soon Tutte discovered an entire class of functions called Tutte polynomials (originally referred to as dichromates) that satisfy DC. Examples Spanning trees The number of spanning trees t( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
European Journal Of Combinatorics
The ''European Journal of Combinatorics'' is an international peer-reviewed scientific journal that specializes in combinatorics. The journal primarily publishes papers dealing with mathematical structures within combinatorics and/or establishing direct links between combinatorics and the theories of computing. The journal includes full-length research papers, short notes, and research problems on several topics. This journal has been founded in 1980 by Michel Deza, Michel Las Vergnas and Pierre Rosenstiehl. The current editor-in-chief is Patrice Ossona de Mendez and the vice editor-in-chief is Marthe Bonamy. Abstracting and indexing The journal is abstracted and indexed in *MathSciNet, *Science Citation Index Expanded, *Scopus Scopus is a scientific abstract and citation database, launched by the academic publisher Elsevier as a competitor to older Web of Science in 2004. The ensuing competition between the two databases has been characterized as "intense" and is c . ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of Combinatorial Theory
The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applications of combinatorics. ''Series B'' is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as ''JCTA'' and ''JCTB''. The journal was founded in 1966 by Frank Harary and Gian-Carlo Rota.They are acknowledged on the journals' title pages and Web sites. SeEditorial board of JCTA Originally there was only one journal, which was split into two parts in 1971 as the field grew rapidly. In 2020, most of the editorial board of ''JCTA'' resigned to form a new, |
Homology Theory
In mathematics, the term homology, originally introduced in algebraic topology, has three primary, closely-related usages. The most direct usage of the term is to take the ''homology of a chain complex'', resulting in a sequence of abelian groups called ''homology groups.'' This operation, in turn, allows one to associate various named ''homologies'' or ''homology theories'' to various other types of mathematical objects. Lastly, since there are many homology theories for topological spaces that produce the same answer, one also often speaks of the ''homology of a topological space''. (This latter notion of homology admits more intuitive descriptions for 1- or 2-dimensional topological spaces, and is sometimes referenced in popular mathematics.) There is also a related notion of the cohomology of a cochain complex, giving rise to various cohomology theories, in addition to the notion of the cohomology of a topological space. Homology of chain complexes To take the homology o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Categorification
In mathematics, categorification is the process of replacing set-theoretic theorems with category-theoretic analogues. Categorification, when done successfully, replaces sets with categories, functions with functors, and equations with natural isomorphisms of functors satisfying additional properties. The term was coined by Louis Crane. The reverse of categorification is the process of ''decategorification''. Decategorification is a systematic process by which isomorphic objects in a category are identified as equal. Whereas decategorification is a straightforward process, categorification is usually much less straightforward. In the representation theory of Lie algebras, modules over specific algebras are the principal objects of study, and there are several frameworks for what a categorification of such a module should be, e.g., so called (weak) abelian categorifications. Categorification and decategorification are not precise mathematical procedures, but rather a class o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semistandard Young Tableaux
In mathematics, a Young tableau (; plural: tableaux) is a combinatorial object useful in representation theory and Schubert calculus. It provides a convenient way to describe the group representations of the symmetric and general linear groups and to study their properties. Young tableaux were introduced by Alfred Young, a mathematician at Cambridge University, in 1900. They were then applied to the study of the symmetric group by Georg Frobenius in 1903. Their theory was further developed by many mathematicians, including Percy MacMahon, W. V. D. Hodge, G. de B. Robinson, Gian-Carlo Rota, Alain Lascoux, Marcel-Paul Schützenberger and Richard P. Stanley. Definitions ''Note: this article uses the English convention for displaying Young diagrams and tableaux''. Diagrams A Young diagram (also called a Ferrers diagram, particularly when represented using dots) is a finite collection of boxes, or cells, arranged in left-justified rows, with the row lengths in non-increas ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Discrete Mathematics (journal)
''Discrete Mathematics'' is a biweekly peer-reviewed scientific journal in the broad area of discrete mathematics, combinatorics, graph theory, and their applications. It was established in 1971 and is published by North-Holland Publishing Company. It publishes both short notes, full length contributions, as well as survey articles. In addition, the journal publishes a number of special issues each year dedicated to a particular topic. Although originally it published articles in French and German, it now allows only English language articles. The editor-in-chief is Douglas West ( University of Illinois, Urbana). History The journal was established in 1971. The first article it published was written by Paul Erdős, who went on to publish a total of 84 papers in the journal. Abstracting and indexing The journal is abstracted and indexed in: According to the ''Journal Citation Reports'', the journal has a 2020 impact factor The impact factor (IF) or journal impact facto ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schur Polynomial
In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in ''n'' variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of polynomial irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur polynomials can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials. Definition (Jacobi's bialternant formula) Schur polynomials are indexed by integer partitions. Given a partition , where , and each is a non-negative integer, the functions a_ (x ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Comparability
In mathematics, two elements ''x'' and ''y'' of a set ''P'' are said to be comparable with respect to a binary relation ≤ if at least one of ''x'' ≤ ''y'' or ''y'' ≤ ''x'' is true. They are called incomparable if they are not comparable. Rigorous definition A binary relation on a set P is by definition any subset R of P \times P. Given x, y \in P, x R y is written if and only if (x, y) \in R, in which case x is said to be to y by R. An element x \in P is said to be , or (), to an element y \in P if x R y or y R x. Often, a symbol indicating comparison, such as \,,\, \geq, and many others) is used instead of R, in which case x < y is written in place of which is why the term "comparable" is used. Comparability with respect to induces a canonical binary relation on ; specifically, the induced by is defined to be the set of all pairs such that i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Comparability Graph
In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. Definitions and characterization For any strict partially ordered set , the comparability graph of is the graph of which the vertices are the elements of and the edges are those pairs of elements such that . That is, for a partially ordered set, take the directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ..., apply t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
