Symmetric Chromatic Function for Voltage Graphs

Exploring the concept of a Symmetric Chromatic Function (SCF) for voltage graphs involves proper coloring conditions for edges and vertices, edge polarization functions, and decomposing voltage graphs into disconnected and connected squiggly graphs. The SCF allows for determining the number of ways to properly color a graph and involves notations and calculations to achieve this. Understanding types of edges like full and squiggly edges, and the transformation between them, is essential in this context.

• Voltage Graphs
• Symmetric Chromatic Function
• Edge Polarization
• Proper Coloring
• Squiggly Graphs

beas805 Follow

Uploaded on Sep 22, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. A Symmetric Chromatic Function for Voltage Graphs Noah Donald The Ohio State University, Columbus Undergraduate Research Advisor: Prof. Sergei Chmutov Assistance on Project by Ishaan Shah OSU-Marion, MIGHTY LXII Noah Donald | A Symmetric Chromatic Function for Voltage Graphs

2. Voltage Graphs and a Proper Coloring. Example of the edge polarization function: A voltage graph consists of: A graph, ? = ?,? ? ? A group, An edge labeling, ? An edge polarization, ? An edge is properly colored if any one of the following holds for an edge (??,??): 1. ?1?? ?1(??) 2. If ?1?? = ?1(??) and ? ?1 ?2 ??,?? = 1, then ? ??,?? ?2?? ?2(??) ? ?1,?2 ? ?2,?1 = 1 = 1 Example of a voltage graph (?, ,?,?) 3. If ?1?? = ?2(??) and ? ??,?? = 1, then ? ??,?? ?2?? = ?2(??). ?1 The vertices of the voltage graph are colored using the following functions: ?1:? ?2:? ?:? where ? ? = ?1? ,?2? Example of a properly colored edge ?12 ?31 ?12 ?1 ?2 ?3 ?2 (1,?) (1, ) ?23 ?12? ?:? ?:? 1,1 Noah Donald | A Symmetric Chromatic Function for Voltage Graphs

3. A Symmetric Chromatic Function. Notation: ???= ??1??,?1?? ????= ?? ????= ??2??,? ?,? = (??,??) ??= ?? ?1???2 ?? ??, ? = ? Here, ??? is the 0-1 valued term that determines when a coloring is improper. If ?1,?2 are disconnected graphs and ? = ?1 ?2, then ?= ?1 ?2 ??,?? ?2??,?2?? ???=1 2??? ????+ ????+ ??????? ???? ??,?? ?2?? Expanding the product term in the SCF gives a subsets of edges formulation. Example Calculation: We define the symmetric chromatic function (SCF) as: ?12 ?1 ?2 ???? ?, ,?,? = ?? ? ? 1 (?, ,?,?)= ?? ?:? ?:? ? ?? ?????? 2 X = ?(?,?) If we have the coloring ?:? and ?? ? , then the coefficient of the term ?? in the SCF is the number of ways to properly color the graph using only and all of the elements of ??[?]. We can sum over all colorings of the graph by introducing the second factor to encode the proper coloring condition. (?,?) ?(?,?)?(?,?12?) ?,? (?, ,?,?)= ?? ?,? ? (1 ???) ?:? Noah Donald | A Symmetric Chromatic Function for Voltage Graphs

4. Squiggly Voltage Graphs. Types of Edges: Full edges are edges which require the proper coloring condition for the vertices connected to the edge. Squiggly edges are edges which require an improper coloring for the vertices connected to the edge. Example of this formula: (?,?14?) 4 ?12 ?1 ?2 ?14 (?,?) = 1 ?12 ?1 ?2 ?1 ?2 ?13?12 (?,?13?) 2 3 (?,?12?) Using this algorithm, we can decompose voltage graphs into combinations of disconnected graphs and connected squiggly graphs. Example of a squiggly graph whose colorablity is independent of the chosen coloring. Proper coloring of a squiggly edge: ?12 ?1 ?2 By coloring any one vertex in a connected squiggly graph, we can find a proper coloring by propagating the group element by paths to any other group element. ?1 (?,?) (?, ) ?31 ?12 ?12? = ?2 ?3 Turning full edges into squiggly edges: Let ? ? and ? = ? ?. Then, ?23 For any coloring to work we require: ?12?23?31= ? ( ?,? ? , )= ( ?, ? ? ? , ) ?, ? ? ? ? , Noah Donald | A Symmetric Chromatic Function for Voltage Graphs

5. Moving Rules. The goal is to move edges over other edges and leave the SCF invariant under this transformation. ?23 ?23 ?2 ?3 ?2 ?3 ?12 ?12 If we think of the vertices as labeled here, then we can write a formula which incorporates arbitrary edge polarizations. ?1 ?1 ?23 ?23 ?13= ?23 ?23?12 ?12 ?13 ?2 ?3 ?2 ?3 This formula holds for moving squiggly edges over squiggly edges and for moving full edges over squiggly edges. 1 1 ?13= ?12?23 ?13= ?12?23 The edge here has picked up a phase from the edge it moved over. ?1 ?1 Noah Donald | A Symmetric Chromatic Function for Voltage Graphs

6. Going Forward and Algebraic Bases. Turning full edges into squiggly edges: ( ?,? ? , )= ( ?, ? ? ? , ) ?, ? ? ? ? , By performing the decomposition into radiating voltage stars , we can use this as an algebraic basis for the SCF. 4 ?14 ?46 (?, ,?,?) = 1 5 3 + 6 4 (? is a tree) ?13?12 2 3 Star Basis Element: Let ?: ? ? be a group action defined by, ? ?, 1, , ? = 1?, , ?? . ? = ?,???,???, ??? ? ? ? ? is the orbit of ? in ? under the group action ?. Example term: ??,?= ??(?) 4 ? ? ?(?) ?14 1 ??: ? ? ? , ? {2, ,? + 1} ?1: ? ? ? defined by ???,?1, ,?? = ?,? = 1 ?13?12 2 3 ??,? 1 ?(?,?14,?13,?12),4= ??(?) ?? ? = ?(?,?2? )?(?,?3? ) ?(?,??+1? ) ? ? 4((?,?14,?13,?12)) Noah Donald | A Symmetric Chromatic Function for Voltage Graphs

7. References. Noble, S., Welsh, D. (1999). A weighted graph polynomial from chromatic invariants of knots. Annales de l institut Fourier, 49(3), 1057 1087. Stanley, R.P. (1995). A Symmetric Function Generalization of the Chromatic Polynomial of a Graph. Advances in Mathematics, 111, 166-194. Zaslavsky, T. (1982). Signed Graph Coloring. Discrete Math, 39, 215-228. Zaslavsky, T. (1982). Chromatic invariants of signed graphs. Discrete Math, 42, 287 312. Noah Donald | A Symmetric Chromatic Function for Voltage Graphs