Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial species and graph enumeration
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In enumerative combinatorics, it is often a goal to enumerate both labeled and unlabeled structures of a given type. The theory of combinatorial species is a novel toolset which provides a rigorous foundation for dealing with the distinction between labeled and unlabeled structures. The cycle index series of a species encodes the labeled and unlabeled enumerative data of that species. Moreover, by using species operations, we are able to solve for the cycle index series of one species in terms of other, known cycle indices of other species. Section 3 is an exposition of species theory and Section 4 is an enumeration of point-determining bipartite graphs using this toolset. In Section 5, we extend a result about point-determining graphs to a similar result for point-determining {Phi}-graphs, where {Phi} is a class of graphs with certain properties. Finally, Appendix A is an expository on species computation using the software Sage [9] and Appendix B uses Sage to calculate the cycle index series of point-determining bipartite graphs.
rate research
Read More
A split graph is a graph whose vertices can be partitioned into a clique and a stable set. We investigate the combinatorial species of split graphs, providing species-theoretic generalizations of enumerative results due to Bina and Pv{r}ibil (2015), Cheng, Collins, and Trenk (2016), and Collins and Trenk (2018). In both the labeled and unlabeled cases, we give asymptotic results on the number of split graphs, of unbalanced split graphs, and of bicolored graphs, including proving the conjecture of Cheng, Collins, and Trenk (2016) that almost all split graphs are balanced.
A connected digraph in which the in-degree of any vertex equals its out-degree is Eulerian; this baseline result is used as the basis of existence proofs for universal cycles (also known as ucycles or generalized deBruijn cycles or U-cycles) of several combinatorial objects. The existence of ucycles is often dependent on the specific representation that we use for the combinatorial objects. For example, should we represent the subset ${2,5}$ of ${1,2,3,4,5}$ as 25 in a linear string? Is the representation 52 acceptable? Or it it tactically advantageous (and acceptable) to go with ${0,1,0,0,1}$? In this paper, we represent combinatorial objects as graphs, as in cite{bks}, and exhibit the flexibility and power of this representation to produce {it graph universal cycles}, or {it Gucycles}, for $k$-subsets of an $n$-set; permutations (and classes of permutations) of $[n]={1,2,ldots,n}$, and partitions of an $n$-set, thus revisiting the classes first studied in cite{cdg}. Under this graphical scheme, we will represent ${2,5}$ as the subgraph $A$ of $C_5$ with edge set consisting of ${2,3}$ and ${5,1}$, namely the second and fifth edges in $C_5$. Permutations are represented via their permutation graphs, and set partitions through disjoint unions of complete graphs.
We present new short proofs of known spanning tree enumeration formulae for threshold and Ferrers graphs by showing that the Laplacian matrices of such graphs admit triangular rank-one perturbations. We then characterize the set of graphs whose Laplacian matrices admit triangular rank-one perturbations as the class of special 2-threshold graphs, introduced by Hung, Kloks, and Villaamil. Our work introduces (1) a new characterization of special 2-threshold graphs that generalizes the characterization of threshold graphs in terms of isolated and dominating vertices, and (2) a spanning tree enumeration formula for special 2-threshold graphs that reduces to the aforementioned formulae for threshold and Ferrers graphs. We consider both unweighted and weighted spanning tree enumeration.
We prove an asymptotic formula for the number of orientations with given out-degree (score) sequence for a graph $G$. The graph $G$ is assumed to have average degrees at least $n^{1/3 + varepsilon}$ for some $varepsilon > 0$, and to have strong mixing properties, while the maximum imbalance (out-degree minus in-degree) of the orientation should be not too large. Our enumeration results have applications to the study of subdigraph occurrences in random orientations with given imbalance sequence. As one step of our calculation, we obtain new bounds for the maximum likelihood estimators for the Bradley-Terry model of paired comparisons.
We consider pressing sequences, a certain kind of transformation of graphs with loops into empty graphs, motivated by an application in phylogenetics. In particular, we address the question of when a graph has precisely one such pressing sequence, thus answering an question from Cooper and Davis (2015). We characterize uniquely pressable graphs, count the number of them on a given number of vertices, and provide a polynomial time recognition algorithm. We conclude with a few open questions. Keywords: Pressing sequence, adjacency matrix, Cholesky factorization, binary matrix
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
