检索结果-内蒙古大学图书馆

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第8期62卷 4361-4375页

作者： Baryshnikov, Yuliy Duda, Jaroslaw (Jarek) Szpankowski, Wojciech Univ Illinois Dept Math & Elect & Comp Engn Urbana IL 61801 USA Purdue Univ Ctr Sci Informat W Lafayette IN 47907 USA Jagiellonian Univ Inst Comp Sci & Comp Math PL-31007 Krakow Poland Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Gdansk Univ Technol Fac Elect Telecommun & Informat PL-80233 Gdansk Poland

The method of types is one of the most popular techniques in information theory and combinatorics. However, thus far the method has been mostly applied to 1-D Markov processes, and it has not been thoroughly studied for general Markov fields. Markov fields over a finite alphabet of size m >= 2 can be viewed as models for multidimensional systems with local interactions. The locality of these interactions is represented by a shape S while its marking by symbols of the underlying alphabet is called a tile. Two assignments in a Markov field have the same type if they have the same empirical distribution, i.e., if they have the same number of tiles of a given type. Our goal is to study the growth of the number of possible Markov field types in either a d-dimensional box of lengths n(1), ..., n(d) or its cyclic counterpart, a d-dimensional torus. We relate this question to the enumeration of nonnegative integer solutions of a large system of Diophantine linear equations called the conservation laws. We view a Markov type as a vector in a D = m(vertical bar S vertical bar) dimensional space and count the number of such vectors satisfying the conservation laws, which turns out to be the number of integer points in a certain polytope. For the torus, this polytope is of dimension mu = D - 1- rk(C), where rk(C) is the number of linearly independent conservation laws C. This provides an upper bound on the number of types. Then, we construct a matching lower bound leading to the conclusion that the number of types in the torus Markov field is Theta (N-mu), where N = n(1) ... n(d). These results are derived by geometric tools, including ideas of discrete and convex multidimensional geometry.

关键词： Markov fields Markov types conservation laws linear diophantine equations enumerative combinatorics analytic and discrete geometry

来源：评论

学校读者我要写书评

暂无评论

Asymptotics of classical spin networks

引用

GEOMETRY & TOPOLOGY 2013年第1期17卷 1-37页

作者： Garoufalidis, Stavros van der Veen, Roland Georgia Inst Technol Sch Math Atlanta GA 30332 USA Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Max Planck Inst Math D-53111 Bonn Germany

A spin network is a cubic ribbon graph labeled by representations of SU(2). Spin networks are important in various areas of Mathematics (3-dimensional Quantum Topology), Physics (Angular Momentum, Classical and Quantum Gravity) and Chemistry (Atomic Spectroscopy). The evaluation of a spin network is an integer number. The main results of our paper are: (a) an existence theorem for the asymptotics of evaluations of arbitrary spin networks (using the theory of G-functions), (b) a rationality property of the generating series of all evaluations with a fixed underlying graph (using the combinatorics of the chromatic evaluation of a spin network), (c) rigorous effective computations of our results for some 6j-symbols using the Wilf-Zeilberger theory and (d) a complete analysis of the regular Cube 12j spin network (including a nonrigorous guess of its Stokes constants), in the appendix.

关键词： Spin networks ribbon graphs $6j$–symbols Racah coefficients angular momentum asymptotics G-functions Kauffman bracket Jones polynomial Wilf-Zeilberger method Borel transform enumerative combinatorics recoupling Nilsson

来源：评论

学校读者我要写书评

暂无评论

A Hardy-Ramanujan formula for lie algebras

引用

EXPERIMENTAL MATHEMATICS 2007年第3期16卷 375-384页

作者： Ritter, Gordon Harvard Univ Dept Phys Cambridge MA 02138 USA

We study certain combinatoric aspects of the set of all unitary representations of a finite-dimensional semisimple Lie algebra g. We interpret the Hardy-Ramanujan-Rademacher formula for the integer partition function as a statement about su(2), and explore in some detail the generalization to other Lie algebras. We conjecture that the number Mod(g, d) of g-modules in dimension d is given by (alpha/d) exp(beta d(gamma)) for d >> 1, which (if true) has profound consequences for other combinatorial invariants of g-modules. In particular, the fraction F-1(g, d) of d-dimensional g-modules that have a one-dimensional submodule is determined by the generating function for Mod(g, d). The dependence of F-1(g, d) on d is complicated and beautiful, depending on the congruence class of d mod n and on generating curves that resemble a double helix within a given congruence class. We also consider the total number of repeated irreducible summands in the direct sum decomposition as a function on the space of all g-modules in a fixed dimension, and plot its histogram. This is related to the concept (used in quantum information theory) of noiseless subsystem. We identify a simple function that is conjectured to be the asymptotic form of the aforementioned histogram, and verify numerically that this is correct for su(n).

关键词： enumerative combinatorics representation theory

来源：评论

学校读者我要写书评

暂无评论

On the composition of an arbitrary collection of SU(2) spins: an enumerative combinatoric approach

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2018年第10期51卷 105202-105202页

作者： Gyamfi, J. A. Barone, V. Scuola Normale Super Pisa Piazza Cavalieri 7 I-56126 Pisa Italy

The whole enterprise of spin compositions can be recast as simple enumerative combinatoric problems. We show here that enumerative combinatorics (Stanley 2011 enumerative combinatorics (Cambridge Studies in Advanced Mathematics vol 1) (Cambridge: Cambridge University Press)) is a natural setting for spin composition, and easily leads to very general analytic formulae-many of which hitherto not present in the literature. Based on it, we propose three general methods for computing spin multiplicities;namely, (1) the multi-restricted composition, (2) the generalized binomial and (3) the generating function methods. Symmetric and anti-symmetric compositions of SU(2) spins are also discussed, using generating functions. Of particular importance is the observation that while the common Clebsch-Gordan decomposition-which considers the spins as distinguishable-is related to integer compositions, the symmetric and anti-symmetric compositions (where one considers the spins as indistinguishable) are obtained considering integer partitions. The integers in question here are none other than the occupation numbers of the Holstein-Primakoff bosons. The pervasiveness of q-analogues in our approach is a testament to the fundamental role they play in spin compositions. In the appendix, some new results in the power series representation of Gaussian polynomials (or q-binomial coefficients)-relevant to symmetric and antisymmetric compositions-are presented.

关键词： spin composition Clebsch-Gordan series Holstein-Primakoff bosons enumerative combinatorics integer composition integer partition q-analogues

来源：评论

学校读者我要写书评

暂无评论

Exploring Discrete Mathematics with American Football

引用

PRIMUS 2015年第5期25卷 421-438页

作者： Muldoon Brown, Tricia Kahn, Eric B. Armstrong State University Savannah GA United States Kenyon College Gambier OH United States University of Kentucky Lexington KY United States

Abstract: This paper presents an extended project that offers, through American football, an application of concepts from enumerative combinatorics and an introduction to proofs course. The questions in this paper and subsequent details concerning equivalence relations and counting techniques can be used to reinforce these new topics to students in such a transition-to-proofs-type course or to offer an application of known theoretical mathematics to students with more advanced understanding in the major. © , Copyright © Taylor & Francis Group, LLC.

关键词： Abstract algebra discrete mathematics enumerative combinatorics football

来源：评论

学校读者我要写书评

暂无评论

Twin-Width IV: Ordered Graphs and Matrices* 2022

Twin-Width IV: Ordered Graphs and Matrices*

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bonnet, Edouard Giocanti, Ugo de Mendez, Patrice Ossona Simon, Pierre Thomasse, Stephan Torunczyk, Szymon ENS Lyon Lip UMR5668 Lyon France CAMS CNRS UMR 8557 Lyon France Univ Calif Berkeley Berkeley CA USA Univ Warsaw Warsaw Poland

ISBN: (纸本)9781450392648

We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh, Bollobas, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles our small conjecture [SODA '21] in the case of ordered graphs.

关键词： Twin-width matrices ordered graphs enumerative combinatorics model theory algorithms computational complexity Ramsey theory

来源：评论

学校读者我要写书评

暂无评论

Trajectories and Traces on Non-traditional Regular Tessellations of the Plane 18th

引用

18th International Workshop on Combinatorial Image Analysis (IWCIA)

作者： Nagy, Benedek Akkeles, Arif Eastern Mediterranean Univ Fac Arts & Sci Dept Math Mersin 10 Famagusta North Cyprus Turkey

ISBN: (纸本)9783319591087;9783319591070

In this paper, shortest paths on two regular tessellations, on the hexagonal and on the triangular grids, are investigated. The shortest paths (built by steps to neighbor pixels) between any two points (cells, pixels) are described as traces and generalized traces on these grids, respectively. In the hexagonal grid, there is only one type of usual neighborhood and at most two directions of the steps are used in any shortest paths, and thus, the number of linearizations of these traces is easily computed by a binomial coefficient based on the coordinate differences of the pixels. Opposite to this, in the triangular grid the neighborhood is inhomogeneous (there are three types of neighborhood), moreover this grid is not a lattice, therefore, the possible shortest paths form more complicated sets, a kind of generalized traces. The linearizations of these sets are described by associative rewriting systems, and, as a main combinatorial result, the number of the shortest paths are computed between two triangles, where two cells are considered adjacent if they share at least one vertex.

关键词： combinatorics Traces Trajectories Non-traditional grids Triangular grid Generalized traces Shortest paths Number of shortest paths enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Enumeration and Generating Functions of Differential Rota-Baxter Words

引用

MATHEMATICS IN COMPUTER SCIENCE 2010年第2-3期4卷 339-358页

作者： Guo, Li Sit, William Y. Rutgers State Univ Dept Math & Comp Sci Newark NJ 07102 USA CUNY City Coll Dept Math New York NY 10031 USA

In this paper, the methods and results in enumeration and generation of Rota-Baxter words in Guo and Sit (Algebraic and Algorithmic Aspects of Differential and Integral Operators (AADIOS), Math. Comp. Sci., vol. 4, Sp. Issue (2,3), 2011) are generalized and applied to a free, non-commutative, non-unitary, ordinary differential Rota-Baxter algebra with one generator. A differential Rota-Baxter algebra is an associative algebra with two operators modeled after the differential and integral operators, which are related by the First Fundamental Theorem of Calculus. Differential Rota-Baxter words are words formed by concatenating differential monomials in the generator with images of words under the Rota-Baxter operator. Their totality is a canonical basis of a free, non-commutative, non-unitary, ordinary differential Rota-Baxter algebra. A free differential Rota-Baxter algebra can be constructed from a free Rota-Baxter algebra on a countably infinite set of generators. The order of the derivation gives another dimension of grading on differential Rota-Baxter words, enabling us to generalize and refine results from Guo and Sit to enumerate the set of differential Rota-Baxter words and outline an algorithm for their generation according to a multi-graded structure. Enumeration of a basis is often a first step to choosing a data representation in implementation of algorithms involving free algebras, and in particular, free differential Rota-Baxter algebras and several related algebraic structures on forests and trees. The generating functions obtained can be used to provide links to other combinatorial structures.

关键词： Differential Rota-Baxter words Differential Rota-Baxter algebras Generating functions Compositions Colorings enumerative combinatorics

来源：评论

学校读者我要写书评

暂无评论

Characterisation of symmetries of unlabelled triangulations

引用

Electronic Notes in Discrete Mathematics 2015年 49卷 587-594页

作者： Kang, M. Sprüssel, P. Institute of Optimization and Discrete Mathematics Graz University of Technology Graz Austria

We derive a constructive decomposition of unlabelled triangulations by giving a full characterisation of their symmetries. This result will enable us to deduce a complete enumerative description of unlabelled cubic pl... 详细信息

关键词： enumerative combinatorics Graph automorphisms Triangulations

来源：评论

学校读者我要写书评

暂无评论

Terminal chords in connected chord diagrams

引用

ANNALES DE L INSTITUT HENRI POINCARE D 2017年第4期4卷 417-452页

作者： Courtiel, Julien Yeats, Karen Univ Paris 13 LIPN Inst Galilee Villetaneuse France Univ Waterloo Combinator & Optimizat Waterloo ON N2L 3G1 Canada

Rooted connected chord diagrams form a nice class of combinatorial objects. Recently they were shown to index solutions to certain Dyson-Schwinger equations in quantum field theory. Key to this indexing role are certain special chords which are called terminal chords. Terminal chords provide a number of combinatorially interesting parameters on rooted connected chord diagrams which have not been studied previously. Understanding these parameters better has implications for quantum field theory. Specifically, we show that the distributions of the number of terminal chords and the number of adjacent terminal chords are asymptotically Gaussian with logarithmic means, and we prove that the average index of the first terminal chord is 2n/3. Furthermore, we obtain a method to determine any next-to(i) leading log expansion of the solution to these Dyson-Schwinger equations, and have asymptotic information about the coefficients of the log expansions.

关键词： Chord diagrams terminal chords quantum field theory Dyson-Schwinger equations enumerative combinatorics analytic combinatorics

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：