Let G be a graph with m edges, minimum degree $\delta $ and containing no cycle of length 4. Answering a question of Bollobás and Scott, Fan et al. [‘Bisections of graphs without short cycles’, Combinatorics, Probability and Computing 27(1) (2018), 44–59] showed that if (i) G is $2$-connected, or (ii) $\delta \ge 3$, or (iii) $\delta \ge 2$ and the girth of G is at least 5, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$, where $e(V_i)$ denotes the number of edges of G with both ends in $V_i$. Let $s\ge 2$ be an integer. In this note, we prove that if $\delta \ge 2s-1$ and G contains no $K_{2,s}$ as a subgraph, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$.

In this paper, we present an extension of the model proposed by Lin & Liu that uses the concept of physiological age to model the ageing process by using phase-type distributions to calculate the probability of death. We propose a finite-state Markov jump process to model the hypothetical ageing process in which it is possible the transition rates between non-consecutive physiological ages. Since the Markov process has only a single absorbing state, the death time follows a phase-type distribution. Thus, to build a mortality table the challenge is to estimate this matrix based on the records of the ageing process. Considering the nature of the data, we consider two cases: having continuous time information of the ageing process, and the more interesting and realistic case, having reports of the process just in determined times. If the ageing process is only observed at discrete time points we have a missing data problem, thus, we use a stochastic Expectation–Maximisation (SEM) algorithm to find the maximum likelihood estimator of the intensity matrix. And in order to do that, we build Markov bridges which are sampled using the Bisection method. The theory is illustrated by a simulation study and used to fit real data.

We consider the problem of twenty questions with noisy answers, in which we seek to find a target by repeatedly choosing a set, asking an oracle whether the target lies in this set, and obtaining an answer corrupted by noise. Starting with a prior distribution on the target's location, we seek to minimize the expected entropy of the posterior distribution. We formulate this problem as a dynamic program and show that any policy optimizing the one-step expected reduction in entropy is also optimal over the full horizon. Two such Bayes optimal policies are presented: one generalizes the probabilistic bisection policy due to Horstein and the other asks a deterministic set of questions. We study the structural properties of the latter, and illustrate its use in a computer vision application.

We prove that the cutwidth of the r-dimensional mesh of d-ary trees is of order $\Theta(d^{(r-1)n+1})$, which improves and generalizes previous results.