Change search
Refine search result
1 - 35 of 35
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1. Adamaszek, Michal
    et al.
    Barmak, Jonathan Ariel
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    On a lower bound for the connectivity of the independence complex of a graph2011In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, no 21, p. 2566-2569Article in journal (Refereed)
    Abstract [en]

    Aharoni, Berger and Ziv proposed a function which is a lower bound for the connectivity of the independence complex of a graph. They conjectured that this bound is optimal for every graph. We give two different arguments which show that the conjecture is false.

  • 2.
    Alexandersson, Per
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Panova, Greta
    LLT polynomials, chromatic quasisymmetric functions and graphs with cycles2018In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 341, no 12, p. 3453-3482Article in journal (Refereed)
    Abstract [en]

    We use a Dyck path model for unit-interval graphs to study the chromatic quasisymmetric functions introduced by Shareshian and Wachs, as well as unicellular LLT polynomials, revealing some parallel structure and phenomena regarding their e-positivity. The Dyck path model is also extended to circular arc digraphs to obtain larger families of polynomials, giving a new extension of LLT polynomials. Carrying over a lot of the noncircular combinatorics, we prove several statements regarding the e-coefficients of chromatic quasisymmetric functions and LLT polynomials, including a natural combinatorial interpretation for the e-coefficients for the line graph and the cycle graph for both families. We believe that certain e-positivity conjectures hold in all these families above. Furthermore, beyond the chromatic analogy, we study vertical-strip LLT polynomials, which are modified Hall-Littlewood polynomials. 

  • 3.
    Amini, Nima
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Combinatorics and zeros of multivariate polynomials2019Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis consists of five papers in algebraic and enumerative combinatorics. The objects at the heart of the thesis are combinatorial polynomials in one or more variables. We study their zeros, coefficients and special evaluations. Hyperbolic polynomials may be viewed as multivariate generalizations of real-rooted polynomials in one variable. To each hyperbolic polynomial one may associate a convex cone from which a matroid can be derived - a so called hyperbolic matroid. In Paper A we prove the existence of an infinite family of non-representable hyperbolic matroids parametrized by hypergraphs. We further use special members of our family to investigate consequences to a central conjecture around hyperbolic polynomials, namely the generalized Lax conjecture. Along the way we strengthen and generalize several symmetric function inequalities in the literature, such as the Laguerre-Tur\'an inequality and an inequality due to Jensen. In Paper B we affirm the generalized Lax conjecture for two related classes of combinatorial polynomials: multivariate matching polynomials over arbitrary graphs and multivariate independence polynomials over simplicial graphs. In Paper C we prove that the multivariate $d$-matching polynomial is hyperbolic for arbitrary multigraphs, in particular answering a question by Hall, Puder and Sawin. We also provide a hypergraphic generalization of a classical theorem by Heilmann and Lieb regarding the real-rootedness of the matching polynomial of a graph. In Paper D we establish a number of equidistributions between Mahonian statistics which are given by conic combinations of vincular pattern functions of length at most three, over permutations avoiding a single classical pattern of length three. In Paper E we find necessary and sufficient conditions for a candidate polynomial to be complemented to a cyclic sieving phenomenon (without regards to combinatorial context). We further take a geometric perspective on the phenomenon by associating a convex rational polyhedral cone which has integer lattice points in correspondence with cyclic sieving phenomena. We find the half-space description of this cone and investigate its properties.

  • 4.
    Amini, Nima
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Spectrahedrality of hyperbolicity cones of multivariate matching polynomials2018In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192Article in journal (Refereed)
    Abstract [en]

    The generalized Lax conjecture asserts that each hyperbolicity cone is a linear slice of the cone of positive semidefinite matrices. We prove the conjecture for a multivariate generalization of the matching polynomial. This is further extended (albeit in a weaker sense) to a multivariate version of the independence polynomial for simplicial graphs. As an application we give a new proof of the conjecture for elementary symmetric polynomials (originally due to Brändén). Finally we consider a hyperbolic convolution of determinant polynomials generalizing an identity of Godsil and Gutman.

  • 5.
    Amini, Nima
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Stable multivariate generalizations of matching polynomialsManuscript (preprint) (Other academic)
    Abstract [en]

    The first part of this note concerns stable averages of multivariate matching polynomials. In proving the existence of infinite families of bipartite Ramanujan d-coverings, Hall, Puder and Sawin introduced the d-matching polynomial of a graph G, defined as the uniform average of matching polynomials over the set of d-sheeted covering graphs of G. We prove that a natural multivariate version of the d-matching polynomial is stable, consequently giving a short direct proof of the real-rootedness of the d-matching polynomial. Our theorem also includes graphs with loops, thus answering a question of said authors. Furthermore we define a weaker notion of matchings for hypergraphs and prove that a family of natural polynomials associated to such matchings are stable. In particular this provides a hypergraphic generalization of the classical Heilmann-Lieb theorem.

  • 6.
    Amini, Nima
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Alexandersson, Per
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    The cone of cyclic sieving phenomena2019In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 342, no 6, p. 1581-1601Article in journal (Refereed)
    Abstract [en]

    We study cyclic sieving phenomena (CSP) on combinatorial objects from an abstract point of view by considering a rational polyhedral cone determined by the linear equations that define such phenomena. Each lattice point in the cone corresponds to a non-negative integer matrix which jointly records the statistic and cyclic order distribution associated with the set of objects realizing the CSP. In particular we consider a universal subcone onto which every CSP matrix linearly projects such that the projection realizes a CSP with the same cyclic orbit structure, but via a universal statistic that has even distribution on the orbits.

    Reiner et.al. showed that every cyclic action gives rise to a unique polynomial (mod q^n-1) complementing the action to a CSP. We give a necessary and sufficient criterion for the converse to hold. This characterization allows one to determine if a combinatorial set with a statistic gives rise (in principle) to a CSP without having a combinatorial realization of the cyclic action. We apply the criterion to conjecture a new CSP involving stretched Schur polynomials and prove our conjecture for certain rectangular tableaux. Finally we study some geometric properties of the CSP cone. We explicitly determine its half-space description and in the prime order case we determine its extreme rays.

  • 7.
    Anastasiou, Aspasia
    et al.
    KTH, Centres, Nordic Institute for Theoretical Physics NORDITA.
    Borsten, L.
    Dublin Inst Adv Studies, Sch Theoret Phys, 10 Burlington Rd, Dublin 4, Ireland..
    Duff, M. J.
    Imperial Coll London, Blackett Lab, Theoret Phys, London SW7 2AZ, England.;Univ Oxford, Math Inst, Radcliffe Observ Quarter, Andrew Wiles Bldg,Woodstock Rd, Oxford OX2 6GG, England..
    Marrani, A.
    Museo Stor Fis, Via Panisperna 89A, I-00184 Rome, Italy.;Ctr Studi & Ric Enrico Fermi, Via Panisperna 89A, I-00184 Rome, Italy.;Univ Padua, Dipartimento Fis & Astron Galileo Galilei, Via Marzolo 8, I-35131 Padua, Italy.;INFN, Sez Padova, Via Marzolo 8, I-35131 Padua, Italy..
    Nagy, S.
    Ctr Astron & Particle Theory, Univ Pk, Nottingham NG7 2RD, England..
    Zoccali, M.
    Imperial Coll London, Blackett Lab, Theoret Phys, London SW7 2AZ, England..
    The mile high magic pyramid2019In: NONASSOCIATIVE MATHEMATICS AND ITS APPLICATIONS / [ed] Vojtechovsky, P Bremner, MR Carter, JS Evans, AB Huerta, J Kinyon, MK Moorhouse, GE Smith, JDH, AMER MATHEMATICAL SOC , 2019, p. 1-27Conference paper (Refereed)
    Abstract [en]

    Using a unified formulation of N = 1, 2, 4, 8, super Yang-Mills theories in D = 3 spacetime dimensions with fields valued respectively in R, C, H, O, it was shown that tensoring left and right multiplets yields a Freudenthal magic square of D = 3 supergravities. When tied in with the more familiar R, C, H, O description of super Yang-Mills in D = 3, 4, 6, 10 this results in a magic pyramid of supergravities: the known 4x4 magic square at the base in D = 3, a 3x3 square in D = 4, a 2x2 square in D = 6 and Type II supergravity at the apex in D = 10.

  • 8.
    Atserias, Albert
    et al.
    Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..
    Bonacina, Ilario
    Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..
    de Rezende, Susanna F.
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Lauria, Massimo
    Sapienza Univ Roma, Dept Stat Sci, Rome, Italy..
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS).
    Razborov, Alexander
    Univ Chicago, Chicago, IL 60637 USA.;Steklov Math Inst, Moscow, Russia..
    Clique Is Hard on Average for Regular Resolution2018In: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING / [ed] Diakonikolas, I Kempe, D Henzinger, M, ASSOC COMPUTING MACHINERY , 2018, p. 866-877Conference paper (Refereed)
    Abstract [en]

    We prove that for k << (4)root n regular resolution requires length n(Omega(k)) to establish that an Erdos Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n(Omega(k)) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

  • 9.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlöf, J.
    Dense Subset Sum may be the hardest2016In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Conference paper (Refereed)
    Abstract [en]

    The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O∗(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O∗(2(0.5-δ)n)-time algorithm, with some constant δ &gt; 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ &gt; 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

  • 10. Ayyer, Arvind
    et al.
    Bouttier, Jeremie
    Linusson, Svante
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Nunzi, Francois
    Some genelalized juggling processes (extended abstract)2015In: DMTCS proc. FPSAC'15, Nancy, France, 2015, p. 925-936Conference paper (Refereed)
    Abstract [en]

    We consider generalizations of juggling Markov chains introduced by Ayyer, Bouttier, Corteel and Nunzi. We first study multispecies generalizations of all the finite models therein, namely the MJMC, the add-drop and the annihilation models. We then consider the case of several jugglers exchanging balls. In all cases, we give explicit product formulas for the stationary probability and closed-form expressions for the normalization factor if known.

  • 11. Barak, B.
    et al.
    Gopalan, P.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Meka, R.
    Raghavendra, P.
    Steurer, D.
    Making the long code shorter2015In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, no 5, p. 1287-1324Article in journal (Refereed)
    Abstract [en]

    The long code is a central tool in hardness of approximation especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results including the following: (1) For any ε &gt; 0, we show the existence of an n-vertex graph G where every set of o(n) vertices has expansion 1-ε but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563-572] who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo K into instances with alphabet k with a blowup of kpolylog(K) , improving over the previously known gadget with blowup of kω(K). (3) An n-variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the semidefinite programming version of the Sherali-Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.

  • 12. Bhattacharya, S.
    et al.
    Henzinger, M.
    Na Nongkai, Danupon
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    New deterministic approximation algorithms for fully dynamic matching2016In: STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, p. 398-411Conference paper (Refereed)
    Abstract [en]

    We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2 + ϵ)-approximate maximum matching in general graphs with O(poly(log n, 1/ϵ)) update time. (2) An algorithm that maintains an αk approximation of the value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1 ≤ αk ≤ 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.

  • 13.
    Björnberg, Jakob Erik
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Graphical representations of Ising and Potts models: Stochastic geometry of the quantum Ising model and the space-time Potts model2009Doctoral thesis, monograph (Other academic)
    Abstract [en]

    HTML clipboard Statistical physics seeks to explain macroscopic properties of matter in terms of microscopic interactions. Of particular interest is the phenomenon of phase transition: the sudden changes in macroscopic properties as external conditions are varied. Two models in particular are of great interest to mathematicians, namely the Ising model of a magnet and the percolation model of a porous solid. These models in turn are part of the unifying framework of the random-cluster representation, a model for random graphs which was first studied by Fortuin and Kasteleyn in the 1970’s. The random-cluster representation has proved extremely useful in proving important facts about the Ising model and similar models.

    In this work we study the corresponding graphical framework for two related models. The first model is the transverse field quantum Ising model, an extension of the original Ising model which was introduced by Lieb, Schultz and Mattis in the 1960’s. The second model is the space–time percolation process, which is closely related to the contact model for the spread of disease. In Chapter 2 we define the appropriate space–time random-cluster model and explore a range of useful probabilistic techniques for studying it. The space– time Potts model emerges as a natural generalization of the quantum Ising model. The basic properties of the phase transitions in these models are treated in this chapter, such as the fact that there is at most one unbounded fk-cluster, and the resulting lower bound on the critical value in .

    In Chapter 3 we develop an alternative graphical representation of the quantum Ising model, called the random-parity representation. This representation is based on the random-current representation of the classical Ising model, and allows us to study in much greater detail the phase transition and critical behaviour. A major aim of this chapter is to prove sharpness of the phase transition in the quantum Ising model—a central issue in the theory— and to establish bounds on some critical exponents. We address these issues by using the random-parity representation to establish certain differential inequalities, integration of which gives the results.

    In Chapter 4 we explore some consequences and possible extensions of the results established in Chapters 2 and 3. For example, we determine the critical point for the quantum Ising model in and in ‘star-like’ geometries.

  • 14.
    Björner, Anders
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Vorwerk, Kathrin
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    On the connectivity of manifold graphs2015In: Proceedings of the American Mathematical Society, ISSN 0002-9939, E-ISSN 1088-6826, Vol. 143, no 10, p. 4123-4132Article in journal (Refereed)
    Abstract [en]

    This paper is concerned with lower bounds for the connectivity of graphs (one-dimensional skeleta) of triangulations of compact manifolds. We introduce a structural invariant b_M for simplicial d-manifolds M taking values in the range 0 <= b_M <= d-1. The main result is that b_M influences connectivity in the following way: The graph of a d-dimensional simplicial compact manifold M is (2d - b_M)-connected. The parameter b_M has the property that b_M = 0 if the complex M is flag. Hence, our result interpolates between Barnette's theorem (1982) that all d-manifold graphs are (d+1)-connected and Athanasiadis' theorem (2011) that flag d-manifold graphs are 2d-connected. The definition of b_M involves the concept of banner triangulations of manifolds, a generalization of flag triangulations.

  • 15.
    Braun, Benjamin
    et al.
    Univ Kentucky, Dept Math, Lexington, KY 40506 USA..
    Davis, Robert
    Michigan State Univ, Dept Math, E Lansing, MI 48824 USA..
    Solus, Liam
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Detecting the integer decomposition property and Ehrhart unimodality in reflexive simplices2018In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 100, p. 122-142Article in journal (Refereed)
    Abstract [en]

    A long-standing open conjecture in combinatorics asserts that a Gorenstein lattice polytope with the integer decomposition property (IDP) has a unimodal (Ehrhart) h*-polynomial. This conjecture can be viewed as a strengthening of a previously disproved conjecture which stated that any Gorenstein lattice polytope has a unimodal h*-polynomial. The first counterexamples to unimodality for Gorenstein lattice polytopes were given in even dimensions greater than five by Mustata and Payne, and this was extended to all dimensions greater than five by Payne. While there exist numerous examples in support of the conjecture that IDP reflexives are h*-unimodal, its validity has not yet been considered for families of reflexive lattice simplices that closely generalize Payne's counterexamples. The main purpose of this work is to prove that the former conjecture does indeed hold for a natural generalization of Payne's examples. The second purpose of this work is to extend this investigation to a broader class of lattice simplices, for which we present new results and open problems. 

  • 16. Chalermsook, Parinya
    et al.
    Cygan, Marek
    Kortsarz, Guy
    Laekhanukit, Bundit
    Manurangsi, Pasin
    Na Nongkai, Danupon
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Trevisan, Luca
    From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More2017In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2017, Vol. 2017, p. 743-754Conference paper (Refereed)
    Abstract [en]

    We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e.g., this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (Gap-ETH) [4], [5], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k(o(1))-FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log(1/4+epsilon) (OPT) approximation for DomSet for any constant epsilon > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

  • 17. Deng, J.
    et al.
    Song, Wenjun
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
    Liu, Z.
    Baras, J. S.
    Pose synchronization of rigid body networks with switching topologies2015In: 2015 34th Chinese Control Conference (CCC), IEEE Computer Society, 2015, Vol. 2015, p. 7639-7644Conference paper (Refereed)
    Abstract [en]

    Coordination control of multiple rigid bodies attracts much attention of researchers due to its wide applications. This paper presents the pose synchronization problem of the moving rigid bodies whose dynamics is described by the group SE(3). The case of bidirectional neighbor graphs with switching interconnection topologies is considered. We design a distributed control law based on relative rotation matrices and relative positions between the neighboring rigid bodies, and show that the SE(3) reaches pose synchronization if and only if the neighbor graphs are infinitely jointly connected, which relaxes the theoretical results in the existing literature.

  • 18.
    Di Rocco, Sandra
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Haase, Christian
    Free Univ Berlin, Berlin, Germany..
    Nill, Benjamin
    OvGU Magdeburg, Magdeburg, Germany..
    A note on discrete mixed volume and Hodge-Deligne numbers2019In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 104, p. 1-13Article in journal (Refereed)
    Abstract [en]

    Generalizing the famous Bernstein-Kushnirenko theorem, Khovanskii proved in 1978 a combinatorial formula for the arithmetic genus of the compactification of a generic complete intersection associated to a family of lattice polytopes. Recently, an analogous combinatorial formula, called the discrete mixed volume, was introduced by Bihan and shown to be nonnegative. By making a footnote of Khovanskii in his paper explicit, we interpret this invariant as the (motivic) arithmetic genus of the non-compact generic complete intersection associated to the family of lattice polytopes.

  • 19.
    Engardt, Max
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Structure Learning of Bayesian Networks with Bounded Treewidth Using Mixed Integer Linear Programming2014Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    When given a Bayesian network, a common use of it is calculating conditional probabilities. This is known as inference. In order to be able to infer effectively, the structure of the Bayesian network is required to have low treewidth. Therefore, the problem of learning the structure of Bayesian networks with bounded treewidth is studied in this thesis. This is solved by reducing the problem to a mixed integer linear problem using several formulation for the structure of the Bayesian network as well as for bounding the treewidth of the structure. Solving the problem in this way gives an algorithm known as an anytime algorithm which can be aborted during the run and return a solution as well as an upper bound for the value of the best possible solution. Tests show that several of these formulations are of practical use as implementations of them prove solutions to be optimal or nearly optimal for several data sets.

  • 20. Eriksen, Niklas
    et al.
    Sjöstrand, Jonas
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Equidistributed Statistics on Matchings and Permutations2014In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 21, no 4, article id P4.43Article in journal (Refereed)
    Abstract [en]

    We show that the bistatistic of right nestings and right crossings in matchings without left nestings is equidistributed with the number of occurrences of two certain patterns in permutations, and furthermore that this equidistribution holds when refined to positions of these statistics in matchings and permutations. For this distribution we obtain a non-commutative generating function which specializes to Zagier's generating function for the Fishburn numbers after abelianization. As a special case we obtain proofs of two conjectures of Claesson and Linusson. Finally, we conjecture that our results can be generalized to involving left crossings of matchings too.

  • 21.
    Eriksson, Kimmo
    et al.
    Mälardalen University, School of Education, Culture and Communication.
    Sjöstrand, Jonas
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
    Limiting shapes of birth-and-death processes on Young diagrams2012In: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 48, no 4, p. 575-602Article in journal (Refereed)
    Abstract [en]

    We consider a family of birth processes and birth-and-death processes on Young diagrams of integer partitions of n. This family incorporates three famous models from very different fields: Rost's totally asymmetric particle model (in discrete time), Simon's urban growth model, and Moran's infinite alleles model. We study stationary distributions and limit shapes as n tends to infinity, and present a number of results and conjectures.

  • 22.
    Eriksson, Kimmo
    et al.
    Malardalen Univ, Dept Math & Phys.
    Sjöstrand, Jonas
    Malardalen Univ, Dept Math & Phys.
    Strimling, Pontus
    Malardalen Univ, Dept Math & Phys.
    Optimal expected rank in a two-sided secretary problem2007In: Operations Research, ISSN 0030-364X, E-ISSN 1526-5463, Vol. 55, no 5, p. 921-931Article in journal (Refereed)
    Abstract [en]

    In a two-sided version of the famous secretary problem, employers search for a secretary at the same time as secretaries search for an employer. Nobody accepts being put on hold, and nobody is willing to take part in more than N interviews. Preferences are independent, and agents seek to optimize the expected rank of the partner they obtain among the N potential partners. We find that in any subgame perfect equilibrium, the expected rank grows as the square root of N (whereas it tends to a constant in the original secretary problem). We also compute how much agents can gain by cooperation.

  • 23. Hachem, Walid
    et al.
    Hardy, Adrien
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Najim, Jamal
    Large complex correlated wishart matrices: Fluctuations and asymptotic independence at the edges2016In: Annals of Probability, ISSN 0091-1798, E-ISSN 2168-894X, Vol. 44, no 3, p. 2264-2348Article in journal (Refereed)
    Abstract [en]

    We study the asymptotic behavior of eigenvalues of large complex correlated Wishart matrices at the edges of the limiting spectrum. In this setting, the support of the limiting eigenvalue distribution may have several connected components. Under mild conditions for the population matrices, we show that for every generic positive edge of that support, there exists an extremal eigenvalue which converges almost surely toward that edge and fluctuates according to the Tracy-Widom law at the scale N-2/3. Moreover, given several generic positive edges, we establish that the associated extremal eigenvalue fluctuations are asymptotically independent. Finally, when the leftmost edge is the origin ( hard edge), the fluctuations of the smallest eigenvalue are described by mean of the Bessel kernel at the scale N-2.

  • 24.
    Hultman, Axel
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Jonsson, Jakob
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    The topology of the space of matrices of Barvinok rank two2010In: Beiträge zur Algebra und Geometrie, ISSN 0138-4821, Vol. 51, no 2, p. 373-390Article in journal (Refereed)
    Abstract [en]

    The Barvinok rank of a d x n matrix is the minimum number of  points in Rd such that the tropical convex hull of the points contains all columns of the matrix. The concept originated in work by Barvinok and others on the travelling salesman problem. Our object of study is the space of real d x n matrices of Barvinok rank two. Let Bd,n denote this space modulo rescaling and translation. We show that Bd,n is a manifold, thereby settling a  conjecture due to Develin. In fact, Bd,n is homeomorphic to the quotient of the product of spheres Sd-2 x Sn-2 under the involution which sends each point to its antipode simultaneously in both  components.  In addition, using discrete Morse theory, we compute the integral homology of Bd,n. Assuming d \ge n, for odd d the homology turns out to be   isomorphic to that of Sd-2 x RPn-2. This  is true also for even d up to degree d-3, but the two cases differ from degree d-2 and up. The homology computation straightforwardly extends to more general  complexes of the form (Sd-2 x X)//Z2, where X is a finite cell  complex of dimension at most d-2 admitting a free  Z2-action.

  • 25. Kennedy, J. B.
    et al.
    Kurasov, P.
    Malenova, Gabriela
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.
    Mugnolo, D.
    On the Spectral Gap of a Quantum Graph2016In: Annales de l'Institute Henri Poincare. Physique theorique, ISSN 1424-0637, E-ISSN 1424-0661, p. 1-35Article in journal (Refereed)
    Abstract [en]

    We consider the problem of finding universal bounds of “isoperimetric” or “isodiametric” type on the spectral gap of the Laplacian on a metric graph with natural boundary conditions at the vertices, in terms of various analytical and combinatorial properties of the graph: its total length, diameter, number of vertices and number of edges. We investigate which combinations of parameters are necessary to obtain non-trivial upper and lower bounds and obtain a number of sharp estimates in terms of these parameters. We also show that, in contrast to the Laplacian matrix on a combinatorial graph, no bound depending only on the diameter is possible. As a special case of our results on metric graphs, we deduce estimates for the normalised Laplacian matrix on combinatorial graphs which, surprisingly, are sometimes sharper than the ones obtained by purely combinatorial methods in the graph theoretical literature.

  • 26.
    Linusson, Svante
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Potka, Samu
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    New properties of the Edelman-Greene bijectionManuscript (preprint) (Other academic)
    Abstract [en]

    Edelman and Greene constructed a correspondence between reduced words of the reverse permutation and standard Young tableaux. We prove that for any reduced word the shape of the region of the insertion tableau containing the smallest possible entries evolves exactly as the upper-left component of the permutation's (Rothe) diagram. Properties of the Edelman-Greene bijection restricted to 132-avoiding and 2143-avoiding permutations are presented. We also consider the Edelman-Greene bijection applied to non-reduced words.

  • 27.
    Linusson, Svante
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Potka, Samu
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Sulzgruber, Robin
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    On random shifted standard Young tableaux and 132-avoiding sorting networksManuscript (preprint) (Other academic)
    Abstract [en]

    We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman-Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.

  • 28.
    Lundman, Anders
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Computing Seshardi constants on smooth toric surfacesManuscript (preprint) (Other academic)
    Abstract [en]

    In this paper we compute the Seshadri constants at the general point on many smooth polarized toric surfaces. We consider the case when the degree of jet separation is small or the core of the associated polygon is a line segment. Our main result is that in this case the Seshadri constant at the general point can often be determined in terms of easily computable invariants of the surfaces at hand. Lastly we consider the case that the core of the associated polygon is a point for a smooth polarized toric surface (X, L ). We show that in this case X can be constructed via consecutive equivariant blow-ups of either P^2 or P^1 x P^1. 

  • 29.
    Lundman, Anders
    et al.
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Di Rocco, Sandra
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Jabbusch, Kelly
    Department of mathematics & statistics, University of Michigan-Dearborn.
    A note on higher order Gauss MapsManuscript (preprint) (Other academic)
    Abstract [en]

    We study Gauss maps of order k, associated to a projective variety X embedded in projective space via a line bundle L. We show that if X is a smooth, complete complex variety and L is a k-jet spanned line bundle on X, with k > 1, then the Gauss map of order k has finite fibers, unless X = P^n is embedded by the Veronese embedding of order k. In the case where X is a toric variety, we give a combinatorial description of the Gauss maps of order k, its image and the general fibers. 

  • 30.
    Potka, Samu
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Limit shapes of standard Young tableaux and sorting networks via the Edelman-Greene correspondence2018Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis consists of the following two articles.

    • New properties of the Edelman–Greene bijection. Edelman and Greene constructed a correspondence between reduced words of the reverse permutation and standard Young tableaux. We prove that for any reduced word the shape of the region of the insertion tableau containing the smallest possible entries evolves exactly as the upper-left component of the permutation’s (Rothe) diagram. Properties of the Edelman–Greene bijection restricted to 132-avoiding and 2143-avoiding permutations are presented. We also consider the Edelman-Greene bijection applied to non-reduced words.
    • On random shifted standard Young tableaux and 132-avoiding sorting networks. We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman–Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.
  • 31. Shi, Guodong
    et al.
    Anderson, Brian D. O.
    Johansson, Karl Henrik
    KTH, School of Electrical Engineering (EES), Automatic Control. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
    Consensus Over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence2015In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 61, no 10, p. 5690-5707Article in journal (Refereed)
    Abstract [en]

    Distributed consensus computation over random graph processes is considered. The random graph process is defined as a sequence of random variables which take values from the set of all possible digraphs over the node set. At each time step, every node updates its state based on a Bernoulli trial, independent in time and among different nodes: either averaging among the neighbor set generated by the random graph, or sticking with its current state. The connectivity-independence and arc-independence are introduced to capture the fundamental influence of the random graphs on the consensus convergence. Necessary and/or sufficient conditions are presented on the success probabilities of the Bernoulli trials for the network to reach a global almost sure consensus, with some sharp threshold established revealing a consensus zero-one law. Convergence rates are established by the lower and upper bounds of the epsilon-computation time. We also generalize the concepts of connectivity/arc independence to their analogues from the *-mixing point of view, so that our results apply to a very wide class of graphical models, including the majority of random graph models in the literature, e.g., Erdos-Renyi, gossiping, and Markovian random graphs. We show that under *-mixing, our convergence analysis continues to hold and the corresponding almost sure consensus conditions are established. Finally, we further investigate almost sure finite-time convergence of random gossiping algorithms, and prove that the Bernoulli trials play a key role in ensuring finite-time convergence. These results add to the understanding of the interplay between random graphs, random computations, and convergence probability for distributed information processing.

  • 32.
    Shirabe, Takeshi
    KTH, School of Architecture and the Built Environment (ABE), Urban Planning and Environment, Geoinformatics.
    A method for finding a least-cost wide path in raster space2016In: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, Vol. 30, no 8, p. 1469-1485Article in journal (Refereed)
    Abstract [en]

    Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values.

  • 33. Strimling, Pontus
    et al.
    Sjöstrand, Jonas
    Centre for the Study of Cultural Evolution, Stockholm University.
    Accumulation of independent cultural traits2009In: Theoretical Population Biology, ISSN 0040-5809, E-ISSN 1096-0325, Vol. 76, no 2, p. 77-83Article in journal (Refereed)
    Abstract [en]

    In a species capable of (imperfect) social learning, how much culture can a population of a given size carry? And what is the relationship between the individual and the population? In the first study of these novel questions, here we develop a mathematical model of the accumulation of independent cultural traits in a finite population with overlapping generations.

  • 34. Tancer, Martin
    et al.
    Vorwerk, Kathrin
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Non-embeddability of geometric lattices and buildings2014In: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 51, no 4, p. 779-801Article in journal (Refereed)
    Abstract [en]

    A fundamental question for simplicial complexes is to find the lowest dimensional Euclidean space in which they can be embedded. We investigate this question for order complexes of posets. We show that order complexes of thick geometric lattices as well as several classes of finite buildings, all of which are order complexes, are hard to embed. That means that such -dimensional complexes require -dimensional Euclidean space for an embedding. (This dimension is always sufficient for any -complex.) We develop a method to show non-embeddability for general order complexes of posets.

  • 35.
    Thunberg, Hans
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
    Tonsättaren Per Nörgårds ''oändlighetsserie"2013In: Normat, ISSN 0801-3500, Vol. 61, no 1, p. 33-47Article in journal (Refereed)
    Abstract [en]

    This article presents a mathematical description, in terms of recursively defined number sequences, of the algorithms devised by the Danish composer Nørgård. The ambition of the latter was to generate from a very short sequence of tones melodies rich in symmetries and selfsimilarities, melodies which could be aperiodic and hence infinite in length. Given the mathematical presentation a variety of results can be formulated and proved. Note that the well-known Thue-Morse sequence is essentially a special case.

1 - 35 of 35
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf