hu / en

Megjelent Csáji Gergely és szerzőtársai tanulmánya a European Journal of Combinatorics folyóiratban

european journal of combinatorics

Permutation Tutte polynomial

Csongor Beke, Gergely Kál Csáji, Péter Csikvári, Sára Pituk

Abstract

The classical Tutte polynomial is a two-variate polynomial 𝑇𝐺(𝑥,𝑦) associated to graphs or more generally, matroids. In this paper, we introduce a polynomial 𝑇˜𝐻(𝑥,𝑦) associated to a bipartite graph 𝐻 that we call the permutation Tutte polynomial of the graph 𝐻. It turns out that 𝑇𝐺(𝑥,𝑦) and 𝑇˜𝐻(𝑥,𝑦) share many properties, and the permutation Tutte polynomial serves as a tool to study the classical Tutte polynomial. We discuss the analogues of Brylawsi’s identities and Conde–Merino–Welsh type inequalities. In particular, we will show that if 𝐻 does not contain isolated vertices, then𝑇˜𝐻(3,0)𝑇˜𝐻(0,3)≥𝑇˜𝐻(1,1)2,which gives a short proof of the analogous result of Jackson:𝑇𝐺(3,0)𝑇𝐺(0,3)≥𝑇𝐺(1,1)2for graphs without loops and bridges. We also give improvement on the constant 3 in this statement by showing that one can replace it with 2.9243.

2024

Okt

08

H

K

Sz

Cs

P

Sz

V

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

Következő hónap >
a

2024

Okt

08

H

K

Sz

Cs

P

Sz

V

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

Következő hónap >