No Arabic abstract
The enumeration of lattice paths in wedges poses unique mathematical challenges. These models are not translationally invariant, and the absence of this symmetry complicates both the derivation of a functional recurrence for the generating function, and solving for it. In this paper we consider a model of partially directed walks from the origin in the square lattice confined to both a symmetric wedge defined by $Y = pm pX$, and an asymmetric wedge defined by the lines $Y= pX$ and Y=0, where $p > 0$ is an integer. We prove that the growth constant for all these models is equal to $1+sqrt{2}$, independent of the angle of the wedge. We derive functional recursions for both models, and obtain explicit expressions for the generating functions when $p=1$. From these we find asymptotic formulas for the number of partially directed paths of length $n$ in a wedge when $p=1$. The functional recurrences are solved by a variation of the kernel method, which we call the ``iterated kernel method. This method appears to be similar to the obstinate kernel method used by Bousquet-Melou. This method requires us to consider iterated compositions of the roots of the kernel. These compositions turn out to be surprisingly tractable, and we are able to find simple explicit expressions for them. However, in spite of this, the generating functions turn out to be similar in form to Jacobi $theta$-functions, and have natural boundaries on the unit circle.
Directed paths have been used extensively in the scientific literature as a model of a linear polymer. Such paths models in particular the conformational entropy of a linear polymer and the effects it has on the free energy. These directed models are simplifi
A long standing open problem in extremal graph theory is to describe all graphs that maximize the number of induced copies of a path on four vertices. The character of the problem changes in the setting of oriented graphs, and becomes more tractable. Here we resolve this problem in the setting of oriented graphs without transitive triangles.
Understanding how and how far information, behaviors, or pathogens spread in social networks is an important problem, having implications for both predicting the size of epidemics, as well as for planning effective interventions. There are, however, two main challenges for inferring spreading paths in real-world networks. One is the practical difficulty of observing a dynamic process on a network, and the other is the typical constraint of only partially observing a network. Using a static, structurally realistic social network as a platform for simulations, we juxtapose three distinct paths: (1) the stochastic path taken by a simulated spreading process from source to target; (2) the topologically shortest path in the fully observed network, and hence the single most likely stochastic path, between the two nodes; and (3) the topologically shortest path in a partially observed network. In a sampled network, how closely does the partially observed shortest path (3) emulate the unobserved spreading path (1)? Although partial observation inflates the length of the shortest path, the stochastic nature of the spreading process also frequently derails the dynamic path from the shortest path. We find that the partially observed shortest path does not necessarily give an inflated estimate of the length of the process path; in fact, partial observation may, counterintuitively, make the path seem shorter than it actually is.
Polymers in confined spaces lose conformational entropy. This induces a net repulsive entropic force on the walls of the confining space. A model for this phenomenon is a lattice walk between confining walls, and in this paper a model of an adsorbing partially directed walk is used. The walk is placed in a half square lattice $L^2_+$ with boundary $partial L^2_+$, and confined between two vertical parallel walls, which are vertical lines in the lattice, a distance $w$ apart. The free energy of the walk is determined, as a function of $w$, for walks with endpoints in the confining walls and adsorbing in $partial L^2_+$. This gives the entropic force on the confining walls as a function of $w$. It is shown that there are zero force points in this model and the locations of these points are determined, in some cases exactly, and in other cases asymptotically.
We consider a directed walk model of a homopolymer (in two dimensions) which is self-interacting and can undergo a collapse transition, subject to an applied tensile force. We review and interpret all the results already in the literature concerning the case where this force is in the preferred direction of the walk. We consider the force extension curves at different temperatures as well as the critical-force temperature curve. We demonstrate that this model can be analysed rigorously for all key quantities of interest even when there may not be explicit expressions for these quantities available. We show which of the techniques available can be extended to the full model, where the force has components in the preferred direction and the direction perpendicular to this. Whilst the solution of the generating function is available, its analysis is far more complicated and not all the rigorous techniques are available. However, many results can be extracted including the location of the critical point which gives the general critical-force temperature curve. Lastly, we generalise the model to a three-dimensional analogue and show that several key properties can be analysed if the force is restricted to the plane of preferred directions.