On the OBDD size for graphs of bounded tree- and clique-width

We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function f_G 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 f_G 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 f_G 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 f_G 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 f_G 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.

     

Left and right uniform structures on functionally balanced groups

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.

As a consequence, it is proved that items (i), (ii) and (iii) are equivalent for every inframetrizable group. These results generalize earlier ones established by Itzkowitz, Rothman, Strassberg and Wu, by Milnes and by Pestov for locally compact groups, by Protasov for almost metrizable groups, and by Troallic for groups that are quasi-k-spaces.     

Graph operations that are good for greedoids

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°{H₁,H₂,…,H_n} obtained by joining each vertex x of a graph X to all the vertices of a graph H_x.

     

Locally compact abelian groups admitting non-trivial quasi-convex null sequences

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}∪{±x_n∣n∈N} is infinite and quasi-convex in G, and x_n?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 κ.

     

Colouring graphs with bounded generalized colouring number

Given a graph G and a positive integer p, χ_p(G) is the minimum number of colours needed to colour the vertices of G so that for any i≤p, any subgraph H of G of tree-depth i gets at least i colours. This paper proves an upper bound for χ_p(G) in terms of the k-colouring number of G for k=2^p−2. Conversely, for each integer k, we also prove an upper bound for in terms of χ_k+2(G). As a consequence, for a class K of graphs, the following two statements are equivalent:

(a)

For every positive integer p, χ_p(G) is bounded by a constant for all G∈K.

(b)

For every positive integer k, is bounded by a constant for all G∈K.

It was proved by Nešet?il and Ossona de Mendez that (a) is equivalent to the following:

(c)

For every positive integer q, ∇_q(G) (the greatest reduced average density of G with rank q) is bounded by a constant for all G∈K.

Therefore (b) and (c) are also equivalent. We shall give a direct proof of this equivalence, by introducing ∇_q−(1/2)(G) and by showing that there is a function F_k such that . This gives an alternate proof of the equivalence of (a) and (c).     

Extending compact topologies to compact Hausdorff topologies in ZF

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 compactT₂space.

(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, T₂space.

(3)

For every set X, every compactR₁topology (itsT₀-reflection isT₂) on X can be enlarged to a compactT₂topology.

We show:

(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.

We also show that if the topology of certain compact T₁ spaces can be enlarged to a compact T₂ topology then (1) holds true. But in general, compact T₁ topologies do not extend to compact T₂ ones.     

Extreme points of Banach lattices related to conditional expectations

Let (X,F,μ) be a complete probability space, B a sub-σ-algebra, and Φ the probabilistic conditional expectation operator determined by B. Let K be the Banach lattice {f∈L¹(X,F,μ):‖Φ(|f|)_‖∞<∞} with the norm ‖f‖=‖Φ(|f|)_‖∞. We prove the following theorems:

(1)

The closed unit ball of K contains an extreme point if and only if there is a localizing set E for B such that supp(Φ(χE))=X.

(2)

Suppose that there is n∈N such that f?nΦ(f) for all positive f in L^∞(X,F,μ). Then K has the uniformly λ-property and every element f in the complex K with is a convex combination of at most 2n extreme points in the closed unit ball of K.

     

Topological graph dimension

In the invited chapter Discrete Spatial Models of the book Handbook of Spatial Logics, we have introduced the concept of dimension for graphs, which is inspired by Evako’s idea of dimension of graphs [A.V. Evako, R. Kopperman, Y.V. Mukhin, Dimensional properties of graphs and digital spaces, J. Math. Imaging Vision 6 (1996) 109-119]. Our definition is analogous to that of (small inductive) dimension in topology. Besides the expected properties of isomorphism-invariance and monotonicity with respect to subgraph inclusion, it has the following distinctive features:

•

Local aspect. That is, dimension at a vertex is basic, and the dimension of a graph is obtained as the sup over its vertices.

•

Dimension of a strong product G×H is dim(G)+dim(H) (for non-empty graphs G,H).

In this paper we present a short account of the basic theory, with several new applications and results.     

Inversion arrangements and Bruhat intervals

Let W be a finite Coxeter group. For a given w∈W, the following assertion may or may not be satisfied:

(?)

The principal Bruhat order ideal of w contains as many elements as there are regions in the inversion hyperplane arrangement of w.

We present a type independent combinatorial criterion which characterises the elements w∈W that satisfy (?). A couple of immediate consequences are derived:

(1)

The criterion only involves the order ideal of w as an abstract poset. In this sense, (?) is a poset-theoretic property.

(2)

For W of type A, another characterisation of (?), in terms of pattern avoidance, was previously given in collaboration with Linusson, Shareshian and Sjöstrand. We obtain a short and simple proof of that result.

(3)

If W is a Weyl group and the Schubert variety indexed by w∈W is rationally smooth, then w satisfies (?).

     

Unprovability threshold for the planar graph minor theorem

This note is part of the implementation of a programme in foundations of mathematics to find exact threshold versions of all mathematical unprovability results known so far, a programme initiated by Weiermann. Here we find the exact versions of unprovability of the finite graph minor theorem with growth rate condition restricted to planar graphs, connected planar graphs and graphs embeddable into a given surface, assuming an unproved conjecture (*): ‘there is a number a>0 such that for all k≥3, and all n≥1, the proportion of connected graphs among unlabelled planar graphs of size n omitting the k-element circle as minor is greater than a’. Let γ be the unlabelled planar growth constant (27.2269≤γ<30.061). Let P(c) be the following first-order arithmetical statement with real parameter c: “for every K there is N such that whenever G₁,G₂,…,G_N are unlabelled planar graphs with |G_i|<K+c⋅log₂i then for some i<j≤N, G_i is isomorphic to a minor of G_j”. Then

1.

for every , P(c) is provable in IΔ₀+exp;

2.

for every , P(c) is unprovable in .

We also give proofs of some upper and lower bounds for unprovability thresholds in the general case of the finite graph minor theorem.     

An “almost” full embedding of the category of graphs into the category of groups

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?

have the same answers in the category of groups as in the category of graphs. In other words they depend on set theory: (1) is equivalent to weak Vopěnka's principle and (2) to Vopěnka's principle. Additionally, the second question, considered in the homotopy category, is also equivalent to Vopěnka's principle.     

Extraordinary dimension of maps

We consider the extraordinary dimension dimL introduced recently by Shchepin [E.V. Shchepin, Arithmetic of dimension theory, Russian Math. Surveys 53 (5) (1998) 975-1069]. If L is a CW-complex and X a metrizable space, then dimLX is the smallest number n such that ΣnL is an absolute extensor for X, where ΣnL is the nth suspension of L. We also write dimLf?n, where is a given map, provided dimLf⁻¹(y)?n for every y∈Y. The following result is established: Supposeis a perfect surjection between metrizable spaces, Y a C-space and L a countable CW-complex. Then conditions (1)-(3) below are equivalent:

(1)

dimLf?n;

(2)

There exists a dense andGδsubsetGofC(X,In)with the source limitation topology such thatdimL(f×g)=0for everyg∈G;

(3)

There exists a mapis such thatdimL(f×g)=0;If, in addition, X is compact, then each of the above three conditions is equivalent to the following one;

(4)

There exists anFσsetA⊂Xsuch thatdimLA?n−1and the restriction mapf|(X?A)is of dimensiondimf|(X?A)?0.

     

Norm continuity of weakly continuous mappings into Banach spaces

Let T be the class of Banach spaces E for which every weakly continuous mapping from an α-favorable space to E is norm continuous at the points of a dense subset. We show that:

•

T contains all weakly Lindelöf Banach spaces;

•

l^∞∉T, which brings clarity to a concern expressed by Haydon ([R. Haydon, Baire trees, bad norms and the Namioka property, Mathematika 42 (1995) 30-42], pp. 30-31) about the need of additional set-theoretical assumptions for this conclusion. Also, (l^∞/c₀)∉T.

•

T is stable under weak homeomorphisms;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is densely norm continuous;

•

E∈T iff every quasi-continuous mapping from a complete metric space to (E,weak) is weakly continuous at some point.

     

Bockstein basis and resolution theorems in extension theory

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.

     

Structural analysis of a fractional matching problem

Mixed Software Programming refers to a novel software development paradigm resulting from efforts to combine two different programming approaches: Solo Programming and Pair Programming. Solo Programming refers to the traditional practice of assigning a single developer to develop a software module and Pair Programming refers to a relatively new approach where two developers work simultaneously on developing a module. In Mixed Programming, given a set of modules to be developed, a chosen subset of modules may be developed using Solo Programming and the remaining modules using Pair Programming.Motivated by applications in Mixed Software Programming, we consider the following generalization of classical fractional 1-matching problem: Given an undirected simple graph G=(V;E), and a positive number F, find values for x_e,e∈E, satisfying the following:

1.

.

2.

, where δ(i)={e∈E:e=(i,j)},i∈V.

3.

Maximize {2∑_e∈Ex_e−F|{i∈V:∑_e∈δ(i)x_e=1}|}.

We show that this problem is solvable in strongly polynomial time. Our primary focus in this paper is on obtaining the structure of the optimal solution for an arbitrary instance of the problem.