Hasil untuk "math.CO"

Johann Cigler

We show that the q-Narayana numbers for q=-1 count symmetric Dyck paths according to the number of their valleys.

Rafael Díaz

We build a continuous analogue for Young diagrams, thought of as left-aligned stairs, following the line of research initiated by Díaz and Cano on the construction of continuous analogues for combinatorial objects.

Mugdha Mahesh Pokharanakar

The higher-order Cheeger inequalities were established for graphs by Lee, Oveis Gharan and Trevisan. We prove analogous inequalities for graphons in this article.

Eric Katz

We give an exposition of the proof of the lower bound part of the $g$-theorem for simplicial spheres by Adiprasito, Papadakis, and Petrotou.

Johan Nilsson

We give exact formulas for the number of distinct triangular patterns (or subtriangles) of a given size that occur in the Sierpiński Triangle.

Vuong Bui

In this short note, we prove Hadwiger's conjecture for strongly monotypic polytopes.

Mykola Pochekai

We prove that the Ehrhart $h^*$-vector is unimodal for unimodular triangulations whose boundary is an induced subcomplex.

Helmut Prodinger

Carlitz-compositions follow the restrictions of neighbouring parts $σ_{i-1}\neqσ_{i}$. The recently introduced Arndt-compositions have to satisfy $σ_{2i-1}>σ_{2i}$. The two concepts are combined to new and exciting objects that we call Arndt-Carlitz compositions.

Askar Dzhumadil'daev

We prove that symmetry group of the pfaffian polynomial of a symmetric matrix is a dihedral group. We calculate pfaffians of symmetric matrices with components $(x_i-x_j)^2$ and $\cos(x_i-x_j)$ for $i<j.$

Bogdan Nica

We discuss an algebraic identity, due to Sylvester, as well as related algebraic identities and applications.

Ev Sotnikova, Alexandr Valyuzhenich

In this work we present a survey of results on the problem of finding the minimum cardinality of the support of eigenfunctions of graphs.

Youngjin Bae

The Frame-Stewart conjecture states the least number of moves to solve a generalized Tower of Hanoi problem, of n disks and p pegs. In this paper, we prove a weaker version of the Frame-Stewart conjecture.

Sara Billey, Matjaz Konvalinka, Frderick Matsen IV

Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with n matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with n leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared.

Hortensia Galeana-Sanchez, Hugo Rincon-Galeana, Ricardo Strausz

We prove that, if every cycle of $D$ is an $H$-cycle, then $D$ has an $H$-kernel by walks.

Christophe Picouleau

For every $n\ge 3$ we determine the minimum number of edges of graph with $n$ vertices such that for any non edge $xy$ there exits a hamiltonian cycle containing $xy$.

R. M. Causey, C. Doebele

We prove a sharp structural result concerning finite colorings of pairs in well-founded trees.

Ilker Akkus, Gonca Kizilaslan

In this paper, we give some properties of the Tribonacci and Tribonacci-Lucas quaternions and obtain some identities for them.

Rene Rühr

We give a counterexample to a conjecture stated in Linial and London 2006 regarding expansion on $\mathbb{T}^2$ under $\begin{bmatrix}1&1\\ 0&1\end{bmatrix}$ and $\begin{bmatrix}1&0\\ 1&1\end{bmatrix}$.

Mireille Bousquet-Mélou, Kerstin Weller

Let $\mathcal{A}$ be a minor-closed class of labelled graphs, and let $G_n$ be a random graph sampled uniformly from the set of n-vertex graphs of $\mathcal{A}$. When $n$ is large, what is the probability that $G_n$ is connected? How many components does it have? How large is its biggest component? Thanks to the work of McDiarmid and his collaborators, these questions are now solved when all excluded minors are 2-connected. Using exact enumeration, we study a collection of classes $\mathcal{A}$ excluding non-2-connected minors, and show that their asymptotic behaviour is sometimes rather different from the 2-connected case. This behaviour largely depends on the nature of the dominant singularity of the generating function $C(z)$ that counts connected graphs of $\mathcal{A}$. We classify our examples accordingly, thus taking a first step towards a classification of minor-closed classes of graphs. Furthermore, we investigate a parameter that has not received any attention in this context yet: the size of the root component. This follows non-gaussian limit laws (beta and gamma), and clearly deserves a systematic investigation.

Jacek Cichoń, Zbigniew Gołębiewski

In the paper we discuss a technology based on Bernstein polynomials of asymptotic analysis of a class of binomial sums that arise in information theory. Our method gives a quick derivation of required sums and can be generalized to multinomial distributions. As an example we derive a formula for the entropy of multinomial distributions. Our method simplifies previous work of Jacquet, Szpankowski and Flajolet from 1999.