1,720,987 research outputs found
The k-assignment polytope
No full textIn this paper we Study the structure of the k-assignment polytope, whose vertices are the m x n (0, 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. A representation of the faces by certain bipartite graphs is given. This tool is used to describe the properties of the polytope, especially a complete description of the cover relation in the face poset of the polytope and an exact expression for the diameter. An ear decomposition of these bipartite graphs is constructed.Original Publication:Jonna Gill and Svante Linusson, The k-assignment polytope, 2009, DISCRETE OPTIMIZATION, (6), 2, 148-161.http://dx.doi.org/10.1016/j.disopt.2008.10.003Copyright: Elsevier Science B.V. Amsterdamhttp://www.elsevier.com
The Number Of M-Sequences And f-Vectors
No full text. We give a recursive formula for the number of M-sequences (a.k.a. f-vectors for multicomplexes or O-sequences) given the number of variables and a maximum degree. In particular, it is shown that the number of M-sequences for at most 2 variables are powers of two and for at most 3 variables are Bell numbers. We give an asymptotic estimate of the number of M-sequences when the number of variables is fixed. This leads to a new lower bound for the number of polytopes with few vertices. We also prove a similar recursive formula for the number of f-vectors for simplicial complexes. Keeping the maximum degree fixed we get the number of M-sequences and the number of f-vectors for simplicial complexes as polynomials in the number of variables and it is shown that these numbers are asymptotically equal. 1. Introduction A multicomplex is a collection M of finite multisets satisfying A ` B 2 M =) A 2 M. It is often convenient to think of the underlying ground set as variables and of the sets i..
Extended Pattern Avoidance
No full textA 0-1 matrix is said to be extendably ø-avoiding if it can be the upper left corner of a ø-avoiding permutation matrix. This concept arose in [EL], where the surprising result that the number of extendably 321-avoiding rectangles are enumerated by the ballot numbers was proved. Here we study the other five patterns of length three. The main result is that the six patterns of length three divides into only two cases, no easy symmetry can explain this. An other result is that the Simion-Schmidt-West-bijection for permutations avoiding patterns 12ø and 21ø works also for extended pattern avoidance. The results and proofs use many properties of the Catalan numbers and refinements of the Catalan numbers. Keywords: avoiding pattern, Catalan number, ballot number 1. Introduction 1.1. Notation. Given a permutation ß 2 S n , let it be represented by a permutation matrix, with 1's in positions (i; ß(i)). Fix any t of these 1's and delete all rows and columns that do not contain any of them. Th..
A note on correlations in randomly oriented graphs
No full textAbstract. Given a graph G, we consider the model where G is given a random orientation by giving each edge a random direction. It is proven that for a, b, s ∈ V (G), the events {s → a} and {s → b} are positively correlated. This correlation persists, perhaps unexpectedly, also if we first condition on {s t} for any vertex t = s. With this conditioning it is also true that {s → b} and {a → t} are negatively correlated. A concept of increasing events in random orientations is defined and a general inequality corresponding to Harris inequality is given. The results are obtained by combining a very useful lemma by Colin McDiarmid which relates random orientations with edge percolation, with results by van den Berg, Häggström, Kahn on correlation inequalities for edge percolation. The results are true also for another model of randomly directed graphs
Extending from bijections between marked occurrences of patterns to all occurrences of patterns
Get PDFInternational audienceWe consider two recent open problems stating that certain statistics on various sets of combinatorial objects are equidistributed. The first, posed by Anders Claesson and Svante Linusson, relates nestings in matchings on to occurrences of a certain pattern in permutations in . The second, posed by Miles Jones and Jeffrey Remmel, relates occurrences of a large class of consecutive permutation patterns to occurrences of the same pattern in the cycles of permutations. We develop a general method that solves both of these problems and many more. We further employ the Garsia-Milne involution principle to obtain purely bijective proofs of these results.Nous considérons deux derniers problèmes ouverts indiquant que certaines statistiques sur les divers ensembles d'objets combinatoires sont équiréparties. La première, posée par Anders Claesson et Svante Linusson, concerne les imbrications dans des filtrages sur pour les occurrences d'un certain modèle de permutations dans . La seconde, posée par Miles Jones et Jeffrey Remmel, concerne les occurrences d'une large classe de schémas de permutation consécutive aux évènements du même modèle dans les cycles de permutations. Nous développons une méthode générale qui résout ces deux problèmes et beaucoup plus. Nous avons également utiliser le principe d'involution Garsia-Milne pour obtenir des preuves purement bijectives de ces résultats
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
