Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number

Asteroidal Triple‐free (AT‐free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT‐free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long‐standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.     

The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices

Yao et al. (Discrete Appl Math 99 (2000), 245–249) proved that every strong tournament contains a vertex u such that every out‐arc of u is pancyclic and conjectured that every k‐strong tournament contains k such vertices. At present, it is known that this conjecture is true for k = 1, 2, 3 and not true for k?4. In this article, we obtain a sufficient and necessary condition for a 4‐strong tournament to contain exactly three out‐arc pancyclic vertices, which shows that a 4‐strong tournament contains at least four out‐arc pancyclic vertices except for a given class of tournaments. Furthermore, our proof yields a polynomial algorithm to decide if a 4‐strong tournament has exactly three out‐arc pancyclic vertices.     

Banach空间中关于有界集的同时远达问题的适定性

本文研究Banach空间中关于有界集的同时远达问题的适定性,在集合的Hausdorff距离下,证明了：对自反局部一致凸Banach空间中的闭有界集K,使所有关于K的同时远达问题是适定的紧凸子集A全体在紧凸子集全体中是Gδ型集．     

Sources and Sinks in Comparability Graphs

We prove that a subset S of vertices of a comparability graph G is a source set if and only if each vertex of S is a source and there is no odd induced path in G between two vertices of S. We also characterize pairs of subsets corresponding to sources and sinks, respectively. Finally, an application to interval graphs is obtained.     

The VC dimension of k‐uniform random hypergraphs

A set of vertices is shattered in a hypergraph if any of its subsets is obtained as the intersection of an edge with the set. The VC dimension is the size of the largest shattered subset. Under the binomial model of k‐uniform random hypergraphs, the threshold function for the VC dimension to be larger than a given integer is obtained. The same is done for the testing dimension, which is the largest integer d such that all sets of cardinality d are shattered. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

广义正则平面曲线的顶点

<正> 引言.四顶点定理.自印度加尔各答大学教授 Mukhopadhyaya 证明后,继而论之者颇多.Blaschke 证明:一正则卵形线若与任一圆之交点至多有四点时,则此卵形线至多有四顶点.另一人证明:一正则卵形线若与一圆有2n个交点时,则此卵形线至少有2n个顶点.Fog 及 Graustein 曾推广四顶点定理至简单闭曲线.Jackson 从研究二顶点曲线的特性出发,以研究四顶点曲线,指出了更广泛的四顶点曲线族.因不具二顶点曲线的特性就为四顶点曲线.以上这些曲线是指正则曲线,即曲线上的曲率不仅存     

Directed cycles with chords

Using a variation of Thomassen's admissible triples technique, we give an alternative proof that every strongly 2‐arc‐connected directed graph with two or more vertices contains a directed cycle that has at least two chords, while at the same time establishing a more general result. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:17–28, 1999     

Almost Chebyshev set with respect to bounded subsets

The uniqueness and existence of restricted Chebyshev center with respect to arbitrary subset are investigated. The concept of almost Chebyshev sets with respect to bounded subsets is introduced. It is proved that each closed subset in a reflexive locally uniformly convex (uniformly convex, respectively) Banach space is an almost Chebyshev subset with respect to compact convex subsets (bounded convex subsets and bounded subsets, respectively). Project supported by the National Natural Science Foundation of China, Natural Science Foundation of Zhejiang Province, and the State Major Key Project for Basic Researchers of China.     

Banach空间中远达和同时远达问题的适定性

本文研究Ｂａｎａｃｈ空间Ｘ中远达和同时远达问题的适定性,在集合的Ｈａｕｓ－ ｄｏｒｆｆ距离下,对Ｘ中的闭凸子集Ｄ和相对弱紧的有界闭子集Ｋ,证明了下述结果： 若Ｄ关于Ｋ严格凸和有Ｋａｄｅｃ性质,则Ｄ中所有使远达问题 ｍａｘ｛ｘ,Ｋ｝是适定的 点ｘ全体在Ｄ中是Ｇδ型集．作为应用,得到了同时远达问题适定性的类似结果．     

The hyperspace of hereditarily decomposable subcontinua of a cube is the Hurewicz set

The hyperspaces of hereditarily decomposable continua and of decomposable subcontinua without pseudoarcs in the cube of dimension greater than 2 are homeomorphic to the Hurewicz set of all nonempty countable closed subsets of the unit interval [0,1]. Moreover, in such a cube, all indecomposable subcontinua form a homotopy dense subset of the hyperspace of (nonempty) subcontinua.     

Quasi-convex subsets in Alexandrov spaces with lower curvature bound

We introduce quasi-convex subsets in Alexandrov spaces with lower curvature bound, which include not only all closed convex subsets without boundary but also all extremal subsets. Moreover, we explore several essential properties of such kind of subsets including a generalized Liberman theorem. It turns out that the quasi-convex subset is a nice and fundamental concept to illustrate the similarities and differences between Riemannian manifolds and Alexandrov spaces with lower curvature bound.     

D.C. Representability of closed sets in reflexive Banach spaces and applications to optimization problems

A closed subsetM of a Hausdorff locally convex space is called d.c. representable if there are an extended-real valued lsc convex functionf and a continuous convex functionh such that $$M = \{ x \in X:f(x) - h(x) \leqslant 0\} .$$ Using the existence of a locally uniformly convex norm, we prove that any closed subset in a reflexive Banach space is d.c. representable. For d.c. representable subsets, we define an index of nonconvexity, which can be regarded as an indicator for the degree of nonconvexity. In fact, we show that a convex closed subset is weakly closed when it has a finite index of nonconvexity, and optimization problems on closed subsets with a low index of nonconvexity are less difficult from the viewpoint of computation.     

Extension of Arrow's theorem to symmetric sets of tournaments

Arrow's impossibility theorem [K.J. Arrow, Social Choice and Individual Values, Wiley, New York, NY, 1951] shows that the set of acyclic tournaments is not closed to non-dictatorial Boolean aggregation. In this paper we extend the notion of aggregation to general tournaments and we show that for tournaments with four vertices or more any proper symmetric (closed to vertex permutations) subset cannot be closed to non-dictatorial monotone aggregation and to non-neutral aggregation. We also demonstrate a proper subset of tournaments that is closed to parity aggregation for an arbitrarily large number of vertices. This proves a conjecture of Kalai [Social choice without rationality, Reviewed NAJ Economics 3(4)] for the non-neutral and the non-dictatorial and monotone cases and gives a counter example for the general case.     

A dual algorithm for the minimum covering weighted ball problem in {\mathbb{R}^n}

The nonlinear convex programming problem of finding the minimum covering weighted ball of a given finite set of points in ${\mathbb{R}^n}$ is solved by generating a finite sequence of subsets of the points and by finding the minimum covering weighted ball of each subset in the sequence until all points are covered. Each subset has at most n + 1 points and is affinely independent. The radii of the covering weighted balls are strictly increasing. The minimum covering weighted ball of each subset is found by using a directional search along either a ray or a circular arc, starting at the solution to the previous subset. The step size is computed explicitly at each iteration.     

Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

Density of the circular chromatic numbers of series‐parallel graphs

In this paper we show that every simple cubic graph on n vertices has a set of at least ? n/4 ? disjoint 2‐edge paths and that this bound is sharp. Our proof provides a polynomial time algorithm for finding such a set in a simple cubic graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 57–79, 2003     

Nilpotent and soluble groups with respect to a homomorph

For an excellent ring Awhose real spectrum satisfies some connectedness condition, we give a sensible notion of real analytic component for a Zariski closed subset of Specr A(such a closed subset will also be called a locally Nash set).Indeed we show that the locally Nash sets are the closed subsets of a noetherian topology on an abstract new space G which we introduce.This generalizes the geometric notion of global real analytic component when Ais the ring of global Nash functions on an affine Nash manifold.     

Hamel‐isomorphic images of the unit ball

In this article we consider linear isomorphisms over the field of rational numbers between the linear spaces ?² and ?. We prove that if f is such an isomorphism, then the image by f of the unit disk is a strictly nonmeasurable subset of the real line, which has different properties than classical non‐measurable subsets of reals. We shall also consider the question whether all images of bounded measurable subsets of the plane via a such mapping are non‐measurable (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Partitioning series-parallel multigraphs into υ*-excluding edge covers

We prove that, for any given vertex υ* in a series-parallel graph G, its edge set can be partitioned into k = min{κ'(G) + 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except for υ*, where δ(G) is the minimum degree of G and κ'(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

The capacitated max k-cut problem

We consider a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets. Each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that maximizes the sum of edge weights across all pairs of vertices that lie in different subsets. We describe a local-search algorithm that obtains a solution with value no smaller than 1 − 1/k of the optimal solution value. This improves a previous bound of 1/2 for the max k-cut problem with fixed, though possibly different, sizes of subsets. We thank an anonymous referee for extensive and constructive comments. The first and second authors are grateful for the support provided by the Natural Sciences and Engineering Research Council of Canada.