The first order theory of G(n,c∕n)

A well-known result from the 1960 paper of Erdős and Rényi (1960) [2] tells us that the almost sure theory for first order language on the random graph sequence $\left\{G(n,c{n}^{-1})\right\}$ is not complete. Our paper proposes and proves what the complete set of completions of the almost sure theory for $\left\{G(n,c{n}^{-1})\right\}$ should be. The almost sure theory $T$ consists of two sentence groups: the first states that all the components are trees or unicyclic components, and the second states that, given any $k\in \mathbb{N}$ and any finite tree $t$, there are at least $k$ components isomorphic to $t$. We define a $k$-completion of $T$ to be a first order property $A$, such that if $T\cup A$ holds for a graph (which indicates that the property described in sentence $A$ is satisfied by the graph, and for every sentence $B$ in the theory $T$, the property described by $B$ is also satisfied by the graph), we can fully describe the first order sentences of quantifier depth $\le k$ that hold for that graph. We show that a $k$-completion $A$ specifies the numbers, up to “cutoff” $k$, of the (finitely many) unicyclic component types of given parameters (that only depend on $k$) that the graph contains. A complete set of $k$-completions is then the finite collection of all possible $k$-completions.     

List star edge coloring of k-degenerate graphs

A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree $\Delta$ is at most $?\frac{3\Delta }{2}?$, which is tight. In this paper, we study the list star edge coloring of $k$-degenerate graphs. Let $c{h}_{st}^{\prime }\left(G\right)$ be the list star chromatic index of $G$: the minimum $s$ such that for every $s$-list assignment $L$ for the edges, $G$ has a star edge coloring from $L$. By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. $c{h}_{st}^{\prime }\left(T\right)\le ?\frac{3\Delta }{2}?$ for any tree $T$ with maximum degree $\Delta$. And then by applying some orientation technique we present two upper bounds for list star chromatic index of $k$-degenerate graphs.     

On the growth factor upper bound for Aasen’s algorithm

Aasen’s algorithm factorizes a symmetric indefinite matrix $A$ as $A=P^{T}LT{L}^{T}P$, where $P$ is a permutation matrix, $L$ is unit lower triangular with its first column being the first column of the identity matrix, and $T$ is tridiagonal. In this note, we provide a growth factor upper bound for Aasen’s algorithm which is much smaller than that given by Higham. We also show that the upper bound we have given is not tight when the matrix dimension is greater than or equal to 6.     

Convergence of Picard’s iteration using projection algorithm for noncyclic contractions

Given $A$ and$B$ two nonempty subsets of a metric space, a mapping $T:A\cup B\to A\cup B$ is noncyclic provided that $T\left(A\right)?A$ and $T\left(B\right)?B$. A point $(p,q)\in A\times B$ is called a best proximity pair for the noncyclic mapping $T$ if $p=Tp,q=Tq$ and $d(p,q)=\mathrm{dist}(A,B)$. In this article, we survey the convergence of Picard’s iteration to a best proximity pair for noncyclic contractions using a projection algorithm in uniformly convex Banach spaces, where the initial point is in the proximal set of $A$. We also provide some sufficient conditions to ensure the existence of a common best proximity pairs for a pair of noncyclic mappings.     

On the weak representation property in progressively enlarged filtrations with an application in exponential utility maximization

In this paper we show that the weak representation property of a semimartingale $X$ with respect to a filtration $\mathbb{F}$ is preserved in the progressive enlargement $\mathbb{G}$ by a random time $\tau$ avoiding $\mathbb{F}$-stopping times and such that $\mathbb{F}$ is immersed in $\mathbb{G}$. As an application of this, we can solve an exponential utility maximization problem in the enlarged filtration $\mathbb{G}$ following the dynamical approach, based on suitable BSDEs, both over the fixed-time horizon $[0,T]$, $T>0$, and over the random-time horizon $[0,T\wedge \tau ]$.     

Distance matrices of a tree: Two more invariants,and in a unified framework

A classical result of Graham and Pollak (1971) states that the determinant of the distance matrix $D_T$ of any tree $T$ depends only on the number of edges of $T$. This and several other variants of $D_T$ have since been studied – including a $q$-version, a multiplicative version, and directed versions of these – and in all cases, $det\left(D_T\right)$ depends only on the edge-data.In this paper, we introduce a more general framework for bi-directed weighted trees that has not been studied to date; our work is significant for three reasons. First, our setting strictly generalizes – and unifies – all variants of $D_T$ studied to date (with coefficients in an arbitrary unital commutative ring) – including in Graham and Pollak (1971) above, as well as Graham and Lovász (1978), Yan and Yeh (2006), Yan and Yeh (2007), Sivasubramanian (2010), and others.Second, our results strictly improve on state-of-the-art for every variant of the distance matrix studied to date, even in the classical Graham–Pollak case. Here are three results for trees: (1) We compute the minors obtained by deleting arbitrary equinumerous sets of pendant nodes (in fact, more general sub-forests) from the rows and columns of $D_T$, and show these minors depend only on the edge-data and not the tree-structure. (2) We compute a second function of the distance matrix $D_T$: the sum of all its cofactors, termed $cof\left(D_T\right)$. We do so in our general setting and in stronger form, after deleting equinumerous pendant nodes (and more generally) as above – and show these quantities also depend only on the edge-data. (3) We compute in closed form the inverse of $D_T$, extending a result of Graham and Lovász (1978) and answering an open question of Bapat et al. (2006) in greater generality.Third, a new technique is to crucially use commutative algebra arguments – specifically, Zariski density – which to our knowledge are hitherto unused for such matrices/invariants, but are richly rewarding. We also explain why our setting is “most general”, in that for more general edgeweights, $det\left(D_T\right),cof\left(D_T\right)$ depend on the tree structure. In a sense, this completes the study of the invariants $det\left(D_T\right),cof\left(D_T\right)$ for distance matrices of trees $T$ with edge-data in a commutative ring.Our proofs use novel results for arbitrary bi-directed strongly connected graphs $G$: we prove a multiplicative analogue of an additive result by Graham et al. (1977), as well as a novel $q$-version thereof. In particular, we provide closed-form expressions for $det\left(D_G\right)$, $cof\left(D_G\right)$, and $D_G^{-1}$ in terms of their strong blocks. We then show how this subsumes the classical 1977 result, and provide sample applications to adding pendant trees and to cycle-clique graphs (including cactus/polycyclic graphs and hypertrees), subsuming variants in the literature. The final section introduces and computes a third – and novel – invariant for trees, as well as a parallel Graham–Hoffman–Hosoya type result for our “most general” distance matrix $D_T$.     

Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs

Mader (2010) conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge \lfloor \frac{3}{2}k\rfloor +m-1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G-V\left(T^{\prime }\right)$ is $k$-connected. The conjecture has been verified for paths, trees when $k=1$, and stars or double-stars when $k=2$. In this paper we verify the conjecture for two classes of trees when $k=2$.For digraphs, Mader (2012) conjectured that every $k$-connected digraph $D$ with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge 2k+m-1$ for a positive integer $m$ has a dipath $P$ of order $m$ with $\kappa (D-V\left(P\right))\ge k$. The conjecture has only been verified for the dipath with $m=1$, and the dipath with $m=2$ and $k=1$. In this paper, we prove that every strongly connected digraph with minimum semi-degree $\delta \left(D\right)=min\{{\delta }^{+}\left(D\right),{\delta }^{-}\left(D\right)\}\ge m+1$ contains an oriented tree $T$ isomorphic to some given oriented stars or double-stars with order $m$ such that $D-V\left(T\right)$ is still strongly connected.