A note on immersion intertwines of infinite graphs

We present a construction of two infinite graphs and , and of an infinite set of graphs such that is an antichain with respect to the immersion relation and, for each graph in , both and are subgraphs of , but no graph properly immersed in admits an immersion of and of . This shows that the class of infinite graphs ordered by the immersion relation does not have the finite intertwine property.     

Graph minors and linkages

Bollobás and Thomason showed that every 22k‐connected graph is k‐linked. Their result used a dense graph minor. In this paper, we investigate the ties between small graph minors and linkages. In particular, we show that a 6‐connected graph with a K minor is 3‐linked. Further, we show that a 7‐connected graph with a K minor is (2,5)‐linked. Finally, we show that a graph of order n and size at least 7n?29 contains a K minor. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 75–91, 2005     

Random graphs containing few disjoint excluded minors

The Erd?s‐Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a ‘blocking’ set B of at most f(k) vertices such that the graph G – B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor‐closed class of graphs, as long as does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for , there is a set B of at most g(k) vertices such that G – B is in . In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763–775), we showed that, amongst all graphs on vertex set which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor‐closed graph class with 2‐connected excluded minors, as long as does not contain all fans (here a ‘fan’ is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on which contain at most k disjoint excluded minors for , all but an exponentially small proportion contain a set B of k vertices such that G – B is in . (This is not the case when contains all fans.) For a random graph R_n sampled uniformly from the graphs on with at most k disjoint excluded minors for , we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 240‐268, 2014     

A note on the production of matroid minors

The circuits containing some fixed element of a connected matroid (such a collection is called a port) provide a matroid generalization of the “path collections” of graphs. In this note we show how to translate forbidden minor theorems in matroid theory into results about ports — and we find that many theorems are strengthened by such translation. Those collections of sets which are “path collections” of graphs may then be characterized.     

Polynomial relations among principal minors of a -matrix

The image of the principal minor map for n×n-matrices is shown to be closed. In the 19th century, Nanson and Muir studied the implicitization problem of finding all relations among principal minors when n=4. We complete their partial results by constructing explicit polynomials of degree 12 that scheme-theoretically define this affine variety and also its projective closure in . The latter is the main component in the singular locus of the 2×2×2×2-hyperdeterminant.     

A note on determinants,minors and a boundary map

We give an explicit formula for the first non-trivial boundary map of the Akin–Buchsbaum–Weyman resolution (Schur functors and Schur complexes, Adv. Math 1982;44:207-278). The role of the Laplace expansion formula is emphasized.     

Blaschke structure for a special affine immersion

In this paper we determine a Blaschke structure for affine immersion of Euclidian and Hyperbolic type for plane equi-affine curve. In particular, we consider this structure in the case where the Ricci tensor of affine immersion is constant and give a necessary and sufficient condition for Ricci tensor to be constant.     

A note on the disconnection number

We present a simple way to obtain all graphs with a given disconnection number if we know all the graphs with smaller disconnection number. Using this method we answer a question of Sam B. Nadler, i.e. we prove that there exist precisely 26 continua with disconnection number four. Some known results concerning disconnection number are also obtained as simple corollaries. Further we give some estimates on the number of distinct continua with a fixed disconnection number which concerns a problem of Sam B. Nadler.     

切触黎曼浸入的极小性

切触黎曼流形,其殆复结构不一定是可积的,是CR几何中伪厄尔米特流形的一般情形.选取TWT联络作为切触黎曼流形上的联络,在CR情形下它就是TW联络.推广CR几何中的伪厄尔米特浸入得到切触黎曼几何中的切触黎曼浸入,可以证明任何切触黎曼浸入一定是极小的.     

A note on coloring sparse random graphs

Coja-Oghlan and Taraz [Amin Coja-Oghlan, Anusch Taraz, Exact and approximative algorithms for coloring , Random Structures and Algorithms 24 (3) (2004) 259-278] presented a graph coloring algorithm that has expected linear running time for random graphs with edge probability p satisfying np≤1.01. In this work, we develop their analysis by exploiting generating function techniques. We show that, in fact, their algorithm colors G_n,p with the minimal number of colors and has expected linear running time, provided that np≤1.33.     

On reconstruction of a matrix by its minors

In this paper, we reconstruct matrices from their minors, and give explicit formulas for the reconstruction of matrices of orders 2 × 3, 2 × 4, 2 × n, 3 × 6 and m × n. We also formulate the Plücker relations, which are the conditions of the existence of a matrix related to its given minors.     

A note on the DP-chromatic number of complete bipartite graphs

DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvo?ák and Postle. Several known bounds for the list chromatic number of a graph $G$, ${\chi }_{?}\left(G\right)$, also hold for the DP-chromatic number of $G$, ${\chi }_{DP}\left(G\right)$. On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that ${\chi }_{?}\left(K_{k,t}\right)=k+1$ if and only if $t\ge k^k$. We show that ${\chi }_{DP}\left(K_{k,t}\right)=k+1$ if $t\ge 1+(k^k∕k!)(log(k!)+1)$, and we show that ${\chi }_{DP}\left(K_{k,t}\right)<k+1$ if $t<k^k∕k!$.     

Maximal minors of a matrix with linear form entries

Let P be a matrix whose entries are homogeneous polynomials in n variables of degree one over an algebraically closed field. We show that the maximal minors, say m-minors, of P generate the linear space of homogeneous polynomials of degree m if P has the maximal rank m at every point of the affine n-space except the origin.     

A note on the periodic orbits and topological entropy of graph maps

This paper deals with the relationship between the periodic orbits of continuous maps on graphs and the topological entropy of the map. We show that the topological entropy of a graph map can be approximated by the entropy of its periodic orbits.