Publikationen von Gábor Braun

Publikationen (auf Englisch)

  1. Gábor Braun and Sebastian Pokutta, Rigid abelian groups and the probabilistic method, Contemporary Mathematics 576 17–30 doi:10.1090/conm/576/11342 arXiv:1107.2325

    The construction of torsion-free abelian groups with prescribed endomorphism rings starting with Corner’s seminal work is a well-studied subject in the theory of abelian groups. Usually these construction work by adding elements from a (topological) completion in order to get rid of (kill) unwanted homomorphisms. The critical part is to actually prove that every unwanted homomorphism can be killed by adding a suitable element. We will demonstrate that some of those constructions can be significantly simplified by choosing the elements at random. As a result, the endomorphism ring will be almost surely prescribed, i.e., with probability one.

    2000 Mathematics Subject Classification: Primary:20K20, 20K15, 20K30, 05D40; Secondary:60B15

    Keywords: random construction; abelian groups with prescribed endomorphisms; probabilistic method.

  2. Gábor Braun and Sebastian Pokutta, An algebraic approach to symmetric extended formulations, Intern. Symp. on Combinatorial Optimization (ISCO 2012), Lecture Notes in Computer Science 7422 141–152 doi:10.1007/978-3-642-32147-4_14 arXiv:1206.6318

    Extended formulation is an important tool to obtain compact formulations opolytopes by representing them as projections of higher dimensional ones. It is an importanquestion whether a polytope admits a compact extended formulation, i.e., one of polynomiasize. For the case of symmetric extended formulations (i.e., preserving the symmetries of thpolytope) Yannakakis established a powerful technique to derive lower bounds and rule oucompact formulations. We rephrase the technique of Yannakakis in a group-theoretic frameworkThis provides a different perspective on symmetric extensions and considerably simplifies severalower bound constructions.

    2000 Mathematics Subject Classification: Primary:68Q17; Secondary:90C05, 52B15

    Keywords: symmetric extended formulation; lower bound; algebraic method.

  3. Gábor Braun, Samuel Fiorini, Sebastian Pokutta and David Steurer, Approximation Limits of Linear Programs (Beyond Hierarchies), 53rd IEEE Symp. on Foundations of Computer Science (FOCS 2012), 480–489 doi:10.1109/FOCS.2012.10 arXiv:1204.0957

    We develop a framework for unconditional approximation limits of any polynomial-size linear program from lower bounds on the nonnegative ranks of matrices. Using our framework, we prove that O(n^{1/2−ε})-approximations for CLIQUE (with a certain encoding) require linear programs of size 2^{n^{Ω(ε)}}. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs. Our main technical ingredient is a quantitative improvement of Razborov’s rectangle corruption lemma (1992) for the high error regime, which gives strong lower bounds on the non-negative rank of certain perturbations of the unique disjointness matrix.

    2000 Mathematics Subject Classification: Primary:52B15; Secondary:52B05, 20B30

    Keywords: approximate extended formulation; cut polytope; communication complexity; set non-disjointness problem; rectangle corruption lemma.

  4. Gábor Braun and Lutz Strüngmann, Breaking up finite automata presentable torsion-free abelian groups, IJAC no. 8, 1463—1472 doi:10.1142/S0218196711006625

    We show that every torsion-free group representable by a finite automaton is an extension of a finite-rank free group by a direct sum of finitely many Prüfer groups. This builds on a large extent on Tsankov's proof that the group of rational numbers is not representable by a finite automaton.

    2000 Mathematics Subject Classification: Primary:20K15; Secondary:03D05, 20K35, 68R15

    Keywords: FA-presentable abelian groups; automatic structures; additive combinatorics.

  5. Gábor Braun and Sebastian Pokutta, Random half-integer polytopes, Operations Research Letters 39 no. 3, 204—207
    2000 Mathematics Subject Classification: Primary:60C05; Secondary:90C10, 90C27, 90C57
  6. Gábor Braun and Jan Trlifaj, Strong submodules of almost projective modules, Pacific Journal of Mathematics 254 no. 1, 73–87

    The structure of almost projective modules can be better understood in case the following Condition (P) holds: ‘The union of each countable pure chain of projective modules is projective.’ We prove this condition, and its generalization to pure–projective modules, for all countable rings using the new notion of a strong submodule of the union. However, we also show that Condition (P) fails for all Prüfer domains of finite character with uncountable spectrum; in particular, for the polynomial ring K[x] where K is an uncountable field. Moreover, one can even prescribe the Γ–invariant of the union. Our results generalize earlier work of Hill, and complement recent papers by Macías–Díaz, Fuchs, and Rangaswamy.

    2000 Mathematics Subject Classification: Primary:16D40, 13C10; Secondary:03E75, 13F05, 13G05, 16P70

    Keywords: almost projective module; pure chain; strong submodule; Γ–invariant; Prüfer domain.

  7. Gábor Braun and András Némethi, Surgery formulas for Seiberg–Witten invariants of negative definite plumbed 3-manifolds, Journal für die reine und angewandte Mathematik no. 638, 189–208 doi:10.1515/CRELLE.2010.007 arXiv:0704.3145

    We provide a surgery formula for the Seiberg–Witten invariants of negative definite plumbed rational homology 3-spheres. The surgery is deleting an arbitrary vertex of the plumbing graph. The formula is additive in nature: the Seiberg–Witten invariant for a c spinorial structure is the sum of correction terms plus the Seiberg–Witten invariants for the restricted c spinorial structure of the manifolds plumbed using the components of the deleted graph. This formula was conjectured by the second author as an analogue of Okuma's additivity formula for splice-quotient singularities. As a by-product, this proves the Seiberg–Witten invariant conjecture for splice-quotient singularities.

    2000 Mathematics Subject Classification: Primary:57R57, 57M27; Secondary:32S05, 32S25, 32S45, 32C35

    Keywords: isolated surface singularity; plumbed 3-manifold; surgery formula for Seiberg–Witten invariants; rational homology sphere; splice-quotient singularity; Seiberg–Witten invariant conjecture.

  8. Gábor Braun and Sebastian Pokutta, Rank of random half-integral polytopes (extended abstract), ISCO 2010 - International Symposium on Combinatorial Optimization, Electronic Notes in Discrete Mathematics 36 415–422 doi:10.1016/j.endm.2010.05.053

    We will show that random half-integral polytopes contain certain sets with high probability, the sets of k-tuples with entries in {0, 1/2 , 1}, and exactly one entry equal to 1/2. We precisely determine the threshold number k for which the phase transition occurs. Using these random polytopes we show that establishing integer-infeasibility takes Ω(log n/ log log n) rounds of (almost) any cutting-plane procedure with high probability whenever the number of vertices is θ(3^n). As a corollary, a relationship between the number of vertices and the rank of the polytope with respect to (almost) any cutting-plane procedure follows.

    2000 Mathematics Subject Classification: Primary:60C05; Secondary:90C10, 90C27, 90C57

    Keywords: random 0-1 polytopes; cutting-plane procedure; integer infeasibility.

  9. Rüdiger Göbel and Gábor Braun, Splitting kernels into small summands, Israel Journal of Mathematics accepted doi:10.1007/s11856-011-0121-6

    Let λ be a regular cardinal. An epimorphism between abelian groups is λ-pure if it is projective with respect to abelian groups of size less than λ. We show that every cotorsion group have λ-pure projective dimension greater than 1 if and only if λ is smaller than the torsion-free part of the group. (For larger λ, the groups are λ-pure projective.) This is related to a (hard) problem of Neeman in module theory about writing modules as factors of direct sums of small modules.

    2000 Mathematics Subject Classification: Primary:20K25; Secondary:20K21, 20K99

    Keywords: Direct sums; direct products; mixed abelian groups; cotorsion groups.

  10. Gábor Braun, The cobordism class of the multiple points of immersions, Algebraic & Geometric Topology no. 8, 581–601 doi:10.2140/agt.2008.8.581 arXiv:math.AT/0409574

    Let us take an arbitrary immersion with even codimension. We derive an explicit formula for the characteristic classes of its multiple point manifolds. The main trick is solving a recursion on cohomology classes using power series.

    2000 Mathematics Subject Classification: Primary:57R20, 57R42; Secondary:16W60, 57R75

    Keywords: multiple-point manifold; immersion; cobordism class; generating function.

  11. Gábor Braun, Geometry of splice-quotient singularities, arXiv:0812.4403

    We obtain a new important basic result on splice-quotient singularities in an elegant combinatorial-geometric way: every level of the divisorial filtration of the ring of functions is generated by monomials of the defining coordinate functions. The elegant way is the language of of line bundles based on Okuma's description of the function ring of the universal abelian cover. As an easy application, we obtain a new proof of the End Curve Theorem of Neumann and Wahl.

    2000 Mathematics Subject Classification: Primary:14F05, 14J25; Secondary:14C17, 32S05, 32S50

    Keywords: splice-quotient singularity; End Curve Theorem; divisorial filtration.

  12. Gábor Braun and András Némethi, Invariants of Newton non-degenerate surface singularities, Compositio Mathematica no. 143, 1003–1036 MR 2339837 Zbl pre05177033 arXiv:math.AG/0609093

    We consider Newton non-degenerate, isolated surface singularities whose link is a rational homology sphere. We provide an algorithm to compute the Newton boundary of such a singularity from its resolution graph.

    2000 Mathematics Subject Classification: Primary:14J17, 14Q10; Secondary:52B20

    Keywords: hypersurface singularities; links of singularities; resolution graphs; Newton boundary; Newton polyhedrons.

    Remark. Publisher provided doi:10.1112/S0010437X07002941 does not resolve, so it is not linked.

  13. Gábor Braun and Gábor Lippner, Characteristic numbers of multiple-point manifolds, Bull. London Math. Soc. no. 38, 667–678 doi:10.1112/S0024609306018571

    We derive a recursion for the cohomology classes of multiple point manifolds of an arbitrary immersion with even codimension.

    2000 Mathematics Subject Classification: Primary:57R42; Secondary:57R20, 57R75

    Keywords: multiple-point manifold; characteristic number.

  14. Gábor Braun and Rüdiger Göbel, E-algebras whose torsion part is not cyclic, Proc. Amer. Math. Soc. 133 no. 8, 2251–2258 (electronic) MR 2138867 Zbl 1069.16036

    A generalized E-algebra is an algebra isomorphic to its own algebra of module endomorphisms. We give examples of such algebras over a Dedekind domain whose torsion part is not cyclic. It is based on earlier construction of torsion-free E-algebras.

    2000 Mathematics Subject Classification: Primary:16S50; Secondary:16Dxx

    Keywords: mixed E-rings; Dedekind domain.

  15. Gábor Braun, Characterization of matrix types of ultramatricial algebras, New York J. Math. 11 21–33 Zbl 1089.20035

    The matrix type of an algebra is an equivalence relation on natural numbers. Two numbers n and m are equivalent if the ring of n × n matrices is isomorphic to the ring of m × m matrices. We prove that matrix types of ultramatricial algebras over any field is in bijection with subgroups of the multiplicative group of positive rational numbers

    2000 Mathematics Subject Classification: Primary:20K30, 16S50; Secondary:06F20, 19A19

    Keywords: matrix type of a ring; dimension group; ultramtaricial algebra; automorphism group of a dimension group.

  16. Andreas Blass and Gábor Braun, Random Orders and Gambler's Ruin, Electronic Journal of Combinatorics 12 no. 1, R23 Zbl 1075.05004

    Solving a conjecture of Droste and Kuske, we compute the probability that a gambler will play at least a given number of rounds with a given initial wealth in the Gambler's Ruin game with a biased coin. We present several approaches to the problem.

    2000 Mathematics Subject Classification: Primary:05A15; Secondary:05A19, 60C05

    Keywords: gambler's ruin; random linear order.

  17. Gábor Braun, A proof of Higgins's conjecture, Bull. Austral. Math. Soc. 70 no. 2, 207–212 MR 2094288 Zbl 1080.20021 arXiv:math.GR/0312139

    Higgins conjectured a generalization of two theorems on decomposition of subgroups of free product of groups: Kuroš Theorem and his own generalization of Grušhko's Theorem. We prove this conjecture by improving Higgins's proof of these theorems using groupoids and covers.

    2000 Mathematics Subject Classification: Primary:20E06; Secondary:

    Keywords: free product of groups; free product of goupoids; Kuroš's theorem; Higgins's theorem; Gruško's theorem.

  18. Gábor Braun and Rüdiger Göbel, Automorphism groups of nilpotent groups, Arch. Math. (Basel) 80 no. 5, 464–474 MR 1 995 625 Zbl 1031.20032 doi:10.1007/s00013-003-0802-4

    The stabiliser group of an automorphism group of a class 2 nilpotent group is the normal subgroup consisting of elements acting trivially on the centre of the group and on the factor gof the group by the centre. We construct torsion-free class 2 nilpotent groups whose automorphism group is the semidirect product of the stabiliser group and an arbitrary group.

    2000 Mathematics Subject Classification: Primary:20F18; Secondary:18B15, 20F28

    Keywords: class 2 nilpotent group; automorphism group.

  19. Gábor Braun and Rüdiger Göbel, Outer automorphisms of locally finite p-groups, J. Algebra 264 no. 1, 55–67 MR 1 980 685 Zbl 1060.20031

    Every group has a semidirect product with a locally finite p-group such that the result has an arbitrary outer automorphism group.

    2000 Mathematics Subject Classification: Primary:20F28; Secondary:20F29, 20F50

    Keywords: outer automorphism group; locally finite p-group; Black Box.

  20. Gábor Braun, Outer automorphism groups, Ph.D. thesis, Universität Duisburg-Essen,

    If the continuum hypothesis holds then there exists a locally finite p-group of cardinality the successor of countably infinite with trivial centre and outer automorphism group. Without any additional set theoretic hypotheses, every group is an outer automorphism group of arbitrary many locally finite p-groups.

    2000 Mathematics Subject Classification: Primary:20F28; Secondary:20E22, 20F19, 20F50

    Keywords: locally finite p-group; outer automorphism group; Black Box; Continuum Hypothesis.