### Top 10 Arxiv Papers Today in Combinatorics

##### #1. New results relating independence and matchings
###### Yair Caro, Randy Davila, Ryan Pepper
In this paper we study relationships between the \emph{matching number}, written $\mu(G)$, and the \emph{independence number}, written $\alpha(G)$. Our first main result is to show $\alpha(G) \le \mu(G) + |X| - \mu(G[N_G[X]]),$ where $X$ is \emph{any} intersection of maximum independent sets in $G$. Our second main result is to show $\delta(G)\alpha(G) \le \Delta(G)\mu(G),$ where $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum vertex degrees of $G$, respectively. These results improve on and generalize known relations between $\mu(G)$ and $\alpha(G)$. Further, we also give examples showing these improvements.
more | pdf | html
None.
###### Tweets
mathCObot: Yair Caro, Randy Davila, Ryan Pepper : New results relating independence and matchings https://t.co/dwVLZX9iGx https://t.co/jtcMvG2IBe
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #2. Block-avoiding point sequencings of Mendelsohn triple systems
###### Donald L. Kreher, Douglas R. Stinson, Shannon Veitch
A cyclic ordering of the points in a Mendelsohn triple system of order $v$ (or MTS$(v)$) is called a sequencing. A sequencing $D$ is $\ell$-good if there does not exist a triple $(x,y,z)$ in the MTS$(v)$ such that (1) the three points $x,y,$ and $z$ occur (cyclically) in that order in $D$; and (2) $\{x,y,z\}$ is a subset of $\ell$ cyclically consecutive points of $D$. In this paper, we prove some upper bounds on $\ell$ for MTS$(v)$ having $\ell$-good sequencings and we prove that any MTS$(v)$ with $v \geq 7$ has a $3$-good sequencing. We also determine the optimal sequencings of every MTS$(v)$ with $v \leq 10$.
more | pdf | html
None.
###### Tweets
mathCObot: Donald L. Kreher, Douglas R. Stinson, Shannon Veitch : Block-avoiding point sequencings of Mendelsohn triple systems https://t.co/MEtPmgrdGJ https://t.co/GnkRHseIqM
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #3. Poset Ramsey Numbers for Boolean Lattices
A subposet $Q'$ of a poset $Q$ is a \textit{copy of a poset} $P$ if there is a bijection $f$ between elements of $P$ and $Q'$ such that $x \le y$ in $P$ iff $f(x) \le f(y)$ in $Q'$. For posets $P, P'$, let the \textit{poset Ramsey number} $R(P,P')$ be the smallest $N$ such that no matter how the elements of the Boolean lattice $Q_N$ are colored red and blue, there is a copy of $P$ with all red elements or a copy of $P'$ with all blue elements. Axenovich and Walzer introduced this concept in \textit{Order} (2017), where they proved $R(Q_2, Q_n) \le 2n + 2$ and $R(Q_n, Q_m) \le mn + n + m$, where $Q_n$ is the Boolean lattice of dimension $n$. They later proved $2n \le R(Q_n, Q_n) \le n^2 + 2n$. Walzer later proved $R(Q_n, Q_n) \le n^2 + 1$. We provide some improved bounds for $R(Q_n, Q_m)$ for various $n,m \in \mathbb{N}$. In particular, we prove that $R(Q_n, Q_n) \le n^2 - n + 2$, $R(Q_2, Q_n) \le \frac{5}{3}n + 2$, and $R(Q_3, Q_n) \le \frac{37}{16}n + \frac{39}{16}$. We also prove that $R(Q_2,Q_3) = 5$, and $R(Q_m, Q_n) \le (m -... more | pdf | html ###### Figures None. ###### Tweets mathCObot: Linyuan Lu, Joshua C. Thompson : Poset Ramsey Numbers for Boolean Lattices https://t.co/fIOibgCGRp https://t.co/hMDiEBITa3 ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 2 Total Words: 0 Unqiue Words: 0 ###### 2.025 Mikeys ##### #4. The Newton polytope of the discriminant of a quaternary cubic form ###### Lars Kastner, Robert Loewe We determine the$166\,104$extremal monomials of the discriminant of a quaternary cubic form. These are in bijection with$D$-equivalence classes of regular triangulations of the$3$-dilated tetrahedron. We describe how to compute these triangulations and their$D$-equivalence classes in order to arrive at our main result. The computation poses several challenges, such as dealing with the sheer amount of triangulations effectively, as well as devising a suitably fast algorithm for computation of a$D$-equivalence class. more | pdf | html ###### Figures None. ###### Tweets mathCObot: Lars Kastner, Robert Loewe : The Newton polytope of the discriminant of a quaternary cubic form https://t.co/NppMgZogNH https://t.co/agPt6xqRn3 ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 2 Total Words: 0 Unqiue Words: 0 ###### 2.025 Mikeys ##### #5. Crescent configurations in normed spaces ###### Sara Fish, Dylan King, Steven J. Miller, Eyvindur A. Palsson, Catherine Wahlenmayer We study the problem of crescent configurations, posed by Erd\H{o}s in 1989. A crescent configuration is a set of$n$points in the plane such that: 1) no three points lie on a common line, 2) no four points lie on a common circle, 3) for each$1 \leq i \leq n - 1$, there exists a distance which occurs exactly$i$times. Constructions of sizes$n \leq 8$have been provided by Liu, Pal\'{a}sti, and Pomerance. Erd\H{o}s conjectured that there exists some$N$for which there do not exist crescent configurations of size$n$for all$n \geq N$. We extend the problem of crescent configurations to general normed spaces$(\mathbb{R}^2, \| \cdot \|)$by studying strong crescent configurations in$\| \cdot \|$. In an arbitrary norm$\|\cdot \|$, we construct a strong crescent configuration of size 4. We also construct larger strong crescent configurations in the Euclidean, taxicab, and Chebyshev norms, of sizes$n \leq 6$,$n \leq 7$, and$n \leq 8$respectively. When defining strong crescent configurations, we introduce the notion of... more | pdf | html ###### Figures None. ###### Tweets mathCObot: Sara Fish, Dylan King, Steven J. Miller, Eyvindur A. Palsson, Catherine Wahlenmayer : Crescent configurations in normed spaces https://t.co/uXJfkoX5XE https://t.co/NOclwf6yVr ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 5 Total Words: 0 Unqiue Words: 0 ###### 2.025 Mikeys ##### #6. Trees of tangles in abstract separation~systems ###### Christian Elbracht, Jakob Kneip, Maximilian Teegen We prove canonical and non-canonical tree-of-tangles theorems for abstract separation systems that are merely structurally submodular. Our results imply all known tree-of-tangles theorems for graphs, matroids and abstract separation systems with submodular order functions, with greatly simplified and shortened proofs. more | pdf | html ###### Figures None. ###### Tweets mathCObot: Christian Elbracht, Jakob Kneip, Maximilian Teegen : Trees of tangles in abstract separation~systems https://t.co/LnjJON36qt https://t.co/mulwEg2soj ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 3 Total Words: 0 Unqiue Words: 0 ###### 2.025 Mikeys ##### #7. A Characterization of Circle Graphs in Terms of Total Unimodularity ###### Robert Brijder, Lorenzo Traldi A graph$G$has an associated multimatroid$\mathcal{Z}_3(G)$, which is equivalent to the isotropic system of$G$studied by Bouchet. In previous work it was shown that$G$is a circle graph if and only if for every field$\mathbb F$, the rank function of$\mathcal{Z}_3(G)$can be extended to the rank function of an$\mathbb F$-representable matroid. In the present paper we strengthen this result using a multimatroid analogue of total unimodularity. As a consequence we obtain a characterization of matroid planarity in terms of this total-unimodularity analogue. more | pdf | html ###### Figures None. ###### Tweets mathCObot: Robert Brijder, Lorenzo Traldi : A Characterization of Circle Graphs in Terms of Total Unimodularity https://t.co/cAgeb5MWFn https://t.co/QnDXwrfj8r ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 2 Total Words: 0 Unqiue Words: 0 ###### 2.025 Mikeys ##### #8. A characterization of 2-neighborhood degree list of diameter 2 graphs ###### N. Benakli, E. Halleck, S. R. Kingan Let$N_2DL(v)$denote the set of degrees of vertices at distance 2 from$v$. The$2$-neighborhood degree list of a graph is a listing of$N_2DL(v)$for every vertex$v$. A degree restricted$2$-switch on edges$v_1v_2$and$w_1w_2$, where$deg(v_1)=deg(w_1)$and$deg(v_2)=deg(w_2)$, is the replacement of a pair of edges$v_1v_2$and$w_1w_2$by the edges$v_1w_2$and$v_2w_1$given that$v_1w_2$and$v_2w_1$did not appear in the graph originally. Let$G$and$H$be two graphs of diameter 2 on the same vertex set. We prove that$G$and$H$have the same$2$-neighborhood degree list if and only if$G$can be transformed into$H$by a sequence of degree restricted$2$-switches. more | pdf | html ###### Figures None. ###### Tweets mathCObot: N. Benakli, E. Halleck, S. R. Kingan : A characterization of 2-neighborhood degree list of diameter 2 graphs https://t.co/zJqcAzfckZ https://t.co/n6ueO7Iw8H ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 3 Total Words: 0 Unqiue Words: 0 ###### 2.025 Mikeys ##### #9. On the Todd Class of the Permutohedral variety ###### Federico Castillo, Fu Liu In the special of braid fans, we give a combinatorial formula for the Berline-Vergne's construction for an Euler-Maclaurin type formula that computes number of lattice points in polytopes. By showing that this formula does not always have positive values, we disprove a positivity conjecture we made previously. Our combinatorial formula is obtained by computing a symmetric expression for the Todd class of the permutohedral variety. Also as a result , we prove that the Todd class of the permutohedral variety$X_d$is not effective for$d \ge 24$. Additionally, we prove that the linear coefficient in the Ehrhart polynomial of any lattice generalized permutohedron is positive. more | pdf | html ###### Figures None. ###### Tweets mathCObot: Federico Castillo, Fu Liu : On the Todd Class of the Permutohedral variety https://t.co/QnmiRe8zOO https://t.co/9MfO455cnA ###### Github None. ###### Youtube None. ###### Other stats Sample Sizes : None. Authors: 2 Total Words: 0 Unqiue Words: 0 ###### 2.003 Mikeys ##### #10. Spectral Extremal Results for Hypergraphs ###### Yuan Hou, An Chang, Joshua Cooper Let$F$be a graph. A hypergraph is called Berge$F$if it can be obtained by replacing each edge in$F$by a hyperedge containing it. Given a family of graphs$\mathcal{F}$, we say that a hypergraph$H$is Berge$\mathcal{F}$-free if for every$F \in \mathcal{F}$, the hypergraph$H$does not contain a Berge$F$as a subhypergraph. In this paper we investigate the connections between spectral radius of the adjacency tensor and structural properties of a linear hypergraph. In particular, we obtain a spectral version of Tur\'{a}n-type problems over linear$k$-uniform hypergraphs by using spectral methods, including a tight result on Berge$C_4$-free linear$3\$-uniform hypergraphs.
more | pdf | html
None.
###### Tweets
mathCObot: Yuan Hou, An Chang, Joshua Cooper : Spectral Extremal Results for Hypergraphs https://t.co/bdLHOlhD5p https://t.co/NsQJJc4BYz
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
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 192,915 papers.

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