共查询到20条相似文献,搜索用时 46 毫秒
1.
S is a local maximum stable set of a graph G, and we write S∈Ψ(G), if the set S is a maximum stable set of the subgraph induced by S∪N(S), where N(S) is the neighborhood of S. In Levit and Mandrescu (2002) [5] we have proved that Ψ(G) is a greedoid for every forest G. The cases of bipartite graphs and triangle-free graphs were analyzed in Levit and Mandrescu (2003) [6] and Levit and Mandrescu (2007) [7] respectively.In this paper we give necessary and sufficient conditions for Ψ(G) to form a greedoid, where G is:
- (a)
- the disjoint union of a family of graphs;
- (b)
- the Zykov sum of a family of graphs;
- (c)
- the corona X°{H1,H2,…,Hn} obtained by joining each vertex x of a graph X to all the vertices of a graph Hx.
2.
3.
In this paper, we show that, for every locally compact abelian group G, the following statements are equivalent:
- (i)
- G contains no sequence such that {0}∪{±xn∣n∈N} is infinite and quasi-convex in G, and xn?0;
- (ii)
- one of the subgroups {g∈G∣2g=0} or {g∈G∣3g=0} is open in G;
- (iii)
- G contains an open compact subgroup of the form or for some cardinal κ.
4.
Dikran Dikranjan 《Topology and its Applications》2007,154(7):1321-1340
We study CLP-compact spaces (every cover consisting of clopen sets has a finite subcover) and CLP-compact topological groups. In particular, we extend a theorem on CLP-compactness of products from [J. Steprāns, A. Šostak, Restricted compactness properties and their preservation under products, Topology Appl. 101 (3) (2000) 213-229] and we offer various criteria for CLP-compactness for spaces and topological groups, that work particularly well for precompact groups. This allows us to show that arbitrary products of CLP-compact pseudocompact groups are CLP-compact. For every natural n we construct:
- (i)
- a totally disconnected, n-dimensional, pseudocompact CLP-compact group; and
- (ii)
- a hereditarily disconnected, n-dimensional, totally minimal, CLP-compact group that can be chosen to be either separable metrizable or pseudocompact (a Hausdorff group G is totally minimal when all continuous surjective homomorphisms G→H, with a Hausdorff group H, are open).
5.
Theorem A ℵ1?.
There is a Boolean algebra B with the following properties:
- (1)
- B is thin-tall, and
- (2)
- B is downward-categorical.
6.
Maria Chudnovsky Alexandra FradkinPaul Seymour 《Journal of Combinatorial Theory, Series B》2012,102(1):93-101
A (loopless) digraph H is strongly immersed in a digraph G if the vertices of H are mapped to distinct vertices of G, and the edges of H are mapped to directed paths joining the corresponding pairs of vertices of G, in such a way that the paths used are pairwise edge-disjoint, and do not pass through vertices of G that are images of vertices of H. A digraph has cutwidth at most k if its vertices can be ordered {v1,…,vn} in such a way that for each j, there are at most k edges uv such that u∈{v1,…,vj−1} and v∈{vj,…,vn}.We prove that for every set S of tournaments, the following are equivalent:
- •
- there is a digraph H such that H cannot be strongly immersed in any member of S,
- •
- there exists k such that every member of S has cutwidth at most k,
- •
- there exists k such that every vertex of every member of S belongs to at most k edge-disjoint directed cycles.
7.
Gabriel Padilla 《Topology and its Applications》2007,154(15):2764-2770
A classical result says that a free action of the circle S1 on a topological space X is geometrically classified by the orbit space B and by a cohomological class e∈H2(B,Z), the Euler class. When the action is not free we have a difficult open question:
- (Π)
- “Is the space X determined by the orbit space B and the Euler class?”
- •
- the intersection cohomology of X,
- •
- the real homotopy type of X.
8.
Vera Toni? 《Topology and its Applications》2010,157(3):674-691
We prove a generalization of the Edwards-Walsh Resolution Theorem:
Theorem.
Let G be an abelian group withPG=P, where. Letn∈Nand let K be a connected CW-complex withπn(K)≅G,πk(K)≅0for0?k<n. Then for every compact metrizable space X with XτK (i.e., with K an absolute extensor for X), there exists a compact metrizable space Z and a surjective mapπ:Z→Xsuch that
- (a)
- π is cell-like,
- (b)
- dimZ?n, and
- (c)
- ZτK.
9.
J. Higes 《Topology and its Applications》2010,157(17):2635-2645
In this paper we study two problems concerning Assouad-Nagata dimension:
- (1)
- Is there a metric space of positive asymptotic Assouad-Nagata dimension such that all of its asymptotic cones are of Assouad-Nagata dimension zero? (Dydak and Higes, 2008 [11, Question 4.5]).
- (2)
- Suppose G is a locally finite group with a proper left invariant metric dG. If dimAN(G,dG)>0, is dimAN(G,dG) infinite? (Brodskiy et al., preprint [6, Problem 5.3]).
10.
Klaus Meer 《Discrete Mathematics》2009,309(4):843-851
We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function fG of a graph G on n vertices. Our results are as follows:
- -
- for graphs of bounded tree-width there is an OBDD of size O(logn) for fG that uses encodings of size O(logn) for the vertices;
- -
- for graphs of bounded clique-width there is an OBDD of size O(n) for fG that uses encodings of size O(n) for the vertices;
- -
- for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for fG that uses encodings of size O(logn) for the vertices;
- -
- for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for fG that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel [R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.
11.
It was shown in Bíró et al. (2001) [7] that every cyclic subgroup C of the circle group T admits a characterizing sequence (un) of integers in the sense that unx→0 for some x∈T iff x∈C. More generally, for a subgroup H of a topological (abelian) group G one can define:
- (a)
- g(H) to be the set of all elements x of G such that unx→0 in G for all sequences (un) of integers such that unh→0 in G for all h∈H;
- (b)
- H to be g-closed if H=g(H).
12.
Linus Kramer 《Advances in Mathematics》2005,193(1):142-173
Let G be a connected semisimple Lie group with at least one absolutely simple factor S such that and let Γ be a uniform lattice in G.
- (a)
- If CH holds, then Γ has a unique asymptotic cone up to homeomorphism.
- (b)
- If CH fails, then Γ has 22ω asymptotic cones up to homeomorphism.
13.
Let G be a Hausdorff topological group. It is shown that there is a class C of subspaces of G, containing all (but not only) precompact subsets of G, for which the following result holds:Suppose that for every real-valued discontinuous function on G there is a set A∈C such that the restriction mapping f|A has no continuous extension to G; then the following are equivalent:
- (i)
- the left and right uniform structures of G are equivalent,
- (ii)
- every left uniformly continuous bounded real-valued function on G is right uniformly continuous,
- (iii)
- for every countable set A⊂G and every neighborhood V of the unit e of G, there is a neighborhood U of e in G such that AU⊂VA.
14.
Edith Hemaspaandra Lane A. Hemaspaandra Stanis?aw P. Radziszowski 《Discrete Applied Mathematics》2007,155(2):103-118
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:
- (1)
- , , , and .
- (2)
- For all k?2, and .
- (3)
- For all k?2, .
- (4)
- .
- (5)
- For all k?2, .
15.
16.
Christopher Mouron 《Topology and its Applications》2009,156(3):558-576
Suppose that is a collection of disjoint subcontinua of continuum X such that limi→∞dH(Yi,X)=0 where dH is the Hausdorff metric. Then the following are true:
- (1)
- X is non-Suslinean.
- (2)
- If each Yi is chainable and X is finitely cyclic, then X is indecomposable or the union of 2 indecomposable subcontinua.
- (3)
- If X is G-like, then X is indecomposable.
- (4)
- If all lie in the same ray and X is finitely cyclic, then X is indecomposable.
17.
Adam J. Prze?dziecki 《Advances in Mathematics》2010,225(4):1893-1913
We construct a functor F:Graphs→Groups which is faithful and “almost” full, in the sense that every nontrivial group homomorphism FX→FY is a composition of an inner automorphism of FY and a homomorphism of the form Ff, for a unique map of graphs f:X→Y. When F is composed with the Eilenberg-Mac Lane space construction K(FX,1) we obtain an embedding of the category of graphs into the unpointed homotopy category which is full up to null-homotopic maps.We provide several applications of this construction to localizations (i.e. idempotent functors); we show that the questions:
- (1)
- Is every orthogonality class reflective?
- (2)
- Is every orthogonality class a small-orthogonality class?
18.
19.
Horst Herrlich 《Topology and its Applications》2011,158(17):2279-2286
Within the framework of Zermelo-Fraenkel set theory ZF, we investigate the set-theoretical strength of the following statements:
- (1)
- For every family(Ai)i∈Iof sets there exists a family(Ti)i∈Isuch that for everyi∈I(Ai,Ti)is a compactT2space.
- (2)
- For every family(Ai)i∈Iof sets there exists a family(Ti)i∈Isuch that for everyi∈I(Ai,Ti)is a compact, scattered, T2space.
- (3)
- For every set X, every compactR1topology (itsT0-reflection isT2) on X can be enlarged to a compactT2topology.
- (a)
- (1) implies every infinite set can be split into two infinite sets.
- (b)
- (2) iff AC.
- (c)
- (3) and “there exists a free ultrafilter” iff AC.
20.
The main results of the paper are:
- (1)
- If X is metrizable but not locally compact topological space, then Ck(X) contains a closed copy of S2, and hence does not have the property AP;
- (2)
- For any zero-dimensional Polish X, the space Ck(X,2) is sequential if and only if X is either locally compact or the derived set X′ is compact; and
- (3)
- All spaces of the form Ck(X,2), where X is a non-locally compact Polish space whose derived set is compact, are homeomorphic, and have the topology determined by an increasing sequence of Cantor subspaces, the nth one nowhere dense in the (n+1)st.