### Top 10 Arxiv Papers Today in Combinatorics

##### #1. Tangles in the social sciences
###### Reinhard Diestel
Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that often occur together. They can thereby identify and discover 'types': of behaviour, views, abilities, dispositions. The mathematical theory of tangles has its origins in the connectivity theory of graphs, which it has transformed over the past 30 years. It has recently been axiomatized in a way that makes its two deepest results applicable to a much wider range of contexts. This expository paper indicates some contexts where this difference of approach is particularly striking. But these are merely examples of such contexts: in principle, it can apply to much of the quantitative social sciences. Our aim here is twofold: to indicate just enough of the theory of tangles to show how this can work in the various different contexts, and to give plenty of different examples illustrating this.
more | pdf | html
None.
###### Tweets
net_science: Tangles in the social sciences. (arXiv:1907.07341v1 [https://t.co/m0fuWYc5xx]) https://t.co/QpVNFA2r4K
mathCObot: Reinhard Diestel : Tangles in the social sciences https://t.co/u9pB6WXQ5V https://t.co/WtvXuYsVmm
frankolken: RT @net_science: Tangles in the social sciences. (arXiv:1907.07341v1 [https://t.co/m0fuWYc5xx]) https://t.co/QpVNFA2r4K
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 32880
Unqiue Words: 4206

##### #2. Motzkin path on RNA abstract shapes
###### Sang Kwan Choi
We consider a certain abstract of RNA secondary structures, which is closely related to RNA shapes. The generating function counting the number of the abstract structures is obtained by means of Narayana numbers and 2-Motzkin paths, through which we provide an identity related to Narayana numbers and Motzkin polynomials. Furthermore, we show that a combinatorial interpretation on 2-Motzkin paths leads to the correspondence between 1-Motkzin paths and RNA shapes, which facilitates probing further classifications or abstractions of the shapes. In this paper, we classify the shapes with respect to the number of components and calculate their asymptotic distributions.
more | pdf | html
None.
###### Tweets
mathCObot: Sang Kwan Choi : Motzkin path on RNA abstract shapes https://t.co/OadnAqI8cd https://t.co/7ijGEZAQjZ
BioPapers: Motzkin path on RNA abstract shapes. https://t.co/mWC0G00Rr8
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #3. The fundamental theorem of finite semidistributive lattices
###### Nathan Reading, David E Speyer, Hugh Thomas
We prove a Fundamental Theorem of Finite Semidistributive Lattices (FTFSDL), modelled on Birkhoff's Fundamental Theorem of Finite Distributive Lattices. Our FTFSDL is of the form "A poset L is a finite semidistributive lattice if and only if there exists a set Sha with some additional structure, such that L is isomorphic to the admissible subsets of Sha ordered by inclusion; in this case, Sha and its additional structure are uniquely determined by L." The additional structure on Sha is a combinatorial abstraction of the notion of torsion pairs from representation theory and has geometric meaning in the case of posets of regions of hyperplane arrangements. We show how the FTFSDL clarifies many constructions in lattice theory, such as canonical join representations and passing to quotients, and how the semidistributive property interacts with other major classes of lattices. Many of our results also apply to infinite lattices.
more | pdf | html
None.
###### Tweets
mathCObot: Nathan Reading, David E Speyer, Hugh Thomas : The fundamental theorem of finite semidistributive lattices https://t.co/NvNQjPxyEu https://t.co/WTReAwijj7
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 25852
Unqiue Words: 3031

##### #4. Hamiltonian and Pseudo-Hamiltonian Cycles and Fillings In Simplicial Complexes
###### Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad
We introduce and study a $d$-dimensional generalization of Hamiltonian cycles in graphs - the Hamiltonian $d$-cycles in $K_n^d$ (the complete simplicial $d$-complex over a vertex set of size $n$). Those are the simple $d$-cycles of a complete rank, or, equivalently, of size $1 + {{n-1} \choose d}$. The discussion is restricted to the fields $F_2$ and $Q$. For $d=2$, we characterize the $n$'s for which Hamiltonian $2$-cycles exist. For $d=3$ it is shown that Hamiltonian $3$-cycles exist for infinitely many $n$'s. In general, it is shown that there always exist simple $d$-cycles of size ${{n-1} \choose d} - O(n^{d-3})$. All the above results are constructive. Our approach naturally extends to (and in fact, involves) $d$-fillings, generalizing the notion of $T$-joins in graphs. Given a $(d-1)$-cycle $Z^{d-1} \in K_n^d$, ~$F$ is its $d$-filling if $\partial F = Z^{d-1}$. We call a $d$-filling Hamiltonian if it is acyclic and of a complete rank, or, equivalently, is of size ${{n-1} \choose d}$. If a Hamiltonian $d$-cycle $Z$ over...
more | pdf | html
None.
###### Tweets
mathCObot: Rogers Mathew, Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad : Hamiltonian and Pseudo-Hamiltonian Cycles and Fillings In Simplicial Complexes https://t.co/lpv7roldQu https://t.co/CSVtYy8iWW
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

##### #5. Gončarov Polynomials in Partition Lattices and Exponential Families
Classical Gon\v{c}arov polynomials arose in numerical analysis as a basis for the solutions of the Gon\v{c}arov interpolation problem. These polynomials provide a natural algebraic tool in the enumerative theory of parking functions. By replacing the differentiation operator with a delta operator and using the theory of finite operator calculus, Lorentz, Tringali and Yan introduced the sequence of generalized Gon\v{c}arov polynomials associated to a pair $(\Delta, Z)$ of a delta operator $\Delta$ and an interpolation grid $Z$. Generalized Gon\v{c}arov polynomials share many nice algebraic properties and have a connection with the theories of binomial enumeration and order statistics. In this paper we give a complete combinatorial interpretation for any sequence of generalized Gon\v{c}arov polynomials. First, we show that they can be realized as weight enumerators in partition lattices. Then, we give a more concrete realization in exponential families and show that these polynomials enumerate various enriched structures of vector...
more | pdf | html
None.
###### Tweets
mathCObot: Ayomikun Adeniran, Catherine Yan : Gončarov Polynomials in Partition Lattices and Exponential Families https://t.co/GGzybpT9rm https://t.co/OktxDquuid
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8931
Unqiue Words: 1869

##### #6. On the equality of domination number and $2$-domination number
###### Gülnaz Boruzanlı Ekinci, Csilla Bujtás
The 2-domination number $\gamma_2(G)$ of a graph $G$ is the minimum cardinality of a set $D \subseteq V(G)$ for which every vertex outside $D$ is adjacent to at least two vertices in $D$. Clearly, $\gamma_2(G)$ cannot be smaller than the domination number $\gamma(G)$. We consider a large class of graphs and characterize those members which satisfy $\gamma_2=\gamma$. For the general case, we prove that it is NP-hard to decide whether $\gamma_2=\gamma$ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.
more | pdf | html
###### Tweets
mathCObot: Gülnaz Boruzanlı Ekinci, Csilla Bujtás : On the equality of domination number and $2$-domination number https://t.co/GsQrYltDmj https://t.co/cX8nxw8EDg
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8926
Unqiue Words: 1571

##### #7. Irreducible Generalized Numerical Semigroups and uniqueness of the Frobenius element
###### Carmelo Cisto, Gioia Failla, Chris Peterson, Rosanna Utano
Let $\mathbb{N}^{d}$ be the $d$-dimensional monoid of non-negative integers. A generalized numerical semigroup is a submonoid $S\subseteq \mathbb{N}^d$ such that $H(S)=\mathbb{N}^d \setminus S$ is a finite set. We introduce irreducible generalized numerical semigroups and characterize them in terms of the cardinality of a special subset of $H(S)$. In particular, we describe relaxed monomial orders on $\mathbb N^d$, define the Frobenius element of $S$ with respect to a given relaxed monomial order, and show that the Frobenius element of $S$ is independent of the order if the generalized numerical semigroup is irreducible.
more | pdf | html
None.
###### Tweets
mathCObot: Carmelo Cisto, Gioia Failla, Chris Peterson, Rosanna Utano : Irreducible Generalized Numerical Semigroups and uniqueness of the Frobenius element https://t.co/NIMPESgtMh https://t.co/B4ubdqsiT9
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

##### #8. MRD-codes arising from the trinomial $x^q+x^{q^3}+cx^{q^5}\in\mathbb{F}_{q^6}[x]$
###### Giuseppe Marino, Maria Montanucci, Ferdinando Zullo
In [10], the existence of $\mathbb{F}_q$-linear MRD-codes of $\mathbb{F}_q^{6\times 6}$, with dimension $12$, minimum distance $5$ and left idealiser isomorphic to $\mathbb{F}_{q^6}$, defined by a trinomial of $\mathbb{F}_{q^6}[x]$, when $q$ is odd and $q\equiv 0,\pm 1\pmod 5$, has been proved. In this paper we show that this family produces $\mathbb{F}_q$-linear MRD-codes of $\mathbb{F}_q^{6\times 6}$, with the same properties, also in the remaining $q$ odd cases, but not in the $q$ even case. These MRD-codes are not equivalent to the previously known MRD-codes. We also prove that the corresponding maximum scattered $\mathbb{F}_q$-linear sets of $\mathrm{PG}(1,q^6)$ are not $\mathrm{P}\Gamma\mathrm{L}(2,q^6)$-equivalent to any previously known scattered linear set.
more | pdf | html
None.
###### Tweets
mathCObot: Giuseppe Marino, Maria Montanucci, Ferdinando Zullo : MRD-codes arising from the trinomial $x^q+x^{q^3}+cx^{q^5}\in\mathbb{F}_{q^6}[x]$ https://t.co/agc0u5Kq7D https://t.co/JYWkJll3gY
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10157
Unqiue Words: 1818

##### #9. The relation between the independence number and rank of a signed graph
###### Shengjie He, Rong-Xia Hao
A signed graph $(G, \sigma)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $(G, \sigma)$. Let $c(G)$, $\alpha(G)$ and $r(G, \sigma)$ be the cyclomatic number, the independence number and the rank of the adjacency matrix of $(G, \sigma)$, respectively. In this paper, we study the relation among the independence number, the rank and the cyclomatic number of a signed graph $(G, \sigma)$ with order $n$, and prove that $2n-2c(G) \leq r(G, \sigma)+2\alpha(G) \leq 2n$. Furthermore, the signed graphs that reaching the lower bound are investigated.
more | pdf | html
None.
###### Tweets
mathCObot: Shengjie He, Rong-Xia Hao : The relation between the independence number and rank of a signed graph https://t.co/RJ8BHhoKuz https://t.co/L2oMhgA97K
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #10. Equivalent formulation of Thomassen's conjecture using Tutte paths in claw-free graphs
We continue studying Thomassen's conjecture (every 4-connected line graph has a Hamilton cycle) in the direction of a recently shown equivalence with Jackson's conjecture (every 2-connected claw-free graph has a Tutte cycle), and we extend the equivalent formulation as follows: In each connected claw-free graph, every two vertices are connected by a maximal path which is a Tutte path.
more | pdf | html
None.
###### Tweets
mathCObot: Adam Kabela, Petr Vrána : Equivalent formulation of Thomassen's conjecture using Tutte paths in claw-free graphs https://t.co/hu8ndzUaEk https://t.co/umJrWGqSfA
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 160,428 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 160,428 papers.