Tutte Polynomial, Complete Invariant, and Theta Series
- PDF / 374,233 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 176 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Tutte Polynomial, Complete Invariant, and Theta Series Misaki Kume1 • Tsuyoshi Miezaki2 Hidehiro Shinohara4
•
Tadashi Sakuma3
•
Received: 8 August 2020 / Revised: 4 October 2020 / Accepted: 5 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract In this study, we present two results that relate Tutte polynomials. First, we provide new and complete polynomial invariants for graphs. We note that the number of variables of our polynomials is one. Second, let L1 and L2 be two non-isomorphic lattices. We state that L1 and L2 are theta series equivalent if those theta series are the same. The problem of identifying theta series equivalent lattices is discussed in Prof. Conway’s book The Sensual (Quadratic) Form with the title ‘‘Can You Hear the Shape of a Lattice?’’ In this study, we present a method to find theta series equivalent lattices using matroids and their Tutte polynomials. Keywords Matroid Tutte polynomial Code Lattice Weight enumerator Theta series
Mathematics Subject Classification Primary 05B35 Secondary 94B05 94B75
& Tsuyoshi Miezaki [email protected] Misaki Kume [email protected] Tadashi Sakuma [email protected] Hidehiro Shinohara [email protected] 1
University of the Ryukyus, Junior High School, Okinawa 903-0213, Japan
2
Faculty of Education, University of the Ryukyus, Okinawa 903-0213, Japan
3
Faculty of Science, Yamagata University, Yamagata 990-8560, Japan
4
Institute for Excellence in Higher Education, Tohoku University, Sendai 980-8576, Japan
123
Graphs and Combinatorics
1 Introduction In this study, we provide two results that relate the Tutte polynomials. The first result is as follows: In [9], de la Harpe and Jones introduced graphinvariant polynomials. We refer to these polynomials as n-state polynomials. The main focus of this paper is on non-directed graphs. Let G be a graph and X be a finite set with n elements. Wn ¼ ðxij Þ is an jXj jXj symmetric matrix indexed by the elements of X. We assume that X ¼ f1; 2; . . .; ng and xij are variables. Moreover, let r : VðGÞ ! X be a state function. Subsequently, the n-state polynomials with nðn þ 1Þ=2 variables are defined as follows: Definition 1.1 [9] ZWn ðGÞ ¼
X
Y
Wn ðrðuÞ; rðvÞÞ;
r:state uv2EðGÞ
where r runs over all state functions. The special values of these polynomials are approximately the same as certain known polynomial invariants for graphs. For example, let 0 1 x1 þ y y y B y x1 þ y y C B C B C: WNegami ¼ B . . . . .. C .. .. @ .. A y
y
x1 þ y
Then, ZWNegami ðGÞ are known as Negami polynomials [13]. In [15], Oxley demonstrated that ZWNegami ðGÞ is essentially equivalent to the Tutte polynomials [17–19]. Therefore, n-state polynomials are a generalization of the Tutte polynomials. Moreover, let WextNegami ¼ ðxij Þ, 8 > < xi þ y ði ¼ j\nÞ; xij ¼ xn þ y ði ¼ j nÞ; > : y: Then, ZWextNegami ðGÞ are known as extended Negami polynomials [14]. In this study, we demonstrate tha
Data Loading...
