Geometry of regular modules over canonical algebras

We classify canonical algebras such that for every dimension vector of a regular module the corresponding module variety is normal (respectively, a complete intersection). We also prove that for the dimension vectors of regular modules normality is equivalent to irreducibility.

     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

Planar graphs: Random walks and bipartiteness testing

We initiates the study of property testing in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time, improving on the previous bound of for graphs on n vertices. The constant‐time testability was only known for planar graphs with bounded degree. Our algorithm is based on random walks. Since planar graphs have good separators, that is, bad expansion, our analysis diverges from standard techniques that involve the fast convergence of random walks on expanders. We reduce the problem to the task of detecting an odd‐parity cycle in a multigraph induced by constant‐length cycles. We iteratively reduce the length of cycles while preserving the detection probability, until the multigraph collapses to a collection of easily discoverable self‐loops. Our approach extends to arbitrary minor‐free graphs. We also believe that our techniques will find applications to testing other properties in arbitrary minor‐free graphs.     

Decomposition of cubic graphs with cyclic connectivity 5

Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components $G_1$ and $G_2$. We prove that each component $G_i$ can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless $G_i$ is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1988.     

Proximity and remoteness in triangle-free and C4-free graphs in terms of order and minimum degree

Let G be a finite, connected graph. The average distance of a vertex v of G is the arithmetic mean of the distances from v to all other vertices of G. The remoteness $\rho (G)$ and the proximity $\pi (G)$ of G are the maximum and the minimum of the average distances of the vertices of G. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of $C_4$-free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible.     

Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets

An $(m,n)$-colored-mixed graph $G=(V,A_1,A_2,\cdots ,A_m,E_1,E_2,\cdots ,E_n)$ is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an $(m,n)$-colored-mixed graph G to another $(m,n)$-colored-mixed graph H is a morphism $\phi :V(G)\to V(H)$ such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An $(m,n)$-colored-mixed graph T is said to be $P_g^{(m,n)}$-universal if every graph in $P_g^{(m,n)}$ (the planar $(m,n)$-colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar $P_g^{(m,n)}$-universal graphs do not exist for $2m+n\ge 3$ (and any value of g) and find a minimal (in the number vertices) planar $P_g^{(m,n)}$-universal graphs in the other cases.     

Enumerative problems for arborescences and monotone paths on polytope graphs

Every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. From the resulting directed graph one can define a notion of $f$-arborescence and $f$-monotone path on $P$, as well as a natural graph structure on the vertex set of $f$-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets.