ﻻ يوجد ملخص باللغة العربية
The chromatic polynomial and its generalization, the chromatic symmetric function, are two important graph invariants. Celebrated theorems of Birkhoff, Whitney, and Stanley show how both objects can be expressed in three different ways: as sums over all spanning subgraphs, as sums over spanning subgraphs with no broken circuits, and in terms of acyclic orientations with compatible colorings. We establish all six of these expressions bijectively. In fact, we do this with only two bijections, as the proofs in the symmetric function setting are obtained using the same bijections as in the polynomial case and the bijection for broken circuits is just a restriction of the one for all spanning subgraphs.
Define a permutation to be any sequence of distinct positive integers. Given two permutations p and s on disjoint underlying sets, we denote by p sh s the set of shuffles of p and s (the set of all permutations obtained by interleaving the two permut
The classical theorem of Vizing states that every graph of maximum degree $d$ admits an edge-coloring with at most $d+1$ colors. Furthermore, as it was earlier shown by KH{o}nig, $d$ colors suffice if the graph is bipartite. We investigate the exis
In this paper we answer a question posed by R. Stanley in his collection of Bijection Proof Problems (Problem 240). We present a bijective proof for the enumeration of walks of length $k$ a chess rook can move along on an $mtimes n$ board starting and ending on the same square.
We give a shorter proof of the following theorem of Kathryn Mann cite{M}: the identity component of the group of the compactly supported $C^r$ diffeomorphisms of $R^n$ cannot admit a nontrivial $C^p$-action on $S^1$, provided $ngeq2$, $r eq n+1$ and
Let $r(n,k)$ (resp. $s(n,k)$) be the number of Schroder paths (resp. little Schroder paths) of length $2n$ with $k$ hills, and set $r(0,0)=s(0,0)=1$. We bijectively establish the following recurrence relations: begin{align*} r(n,0)&=sumlimits_{j=0}^{