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.

mathCObot:
Yair Caro, Randy Davila, Ryan Pepper : New results relating independence and matchings https://t.co/dwVLZX9iGx https://t.co/jtcMvG2IBe

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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.

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.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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
None.

mathCObot:
Linyuan Lu, Joshua C. Thompson : Poset Ramsey Numbers for Boolean Lattices https://t.co/fIOibgCGRp https://t.co/hMDiEBITa3

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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
None.

mathCObot:
Lars Kastner, Robert Loewe : The Newton polytope of the discriminant of a quaternary cubic form https://t.co/NppMgZogNH https://t.co/agPt6xqRn3

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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
None.

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

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 0

Unqiue Words: 0

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
None.

mathCObot:
Christian Elbracht, Jakob Kneip, Maximilian Teegen : Trees of tangles in abstract separation~systems https://t.co/LnjJON36qt https://t.co/mulwEg2soj

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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
None.

mathCObot:
Robert Brijder, Lorenzo Traldi : A Characterization of Circle Graphs in Terms of Total Unimodularity https://t.co/cAgeb5MWFn https://t.co/QnDXwrfj8r

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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
None.

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

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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
None.

mathCObot:
Federico Castillo, Fu Liu : On the Todd Class of the Permutohedral variety https://t.co/QnmiRe8zOO https://t.co/9MfO455cnA

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

mathCObot:
Yuan Hou, An Chang, Joshua Cooper : Spectral Extremal Results for Hypergraphs https://t.co/bdLHOlhD5p https://t.co/NsQJJc4BYz

None.

None.

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible