Top 10 Arxiv Papers Today in Combinatorics


2.053 Mikeys
#1. A Note On Universal Point Sets for Planar Graphs
Manfred Scheucher, Hendrik Schrezenmaier, Raphael Steiner
We investigate which planar point sets allow simultaneous straight-line embeddings of all planar graphs on a fixed number of vertices. We first show that $(1.293-o(1))n$ points are required to find a straight-line drawing of each $n$-vertex planar graph (vertices are drawn as the given points); this improves the previous best constant $1.235$ by Kurowski (2004). Our second main result is based on exhaustive computer search: We show that no set of 11 points exists, on which all planar 11-vertex graphs can be simultaneously drawn plane straight-line. This strengthens the result by Cardinal, Hoffmann, and Kusters (2015), that all planar graphs on $n \le 10$ vertices can be simultaneously drawn on particular `universal' sets of $n$ points while there are no universal sets for $n \ge 15$. Moreover, we provide a set of 23 planar 11-vertex graphs which cannot be simultaneously drawn on any set of 11 points. This, in fact, is another step towards a (negative) answer of the question, whether every two planar graphs can be drawn...
more | pdf | html
Figures
None.
Tweets
mathCObot: Manfred Scheucher, Hendrik Schrezenmaier, Raphael Steiner : A Note On Universal Point Sets for Planar Graphs https://t.co/EVysEzBmXC https://t.co/uIAmi7lrmd
MathPaper: A Note On Universal Point Sets for Planar Graphs. https://t.co/bmAlZY6rv7
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10048
Unqiue Words: 2264

2.053 Mikeys
#2. Fault-Tolerant Metric Dimension of $P(n,2)$ with Prism Graph
Z. Ahmad, M. O. Ahmad, A. Q. Baig, M. Naeem
Let $G$ be a connected graph and $d(a,b)$ be the distance between the vertices $a$ and $b$. A subset $U =\{u_1,u_2,\cdots,u_k\}$ of the vertices is called a resolving set for $G$ if for every two distinct vertices $a,b \in V(G)$, there is a vertex $u_\xi \in U$ such that $d(a,u_\xi)\neq d(b,u_\xi)$. A resolving set containing a minimum number of vertices is called a metric basis for $G$ and the number of vertices in a metric basis is its metric dimension denoted by $dim(G)$. A resolving set $U$ for $G$ is fault-tolerant if $U \setminus \{u\}$ is also a resolving set, for each $u \in U$, and the fault-tolerant metric dimension of $G$ is the minimum cardinality of such a set. In this paper we introduce the study of the fault-tolerant metric dimension of $P(n,2)$ with prism graph.
more | pdf | html
Figures
None.
Tweets
mathCObot: Z. Ahmad, M. O. Ahmad, A. Q. Baig, M. Naeem : Fault-Tolerant Metric Dimension of $P(n,2)$ with Prism Graph https://t.co/8TJySuYVKI https://t.co/MgZkEC4JUk
MathPaper: Fault-Tolerant Metric Dimension of $P(n,2)$ with Prism Graph. https://t.co/J8QZ7sOeRD
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 4507
Unqiue Words: 629

2.053 Mikeys
#3. Semi-perfect 1-Factorizations of the Hypercube
Natalie C. Behague
A 1-factorization $\mathcal{M} = \{M_1,M_2,\ldots,M_n\}$ of a graph $G$ is called perfect if the union of any pair of 1-factors $M_i, M_j$ with $i \ne j$ is a Hamilton cycle. It is called $k$-semi-perfect if the union of any pair of 1-factors $M_i, M_j$ with $1 \le i \le k$ and $k+1 \le j \le n$ is a Hamilton cycle. We consider 1-factorizations of the discrete cube $Q_d$. There is no perfect 1-factorization of $Q_d$, but it was previously shown that there is a 1-semi-perfect 1-factorization of $Q_d$ for all $d$. Our main result is to prove that there is a $k$-semi-perfect 1-factorization of $Q_d$ for all $k$ and all $d$, except for one possible exception when $k=3$ and $d=6$. This is, in some sense, best possible. We conclude with some questions concerning other generalisations of perfect 1-factorizations.
more | pdf | html
Figures
None.
Tweets
mathCObot: Natalie C. Behague : Semi-perfect 1-Factorizations of the Hypercube https://t.co/NI3sxujAb5 https://t.co/b9mDN7cemU
MathPaper: Semi-perfect 1-Factorizations of the Hypercube. https://t.co/sSaO4oEoUN
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5501
Unqiue Words: 1206

2.053 Mikeys
#4. Distinguishing number of Urysohn metric spaces
Anthony Bonato, Claude Laflamme, Micheal Pawliuk, Norbert Sauer
The distinguishing number of a structure is the smallest size of a partition of its elements so that only the trivial automorphism of the structure preserves the partition. We show that for any countable subset of the positive real numbers, the corresponding countable Urysohn metric space, when it exists, has distinguishing number two or is infinite. While it is known that a sufficiently large finite primitive structure has distinguishing number two, unless its automorphism group is not the full symmetric group or alternating group, the infinite case is open and these countable Urysohn metric spaces provide further confirmation toward the conjecture that all primitive homogeneous countably infinite structures have distinguishing number two or else is infinite.
more | pdf | html
Figures
None.
Tweets
mathCObot: Anthony Bonato, Claude Laflamme, Micheal Pawliuk, Norbert Sauer : Distinguishing number of Urysohn metric spaces https://t.co/RLvhxob1TC https://t.co/TEcSsAnbwd
MathPaper: Distinguishing number of Urysohn metric spaces. https://t.co/BgZct2NamP
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9865
Unqiue Words: 1573

2.053 Mikeys
#5. Chordal circulant graphs and induced matching number
Francesco Romeo
Let $G=C_{n}(S)$ be a circulant graph on $n$ vertices. In this paper we characterize chordal circulant graphs and then we compute $\nu (G)$, the induced matching number of $G$. These latter are useful in bounding the Castelnuovo-Mumford regularity of the edge ring of $G$.
more | pdf | html
Figures
None.
Tweets
mathCObot: Francesco Romeo : Chordal circulant graphs and induced matching number https://t.co/uGexRBraS8 https://t.co/MBF8lggdHM
MathPaper: Chordal circulant graphs and induced matching number. https://t.co/8UaDd8puZP
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 4271
Unqiue Words: 956

2.053 Mikeys
#6. On Graphs with equal Dominating and C-dominating energy
S. M. Hosamani, V. B. Awati, R. M. Honmore
Graph energy and Domination in graphs are most studied areas of graph theory. In this paper we made an attempt to connect these two areas of graph theory by introducing c-dominating energy of a graph $G$. First, we show the chemical applications of c-dominating energy with the help of well known statistical tools. Next, we obtain mathematical properties of c-dominating energy. Finally, we characterize trees, unicyclic graphs, cubic and block graphs with equal dominating and c-dominating energy.
more | pdf | html
Figures
Tweets
mathCObot: S. M. Hosamani, V. B. Awati, R. M. Honmore : On Graphs with equal Dominating and C-dominating energy https://t.co/H33ZIfp3jE https://t.co/yzkzUFSU43
MathPaper: On Graphs with equal Dominating and C-dominating energy. https://t.co/9yF3UQVASe
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 3911
Unqiue Words: 1055

2.053 Mikeys
#7. On Infinite Prefix Normal Words
Ferdinando Cicalese, Zsuzsanna Lipták, Massimiliano Rossi
Prefix normal words are binary words that have no factor with more $1$s than the prefix of the same length. Finite prefix normal words were introduced in [Fici and Lipt\'ak, DLT 2011]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order.
more | pdf | html
Figures
Tweets
mathCObot: Ferdinando Cicalese, Zsuzsanna Lipták, Massimiliano Rossi : On Infinite Prefix Normal Words https://t.co/UgQ4LPGd0T https://t.co/9TLYInqZ3l
MathPaper: On Infinite Prefix Normal Words. https://t.co/suCzJtOnC5
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9368
Unqiue Words: 1765

2.053 Mikeys
#8. Leaf-induced subtrees of leaf-Fibonacci trees
Audace Amen Vioutou Dossou-Olory
In analogy to a concept of Fibonacci trees, we define the leaf-Fibonacci tree of size $n$ and investigate its number of nonisomorphic leaf-induced subtrees. Denote by $f_0$ the one vertex tree and $f_1$ the tree that consists of a root with two leaves attached to it; the leaf-Fibonacci tree $f_n$ of size $n\geq 2$ is the binary tree whose branches are $f_{n-1}$ and $f_{n-2}$. We derive a nonlinear difference equation for the number $\text{N}(f_n)$ of nonisomorphic leaf-induced subtrees (subtrees induced by leaves) of $f_n$, and also prove that $\text{N}(f_n)$ is asymptotic to $1.00001887227319\ldots (1.48369689570172 \ldots)^{\phi^n}$ ($\phi=$~golden ratio) as $n$ grows to infinity.
more | pdf | html
Figures
None.
Tweets
mathCObot: Audace Amen Vioutou Dossou-Olory : Leaf-induced subtrees of leaf-Fibonacci trees https://t.co/p9BOukNOSi https://t.co/UUoGPBxQdu
MathPaper: Leaf-induced subtrees of leaf-Fibonacci trees. https://t.co/Ic62CsOqBo
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3040
Unqiue Words: 832

2.053 Mikeys
#9. On the Further Structure of the Finite Free Convolutions
Jonathan Leake, Nick Ryder
Since the celebrated resolution of Kadison-Singer (via the Paving Conjecture) by Marcus, Spielman, and Srivastava, much study has been devoted to further understanding and generalizing the techniques of their proof. Specifically, their barrier method was crucial to achieving the required polynomial root bounds on the finite free convolution. But unfortunately this method required individual analysis for each usage, and the existence of a larger encapsulating framework is an important open question. In this paper, we make steps toward such a framework by generalizing their root bound to all differential operators. We further conjecture a large class of root bounds, the resolution of which would require for more robust techniques. We further give an important counterexample to a very natural multivariate version of their bound, which if true would have implied tight bounds for the Paving Conjecture.
more | pdf | html
Figures
None.
Tweets
mathCObot: Jonathan Leake, Nick Ryder : On the Further Structure of the Finite Free Convolutions https://t.co/nTLlqLxjLl https://t.co/GS31qQXSYy
MathPaper: On the Further Structure of the Finite Free Convolutions. https://t.co/CAn9XhNgbS
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8017
Unqiue Words: 1806

2.053 Mikeys
#10. Characterising $k$-connected sets in infinite graphs
J. Pascal Gollin, Karl Heuer
A $k$-connected set in an infinite graph, where $k > 0$ is an integer, is a set of vertices such that any two of its subsets of the same size $\ell \leq k$ can be connected by $\ell$ disjoint paths in the whole graph. We characterise the existence of $k$-connected sets of arbitrary but fixed infinite cardinality via the existence of certain minors and topological minors. This characterisation provides an analogue of the Star-Comb Lemma, one of the most-used tools in topological infinite graph theory, for higher connectivity. We also prove a duality theorem for the existence of such $k$-connected sets: if a graph contains no such a $k$-connected set, then it has a tree structure which, whenever it exists, clearly precludes the existence of such a $k$-connected set.
more | pdf | html
Figures
None.
Tweets
mathCObot: J. Pascal Gollin, Karl Heuer : Characterising $k$-connected sets in infinite graphs https://t.co/UbaWHpEVz4 https://t.co/QsulaVv5YG
MathPaper: Characterising $k$-connected sets in infinite graphs. https://t.co/kkQ7Nq4kXJ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 23335
Unqiue Words: 2715

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 57,756 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 57,756 papers.