The indecomposable tournaments T with |W5(T)|=|T|−2

We consider a tournament $T=(V,A)$. For $X?V$, the subtournament of T induced by X is $T[X]=(X,A\cap (X\times X))$. An interval of T is a subset X of V such that, for $a,b\in X$ and $x\in V?X$, $(a,x)\in A$ if and only if $(b,x)\in A$. The trivial intervals of T are ?, $\{x\}(x\in V)$ and V. A tournament is indecomposable if all its intervals are trivial. For $n?2$, $W_{2n+1}$ denotes the unique indecomposable tournament defined on $\{0,\dots ,2n\}$ such that $W_{2n+1}[\{0,\dots ,2n?1\}]$ is the usual total order. Given an indecomposable tournament T, $W_5(T)$ denotes the set of $v\in V$ such that there is $W?V$ satisfying $v\in W$ and $T[W]$ is isomorphic to $W_5$. Latka [6] characterized the indecomposable tournaments T such that $W_5(T)=?$. The authors [1] proved that if $W_5(T)\ne ?$, then $|W_5(T)|?|V|?2$. In this note, we characterize the indecomposable tournaments T such that $|W_5(T)|=|V|?2$.     

Odd values of the Rogers–Ramanujan functions

Let $g(n)$ and $h(n)$ be the coefficients of the Rogers–Ramanujan identities. We obtain asymptotic formulas for the number of odd values of $g(n)$ for odd n, and $h(n)$ for even n, which improve Gordon's results. We also obtain lower bounds for the number of odd values of $g(n)$ for even n, and $h(n)$ for odd n.     

A note on two source location problems

We consider Source Location ($\mathsf{SL}$) problems: given a capacitated network $G=(V,E)$, cost $c(v)$ and a demand $d(v)$ for every $v\in V$, choose a min-cost $S\subseteq V$ so that $\lambda (v,S)⩾d(v)$ holds for every $v\in V$, where $\lambda (v,S)$ is the maximum flow value from v to S. In the directed variant, we have demands $d^{\mathit{in}}(v)$ and $d^{\mathit{out}}(v)$ and we require $\lambda (S,v)⩾d^{\mathit{in}}(v)$ and $\lambda (v,S)⩾d^{\mathit{out}}(v)$. Undirected $\mathsf{SL}$ is (weakly) NP-hard on stars with $r(v)=0$ for all v except the center. But, it is known to be polynomially solvable for uniform costs and uniform demands. For general instances, both directed an undirected $\mathsf{SL}$ admit a $(\ln D+1)$-approximation algorithms, where D is the sum of the demands; up to constant this is tight, unless P = NP. We give a pseudopolynomial algorithm for undirected $\mathsf{SL}$ on trees with running time $O(|V|{\Delta }^3)$, where $\Delta ={\max }_{v\in V}d(v)$. This algorithm is used to derive a linear time algorithm for undirected $\mathsf{SL}$ with $\Delta ⩽3$. We also consider the Single Assignment Source Location ($\mathsf{SASL}$) where every $v\in V$ should be assigned to a single node $s(v)\in S$. While the undirected $\mathsf{SASL}$ is in P, we give a $(\ln |V|+1)$-approximation algorithm for the directed case, and show that this is tight, unless P = NP.     

Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

Contracting an element from a cocircuit

We consider the situation that M and N are 3-connected matroids such that $|E(N)|⩾4$ and $C^1$ is a cocircuit of M with the property that $M/x_0$ has an N-minor for some $x_0\in C^1$. We show that either there is an element $x\in C^1$ such that $\mathrm{si}(M/x)$ or $\mathrm{co}(\mathrm{si}(M/x))$ is 3-connected with an N-minor, or there is a four-element fan of M that contains two elements of $C^1$ and an element x such that $\mathrm{si}(M/x)$ is 3-connected with an N-minor.