Jump to content

User:DreamsOfSoftRain/sandbox

From Wikipedia, the free encyclopedia

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.[1]

Definition

[edit]

For a finite graph with vertex set , a vertex coloring is a function where is a set of colors. A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e., ). The chromatic symmetric function denoted is defined to be the weight generating function of proper vertex colorings of :[1][2]

Examples

[edit]

For a partition, let be the monomial symmetric polynomial associated to .

Example 1: Complete Graphs

[edit]

Consider the complete graph on vertices:

  • There are ways to color with exactly colors yielding the term
  • Since every pair of vertices in is adjacent, it can be properly colored with no fewer than colors.

Thus,

Example 2: A Path Graph

[edit]

Consider the path graph of length :

  • There are ways to color with exactly colors, yielding the term
  • For each pair of colors, there are ways to color yielding the terms and for

Altogether, the chromatic symmetric function of is then given by:[2]

Properties

[edit]
  • Let be the chromatic polynomial of , so that is equal to the number of proper vertex colorings of using at most distinct colors. The values of can then be computed by specializing the chromatic symmetric function, setting the first variables equal to and the remaining variables equal to :[1]
  • If is the disjoint union of two graphs, then the chromatic symmetric function for can be written as a product of the corresponding functions for and :[1]
  • A stable partition of is defined to be a set partition of vertices such that each block of is an independent set in . The type of a stable partition is the partition consisting of parts equal to the sizes of the connected components of the vertex induced subgraphs. For a partition , let be the number of stable partitions of with . Then, expands into the augmented monomial symmetric functions, with coefficients given by the number of stable partitions of :[1]
  • Let be the power-sum symmetric function associated to a partition . For , let be the partition whose parts are the vertex sizes of the connected components of the edge-induced subgraph of specified by . The chromatic symmetric function can be expanded in the power-sum symmetric functions via the following formula:[1]
  • Let be the expansion of in the basis of elementary symmetric functions . Let be the number of acyclic orientations on the graph which contain exactly sinks. Then we have the following formula for the number of sinks:[1]

Open Problems

[edit]

There are a number of outstanding questions regarding the chromatic symmetric function which have received substantial attention in the literature surrounding them.

(3+1)-free Conjecture

[edit]

For a partition , let be the elementary symmetric function associated to .

A partially ordered set is called (3+1)-free if it does not contain a subposet isomorphic to the direct sum of the element chain and the element chain. The incomparability graph of a poset is the graph with vertices given by the elements of which includes an edge between two vertices if and only if their corresponding elements in are incomparable.

Conjecture: (Stanley-Stembridge) Let be the incomparability graph of a -free poset, then is -positive.[1]

A weaker positivity result is known for the case of expansions into the basis of Schur functions.

Theorem (Gasharov) Let be the incomparability graph of a -free poset, then is -positive.[3]

In the proof of the theorem above, there is a combinatorial formula for the coefficients of the Schur expansion given in terms of -tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of .

Generalizations

[edit]

There are a number of generalizations of the chromatic symmetric function:

  • There is a categorification of the invariant into a homology theory which is called chromatic symmetric homology.[4] This homology theory is known to be a stronger invariant than the chromatic symmetric function alone.[5] The chromatic symmetric function can also be defined for vertex-weighted graphs,[6] where it satisfies a deletion-contraction property analogous to that of the chromatic polynomial. If the theory of chromatic symmetric homology is generalized to vertex-weighted graphs as well, this deletion-contraction property lifts to a long exact sequence of the corresponding homology theory.[7]
  • There is also a quasisymmetric refinement of the chromatic symmetric function which can be used to refine the formulae expressing in terms of Gessel's basis of fundamental quasisymmetric functions and the expansion in the basis of Schur functions.[8] Fixing an order for the set of vertices, the ascent set of a proper coloring is defined to be . The chromatic quasisymmetric function of a graph is then defined to be:[8]

References

[edit]
  1. ^ a b c d e f g h Stanley, R.P. (1995). "A Symmetric Function Generalization of the Chromatic Polynomial of a Graph". Advances in Mathematics. 111 (1): 166–194. doi:10.1006/aima.1995.1020. ISSN 0001-8708.
  2. ^ a b Saliola, Franco (October 15, 2022). "Lectures on Symmetric Functions with a view towards Hessenberg varieties — Draft" (PDF). Archived (PDF) from the original on October 18, 2022. Retrieved April 27, 2024.
  3. ^ Gasharov, Vesselin (1996). "Incomparability graphs of (3+1)-free posets are s-positive" (PDF). Discrete Mathematics. 157: 193–197.
  4. ^ Sazdanovic, Radmila; Yip, Martha (2018-02-01). "A categorification of the chromatic symmetric function". Journal of Combinatorial Theory, Series A. 154: 218–246. doi:10.1016/j.jcta.2017.08.014. ISSN 0097-3165.
  5. ^ Chandler, Alex; Sazdanovic, Radmila; Stella, Salvatore; Yip, Martha (2023-09-01). "On the strength of chromatic symmetric homology for graphs". Advances in Applied Mathematics. 150: 102559. doi:10.1016/j.aam.2023.102559. ISSN 0196-8858.
  6. ^ Crew, Logan; Spirkl, Sophie (2020-01-15), A Deletion-Contraction Relation for the Chromatic Symmetric Function, doi:10.48550/arXiv.1910.11859, retrieved 2024-04-27
  7. ^ Ciliberti, Azzurra (2024-01-01). "A deletion–contraction long exact sequence for chromatic symmetric homology". European Journal of Combinatorics. 115: 103788. doi:10.1016/j.ejc.2023.103788. ISSN 0195-6698.
  8. ^ a b Shareshian, John; Wachs, Michelle L. (June 4, 2016). "Chromatic quasisymmetric functions". Advances in Mathematics. 295: 497–551. doi:10.1016/j.aim.2015.12.018. ISSN 0001-8708.