Top 10 Arxiv Papers Today in Combinatorics


2.025 Mikeys
#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
Figures
None.
Tweets
mathCObot: Yair Caro, Randy Davila, Ryan Pepper : New results relating independence and matchings https://t.co/dwVLZX9iGx https://t.co/jtcMvG2IBe
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

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

2.025 Mikeys
#3. Poset Ramsey Numbers for Boolean Lattices
Linyuan Lu, Joshua C. Thompson
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
Figures
None.
Tweets
mathCObot: Yuan Hou, An Chang, Joshua Cooper : Spectral Extremal Results for Hypergraphs https://t.co/bdLHOlhD5p https://t.co/NsQJJc4BYz
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
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 192,915 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 192,915 papers.