### Top 10 Arxiv Papers Today in Combinatorics

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 10048
Unqiue Words: 2264

##### #2. Fault-Tolerant Metric Dimension of $P(n,2)$ with Prism Graph
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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 4507
Unqiue Words: 629

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 5501
Unqiue Words: 1206

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9865
Unqiue Words: 1573

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 4271
Unqiue Words: 956

##### #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
###### 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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 3911
Unqiue Words: 1055

##### #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
###### 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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9368
Unqiue Words: 1765

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3040
Unqiue Words: 832

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8017
Unqiue Words: 1806

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 23335
Unqiue Words: 2715

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
Online
###### Stats
Tracking 57,756 papers.