Ändra sökning
Avgränsa sökresultatet
1 - 37 av 37
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf
Träffar per sida
• 5
• 10
• 20
• 50
• 100
• 250
Sortering
• Standard (Relevans)
• Författare A-Ö
• Författare Ö-A
• Titel A-Ö
• Titel Ö-A
• Publikationstyp A-Ö
• Publikationstyp Ö-A
• Äldst först
• Nyast först
• Disputationsdatum (tidigaste först)
• Disputationsdatum (senaste först)
• Standard (Relevans)
• Författare A-Ö
• Författare Ö-A
• Titel A-Ö
• Titel Ö-A
• Publikationstyp A-Ö
• Publikationstyp Ö-A
• Äldst först
• Nyast först
• Disputationsdatum (tidigaste först)
• Disputationsdatum (senaste först)
Markera
Maxantalet träffar du kan exportera från sökgränssnittet är 250. Vid större uttag använd dig av utsökningar.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
On a lower bound for the connectivity of the independence complex of a graph2011Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, nr 21, s. 2566-2569Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
LLT polynomials, chromatic quasisymmetric functions and graphs with cycles2018Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 341, nr 12, s. 3453-3482Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Combinatorics and zeros of multivariate polynomials2019Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Spectrahedrality of hyperbolicity cones of multivariate matching polynomials2018Ingår i: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Stable multivariate generalizations of matching polynomialsManuskript (preprint) (Övrigt vetenskapligt)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The cone of cyclic sieving phenomena2019Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 342, nr 6, s. 1581-1601Artikel i tidskrift (Refereegranskat)

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.
KTH, Centra, Nordic Institute for Theoretical Physics NORDITA.
Dublin Inst Adv Studies, Sch Theoret Phys, 10 Burlington Rd, Dublin 4, Ireland.. 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.. 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.. Ctr Astron & Particle Theory, Univ Pk, Nottingham NG7 2RD, England.. Imperial Coll London, Blackett Lab, Theoret Phys, London SW7 2AZ, England..
The mile high magic pyramid2019Ingår i: 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, s. 1-27Konferensbidrag (Refereegranskat)

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.
Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain..
Univ Politecn Cataluna, Dept Comp Sci, Barcelona, Spain.. KTH, Skolan för elektroteknik och datavetenskap (EECS). Sapienza Univ Roma, Dept Stat Sci, Rome, Italy.. KTH, Skolan för elektroteknik och datavetenskap (EECS). Univ Chicago, Chicago, IL 60637 USA.;Steklov Math Inst, Moscow, Russia..
Clique Is Hard on Average for Regular Resolution2018Ingår i: 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, s. 866-877Konferensbidrag (Refereegranskat)

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.
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.
Dense Subset Sum may be the hardest2016Ingår i: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Konferensbidrag (Refereegranskat)

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
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Some genelalized juggling processes (extended abstract)2015Ingår i: DMTCS proc. FPSAC'15, Nancy, France, 2015, s. 925-936Konferensbidrag (Refereegranskat)

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.
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.
Making the long code shorter2015Ingår i: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, nr 5, s. 1287-1324Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.
New deterministic approximation algorithms for fully dynamic matching2016Ingår i: STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, s. 398-411Konferensbidrag (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
Graphical representations of Ising and Potts models: Stochastic geometry of the quantum Ising model and the space-time Potts model2009Doktorsavhandling, monografi (Övrigt vetenskapligt)

HTML clipboard Statistisk fysik syftar till att förklara ett materials makroskopiska egenskaper i termer av dess mikroskopiska struktur. En särskilt intressant egenskap är är fenomenet fasövergång, det vill säga en plötslig förändring i de makroskopiska egenskaperna när externa förutsättningar varieras. Två modeller är särskilt intressanta för en matematiker, nämligen Ising-modellen av en magnet och perkolationsmodellen av ett poröst material. Dessa två modeller sammanförs av den så-kallade fk-modellen, en slumpgrafsmodell som först studerades av Fortuin och Kasteleyn på 1970-talet. fk-modellen har sedermera visat sig vara extremt användbar för att bevisa viktiga resultat om Ising-modellen och liknande modeller.

I den här avhandlingen studeras den motsvarande grafiska strukturen hos två näraliggande modeller. Den första av dessa är den kvantteoretiska Isingmodellen med transverst fält, vilken är en utveckling av den klassiska Isingmodellen och först studerades av Lieb, Schultz och Mattis på 1960-talet. Den andra modellen är rumtid-perkolation, som är nära besläktad med kontaktmodellen av infektionsspridning. I Kapitel 2 definieras rumtid-fk-modellen, och flera probabilistiska verktyg utforskas för att studera dess grundläggande egenskaper. Vi möter rumtid-Potts-modellen, som uppenbarar sig som en naturlig generalisering av den kvantteoretiska Ising-modellen. De viktigaste egenskaperna hos fasövergången i dessa modeller behandlas i detta kapitel, exempelvis det faktum att det i fk-modellen finns högst en obegränsad komponent, samt den undre gräns för det kritiska värdet som detta innebär.

I Kapitel 3 utvecklas en alternativ grafisk framställning av den kvantteoretiska Ising-modellen, den så-kallade slumpparitetsframställningen. Denna är baserad på slumpflödesframställningen av den klassiska Ising-modellen, och är ett verktyg som låter oss studera fasövergången och gränsbeteendet mycket närmare. Huvudsyftet med detta kapitel är att bevisa att fasövergången är skarp—en central egenskap—samt att fastslå olikheter för vissa kritiska exponenter. Metoden består i att använda slumpparitetsframställningen för att härleda vissa differentialolikheter, vilka sedan kan integreras för att lägga fast att gränsen är skarp.

I Kapitel 4 utforskas några konsekvenser, samt möjliga vidareutvecklingar, av resultaten i de tidigare kapitlen. Exempelvis bestäms det kritiska värdet hos den kvantteoretiska Ising-modellen på , samt i ‘stjärnliknankde’ geometrier.

• 14.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
On the connectivity of manifold graphs2015Ingår i: Proceedings of the American Mathematical Society, ISSN 0002-9939, E-ISSN 1088-6826, Vol. 143, nr 10, s. 4123-4132Artikel i tidskrift (Refereegranskat)

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.
Univ Kentucky, Dept Math, Lexington, KY 40506 USA..
Michigan State Univ, Dept Math, E Lansing, MI 48824 USA.. KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
Detecting the integer decomposition property and Ehrhart unimodality in reflexive simplices2018Ingår i: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 100, s. 122-142Artikel i tidskrift (Refereegranskat)

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
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More2017Ingår i: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2017, Vol. 2017, s. 743-754Konferensbidrag (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Optimeringslära och systemteori.
Pose synchronization of rigid body networks with switching topologies2015Ingår i: 2015 34th Chinese Control Conference (CCC), IEEE Computer Society, 2015, Vol. 2015, s. 7639-7644Konferensbidrag (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Free Univ Berlin, Berlin, Germany.. OvGU Magdeburg, Magdeburg, Germany..
A note on discrete mixed volume and Hodge-Deligne numbers2019Ingår i: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 104, s. 1-13Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Structure Learning of Bayesian Networks with Bounded Treewidth Using Mixed Integer Linear Programming2014Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)

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
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Equidistributed Statistics on Matchings and Permutations2014Ingår i: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 21, nr 4, artikel-id P4.43Artikel i tidskrift (Refereegranskat)

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.
Mälardalen University, School of Education, Culture and Communication.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
Limiting shapes of birth-and-death processes on Young diagrams2012Ingår i: Advances in Applied Mathematics, ISSN 0196-8858, E-ISSN 1090-2074, Vol. 48, nr 4, s. 575-602Artikel i tidskrift (Refereegranskat)

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.
Malardalen Univ, Dept Math & Phys.
Malardalen Univ, Dept Math & Phys. Malardalen Univ, Dept Math & Phys.
Optimal expected rank in a two-sided secretary problem2007Ingår i: Operations Research, ISSN 0030-364X, E-ISSN 1526-5463, Vol. 55, nr 5, s. 921-931Artikel i tidskrift (Refereegranskat)

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
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Large complex correlated wishart matrices: Fluctuations and asymptotic independence at the edges2016Ingår i: Annals of Probability, ISSN 0091-1798, E-ISSN 2168-894X, Vol. 44, nr 3, s. 2264-2348Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
The topology of the space of matrices of Barvinok rank two2010Ingår i: Beiträge zur Algebra und Geometrie, ISSN 0138-4821, Vol. 51, nr 2, s. 373-390Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Numerisk analys, NA.
On the Spectral Gap of a Quantum Graph2016Ingår i: Annales de l'Institute Henri Poincare. Physique theorique, ISSN 1424-0637, E-ISSN 1424-0661, s. 1-35Artikel i tidskrift (Refereegranskat)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
New properties of the Edelman-Greene bijectionManuskript (preprint) (Övrigt vetenskapligt)

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.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Properties of the Edelman-Greene bijection2020Ingår i: Journal of Combinatorics, ISSN 2156-3527, E-ISSN 2150-959X, Vol. 11, nr 2, s. 249-273Artikel i tidskrift (Refereegranskat)

Edelman and Greene constructed a bijective 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.

• 28.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.). KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
On random shifted standard Young tableaux and 132-avoiding sorting networksManuskript (preprint) (Övrigt vetenskapligt)

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.

• 29.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Computing Seshardi constants on smooth toric surfacesManuskript (preprint) (Övrigt vetenskapligt)

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.

• 30.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.). Department of mathematics & statistics, University of Michigan-Dearborn.
A note on higher order Gauss MapsManuskript (preprint) (Övrigt vetenskapligt)

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.

• 31.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Limit shapes of standard Young tableaux and sorting networks via the Edelman-Greene correspondence2018Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)

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.
• 32. Shi, Guodong
KTH, Skolan för elektro- och systemteknik (EES), Reglerteknik. KTH, Skolan för elektro- och systemteknik (EES), Centra, ACCESS Linnaeus Centre.
Consensus Over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence2015Ingår i: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 61, nr 10, s. 5690-5707Artikel i tidskrift (Refereegranskat)

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.

• 33.
KTH, Skolan för arkitektur och samhällsbyggnad (ABE), Samhällsplanering och miljö, Geoinformatik.
A method for finding a least-cost wide path in raster space2016Ingår i: International Journal of Geographical Information Science, ISSN 1365-8816, E-ISSN 1365-8824, Vol. 30, nr 8, s. 1469-1485Artikel i tidskrift (Refereegranskat)

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.

• 34. Strimling, Pontus
Centre for the Study of Cultural Evolution, Stockholm University.
Accumulation of independent cultural traits2009Ingår i: Theoretical Population Biology, ISSN 0040-5809, E-ISSN 1096-0325, Vol. 76, nr 2, s. 77-83Artikel i tidskrift (Refereegranskat)

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.

• 35. Tancer, Martin
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Non-embeddability of geometric lattices and buildings2014Ingår i: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 51, nr 4, s. 779-801Artikel i tidskrift (Refereegranskat)

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.

• 36.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Symmetriska tonförrådManuskript (preprint) (Övrig (populärvetenskap, debatt, mm))

Heltonsskalorna och dimskalorna är exempel på så kallade symmetriska skalor, det vill säga tonklassmängder (tonförråd) som är invarianta under transponering med \$n\$ halvtonssteg för något tal \$n\$, \$1\le n \le 11\$.

På ett systematiskt sätt konstrueras i artikeln alla möjliga symmetriska tonklassmängder inom det kromatiska tonförrådet. Vi finner totalt 15 olika typer, varav 10 stycken innehåller sex tonklasser (toner) eller fler.

• 37.
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.), Matematik (Avd.).
Tonsättaren Per Nörgårds ''oändlighetsserie"2013Ingår i: Normat, ISSN 0801-3500, Vol. 61, nr 1, s. 33-47Artikel i tidskrift (Refereegranskat)

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 - 37 av 37
RefereraExporteraLänk till träfflistan
Permanent länk
Referera
Referensformat
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Annat format
Fler format
Språk
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Annat språk
Fler språk
Utmatningsformat
• html
• text
• asciidoc
• rtf