We show that for every $\eta>0$ and sufficiently large $n$, there exists a poset of size $2^{(1+\eta)n/2}$ containing all the $n$-element posets as induced subposets. This improves a recent result of Bastide, Groenland and Nenadov. Our proof provides a labeling scheme preserving transitivity, inspired by the Boolean lattice. Among other tools, we use the Szemer\'edi Regularity Lemma.
Let $G$ be a finite group and $x \in G$. In 2013, Hai-Reuven proved that the cardinality of the centralizer of $x$ divides the cardinality of the solubilizer of $x$. Settling a conjecture of Mousavi, Poozesh and Zamani, we show that the cardinality of the normalizer of $\langle x \rangle$ is also a divisor. We actually...
We show that there exists $c>0$ such that any subset of $\{1,\ldots,N\}$ having size $\gg N / \exp( (\log\log\log N)^c )$ contains a nontrivial pattern of the form $x,x+y,x+2y,x+y^3$. It is the first configuration of complexity strictly greater than $0$, other than refinements of arithmetic progressions, for which quan...
Bartłomiej Bychawski, Bartosz Głowacki, Ivan Spyrydonov· 0 citations
For every $n$, we construct a 2-dimensional $n$-element poset whose Hasse diagram has independence number $n\exp(-\Omega(\sqrt{\log n}))$, and consequently, chromatic number $\exp(\Omega(\sqrt{\log n}))$. This also yields an $n$-point planar set whose box-Delaunay graph satisfies the same bounds.
Let $b(n)$ denote the minimum number of perfect matchings in a simple brace of order $n$. De~Carvalho, Lucchesi and Murty (SIAM Journal on Discrete Mathematics, 27(2): (2013) 940-958) proved that $b(n)\ge(n-2)^2/8$ and conjectured that $b(n)=(n-2)^2/4$ for all sufficiently large even $n$. We prove this conjecture.
For every real $t>0$, we prove that every $2$-connected $t$-tough graph contains a cycle of length at least $\ell$ whenever $n \leq \ell(1 + 1/t)^{\lfloor \ell/2\rfloor - 1}$. This establishes the logarithmic bound conjectured by Broersma, van den Heuvel, Jung, and Veldman.
We show that the only degree which cannot co-enumerate a non-trivial $\Pi^0_1$-immune real is $\emptyset$, resolving a conjecture of the author. The main ingredient is that if a real $A$ has that all $A$-maximal sets are c.e., then $A$ has c.e. degree, which can be proved via a coding mechanism and two classical result...
David J. Webb· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
