Top 10 Arxiv Papers Today in Combinatorics


2.01 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 32880
Unqiue Words: 4206

2.005 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 25852
Unqiue Words: 3031

2.004 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#5. Gončarov Polynomials in Partition Lattices and Exponential Families
Ayomikun Adeniran, Catherine Yan
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
Figures
None.
Tweets
mathCObot: Ayomikun Adeniran, Catherine Yan : Gončarov Polynomials in Partition Lattices and Exponential Families https://t.co/GGzybpT9rm https://t.co/OktxDquuid
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8931
Unqiue Words: 1869

2.004 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8926
Unqiue Words: 1571

2.004 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10157
Unqiue Words: 1818

2.004 Mikeys
#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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#10. Equivalent formulation of Thomassen's conjecture using Tutte paths in claw-free graphs
Adam Kabela, Petr Vrána
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
Figures
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

About

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
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 160,428 papers.