Łukasz Bożyk

\noindent The well-known and celebrated identity of Girard (1629) and Waring (1762) states that \[x^n+y^n=\sum_{m=0}^{\lfloor n/2\rfloor}(-1)^m\frac{n}{n-m}\binom{n-m}{m}\left(xy\right)^m\left(x+y\right)^{n-2m}\] and can be easily proven algebraically (see H.W. Gould, The Girard--Waring power sum formulas for symmetric functions and Fibonacci sequences,} Fibonacci Quart. 37 (1999), no. 2, 135--140). In this note, we provide a combinatorial proof of this identity.

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $$\ell _1$$ℓ 1 and $$\ell _2$$ℓ 2 , one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is $$\mathsf {NP}$$NP -complete by the classical result of Lewis and Yannakakis [20]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $${\mathcal {O}}(9^k \cdot n^9)$$O ( 9 k · n 9 ) , and also give a polynomial-time 9-approximation algorithm.

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines $l_1$ and $l_2$, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time $O(9^k\cdot n^9)$, and also give a polynomial-time 9-approximation algorithm.