Surgery groups of the fundamental groups of hyperplane arrangement complements

Using a recent result of Bartels and Lück (The Borel conjecture for hyperbolic and CAT(0)-groups (preprint) \({{\tt arXiv:0901.0442v1}}\)) we deduce that the Farrell–Jones Fibered Isomorphism conjecture in \({L^{\langle -\infty \rangle}}\)-theory is true for any group which contains a finite index strongly poly-free normal subgroup, in particular, for the Artin full braid groups. As a consequence we explicitly compute the surgery groups of the Artin pure braid groups. This is obtained as a corollary to a computation of the surgery groups of a more general class of groups, namely for the fundamental group of the complement of any fiber-type hyperplane arrangement in \({{\mathbb C}^n}\).     

Curve graphs and Garside groups

We present a simple construction which associates to every Garside group a metric space, called the additional length graph, on which the group acts. These spaces share important features with curve graphs: they are \(\delta \)-hyperbolic, infinite, and typically locally infinite graphs. We conjecture that, apart from obvious counterexamples, additional length graphs have always infinite diameter. We prove this conjecture for the classical example of braid groups \((B_n,B_n^{+},\varDelta )\); moreover, in this framework, reducible and periodic braids act elliptically, and at least some pseudo-Anosov braids act loxodromically. We conjecture that for \(B_n\), the additional length graph is actually quasi-isometric to the curve graph of the n times punctured disk.     

A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture

The article shrinks the Δ = 6 hole that exists in the family of planar graphs which satisfy the total coloring conjecture. Let G be a planar graph. If ${v_n^k}$ represents the number of vertices of degree n which lie on k distinct 3-cycles, for ${n, k \in \mathbb{N}}$ , then the conjecture is true for planar graphs which satisfy ${v_5^4 +2(v_5^{5^+} +v_6^4) +3v_6^5 +4v_6^{6^+} < 24}$ .     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

Disjoint empty disks supported by a point set

For a planar point-set P, let D(P) be the minimum number of pairwise-disjoint empty disks such that each point in P lies on the boundary of some disk. Further define D(n) as the maximum of D(P) over all n-element point sets. Hosono and Urabe recently conjectured that ${D(n) = \lceil n/2 \rceil}$ . Here we show that ${D(n) \geq n/2 + n/236 - O(\sqrt{n})}$ and thereby disprove this conjecture.     

Homomorphism Bounds for Oriented Planar Graphs of Given Minimum Girth

We find necessary conditions for a digraph H to admit a homomorphism from every oriented planar graph of girth at least n, and use these to prove the existence of a planar graph of girth 6 and oriented chromatic number at least 7. We identify a ${\overleftrightarrow{K_4}}$ -free digraph of order 7 which admits a homomorphism from every oriented planar graph (here ${\overleftrightarrow{K_n}}$ means a digraph with n vertices and arcs in both directions between every distinct pair), and a ${\overleftrightarrow{K_3}}$ -free digraph of order 4 which admits a homomorphism from every oriented planar graph of girth at least 5.     

Homology Theory of Graphs

Higher homotopy of graphs has been defined in several articles. In Dochterman (Hom complexes and homotopy theory in the category of graphs. arXiv math/0605275 v2,28/09/2006, 2006), the authors asked for a companion homology theory. We define such a theory for the category of unoriented reflexive graphs; it exhibits a long exact sequence for a pair of graphs (G, A), satisfies an excision property and a Hurewicz theorem. This allows us to compute the top homology of the graphical n-spheres showing that the theory is not trivial and is able to detect n-dimensional holes in a graph. The long-term objective is to compare the homotopy of the topological and graphical spheres.     

On braid groups and right-angled Artin groups

In this article we prove a special case of a conjecture of A. Abrams and R. Ghrist about fundamental groups of certain aspherical spaces. Specifically, we show that the \(n\) -point braid group of a linear tree is a right-angled Artin group for each \(n\) .     

Using equivariant obstruction theory in combinatorial geometry

A significant group of problems coming from the realm of combinatorial geometry can be approached fruitfully through the use of Algebraic Topology. From the first such application to Kneser's problem in 1978 by Lovász [L. Lovász, Knester's conjecture, chromatic number of distance graphs on the sphere, Acta. Sci. Math (Szeged) 45 (1983) 317-323] through the solution of the Lovász conjecture [E. Babson, D. Kozlov, Proof of Lovasz conjecture, Annals of Mathematics (2) (2004), submitted for publication; C. Schultz, A short proof of for all n and a graph colouring theorem by Babson and Kozlov, 2005, arXiv: math.AT/0507346v2], many methods from Algebraic Topology have been developed. Specifically, it appears that the understanding of equivariant theories is of the most importance. The solution of many problems depends on the existence of an elegantly constructed equivariant map. A variety of results from algebraic topology were applied in solving these problems. The methods used ranged from well known theorems like Borsuk-Ulam and Dold theorem to the integer/ideal-valued index theories. Recently equivariant obstruction theory has provided answers where the previous methods failed. For example, in papers [R.T. ?ivaljevi?, Equipartitions of measures in R⁴, arXiv: math.0412483, Trans. Amer. Math. Soc., submitted for publication] and [P. Blagojevi?, A. Dimitrijevi? Blagojevi?, Topology of partition of measures by fans and the second obstruction, arXiv: math.CO/0402400, 2004] obstruction theory was used to prove the existence of different mass partitions. In this paper we extract the essence of the equivariant obstruction theory in order to obtain an effective general position map scheme for analyzing the problem of existence of equivariant maps. The fact that this scheme is useful is demonstrated in this paper with three applications:

(A)

a “half-page” proof of the Lovász conjecture due to Babson and Kozlov [E. Babson, D. Kozlov, Proof of Lovasz conjecture, Annals of Mathematics (2) (2004), submitted for publication] (one of two key ingredients is Schultz' map [C. Schultz, A short proof of for all n and a graph colouring theorem by Babson and Kozlov, 2005, arXiv: math.AT/0507346v2]),

(B)

a generalization of the result of V. Makeev [V.V. Makeev, Equipartitions of continuous mass distributions on the sphere an in the space, Zap. Nauchn. Sem. S.-Petersburg (POMI) 252 (1998) 187-196 (in Russian)] about the sphere S² measure partition by 3-planes (Section 3), and

(C)

the new (a,b,a), class of 3-fan 2-measures partitions (Section 3).

These three results, sorted by complexity, share the spirit of analyzing equivariant maps from spheres to complements of arrangements of subspaces.     

On diversity and stability of unit bases for the Euclidean metric

We prove the existence of a family Ω(n) of 2 ^c (where c is the cardinality of the continuum) subgraphs of the unit distance graph (E ⁿ , 1) of the Euclidean space E ⁿ , n ≥ 2, such that (a) for each graph G ? Ω(n), any homomorphism of G to (E ⁿ , 1) is an isometry of E ⁿ ; moreover, for each subgraph G ₀ of the graph G obtained from G by deleting less than c vertices, less than c stars, and less than c edges (we call such a subgraph reduced), any homomorphism of G ₀ to (E ⁿ , 1) is an isometry (of the set of the vertices of G ₀); (b) each graph G ? Ω(n) cannot be homomorphically mapped to any other graph of the family Ω(n), and the same is true for each reduced subgraph of G.     

Surface framed braids

In this paper we introduce the framed pure braid group on n strands of an oriented surface, a topological generalisation of the pure braid group P _n . We give different equivalent definitions for framed pure braid groups and we study exact sequences relating these groups with other generalisations of P _n , usually called surface pure braid groups. The notion of surface framed braid groups is also introduced.     

Topological Graph Polynomials in Colored Group Field Theory

In this paper, we analyze the open Feynman graphs of the Colored Group Field Theory introduced in Gurau (Colored group field theory, arXiv:0907.2582 [hep-th]). We define the boundary graph ${\mathcal{G}_{\partial}}In this paper, we analyze the open Feynman graphs of the Colored Group Field Theory introduced in Gurau (Colored group field theory, arXiv:0907.2582 [hep-th]). We define the boundary graph G_?{\mathcal{G}_{\partial}} of an open graph G{\mathcal{G}} and prove it is a cellular complex. Using this structure we generalize the topological (Bollobás–Riordan) Tutte polynomials associated to (ribbon) graphs to topological polynomials adapted to Colored Group Field Theory graphs in arbitrary dimension.     

A Hamada type characterization of the classical geometric designs

The dimension of a combinatorial design ${{\mathcal D}}$ over a finite field F = GF(q) was defined in (Tonchev, Des Codes Cryptogr 17:121–128, 1999) as the minimum dimension of a linear code over F that contains the blocks of ${{\mathcal D}}$ as supports of nonzero codewords. There it was proved that, for any prime power q and any integer n ≥ 2, the dimension over F of a design ${{\mathcal D}}$ that has the same parameters as the complement of a classical point-hyperplane design PG _n-1(n, q) or AG _n-1(n, q) is greater than or equal to n + 1, with equality if and only if ${{\mathcal D}}$ is isomorphic to the complement of the classical design. It is the aim of the present paper to generalize this Hamada type characterization of the classical point-hyperplane designs in terms of associated codes over F = GF(q) to a characterization of all classical geometric designs PG _d (n, q), where 1 ≤ d ≤ n ? 1, in terms of associated codes defined over some extension field E?=?GF(q ^t ) of F. In the affine case, we conjecture an analogous result and reduce this to a purely geometric conjecture concerning the embedding of simple designs with the parameters of AG _d (n, q) into PG(n, q). We settle this problem in the affirmative and thus obtain a Hamada type characterization of AG _d (n, q) for d = 1 and for d > (n ? 2)/2.     

Characterizations of the simple group {^2D_n(3)} by prime graph and spectrum

In this paper, we prove that there exists an infinite series of finite simple groups of Lie type with connected prime graphs which are uniquely determined by their prime graphs. More precisely, we show that every finite group G with the same prime graph as ${{}^2D_{n}(3)}$ , where n ≥ 5 is odd, is necessarily isomorphic to the group ${{}^2D_{n}(3)}$ . In fact, we give a positive answer to an open problem that arose in Zavarnitsine (Algebra Logic 45(4):220–231, 2006). As a consequence of our result, we obtain that the simple group ${{}^2D_n(3)}$ , where n is an odd number, is characterizable by its spectrum.     

Robust Tensegrity Polygons

A tensegrity polygon is a planar cable-strut tensegrity framework in which the cables form a convex polygon containing all vertices. The underlying edge-labeled graph $T=(V;C,S)$ T = ( V ; C , S ) , in which the cable edges form a Hamilton cycle, is an abstract tensegrity polygon. It is said to be robust if every convex realization of T as a tensegrity polygon has an equilibrium stress which is positive on the cables and negative on the struts, or equivalently, if every convex realization of T is infinitesimally rigid. We characterize the robust abstract tensegrity polygons on n vertices with $n-2$ n - 2 struts, answering a question of Roth and Whiteley (Trans Am Math Soc 265:419–446, 1981) and solving an open problem of Connelly (Recent progress in rigidity theory, 2008).     

Flat connections on configuration spaces and braid groups of surfaces

We construct an explicit bundle with flat connection on the configuration space of n points on a complex curve. This enables one to recover the ‘1-formality’ isomorphism between the Lie algebra of the prounipotent completion of the pure braid group of n   points on a surface and an explicitly presented Lie algebra, and to extend it to a morphism from the full braid group of the surface to the semidirect product of the associated group with the symmetric group _Sn$S_n$.     

Cycle Covers of Planar 2-Edge-Connected Graphs

A graph with n vertices is said to have a small cycle cover provided its edges can be covered with at most (2n ? 1)/3 cycles. Bondy [2] has conjectured that every 2-connected graph has a small cycle cover. In [3] Lai and Lai prove Bondy’s conjecture for plane triangulations. In [1] the author extends this result to all planar 3-connected graphs, by proving that they can be covered by at most (n + 1)/2 cycles. In this paper we show that Bondy’s conjecture holds for all planar 2-connected graphs. We also show that all planar 2-edge-connected graphs can be covered by at most (3n ? 3)/4 cycles and we show an infinite family of graphs for which this bound is attained.     

2-Arc-transitive cyclic covers of K n,n −nK 2

Du et al. (in J. Comb. Theory B 74:276–290, 1998 and J. Comb. Theory B 93:73–93, 2005), classified regular covers of complete graph whose fiber-preserving automorphism group acts 2-arc-transitively, and whose covering transformation group is either cyclic or isomorphic to $\mathbb{Z}_{p}^{2}$ or $\mathbb{Z}_{p}^{3}$ with p a prime. In this paper, a complete classification is achieved of all the regular covers of bipartite complete graphs minus a matching K _n,n ?nK ₂ with cyclic covering transformation groups, whose fiber-preserving automorphism groups act 2-arc-transitively.