Zobrazeno 1 - 10
of 39
pro vyhledávání: '"Simkin, Michael"'
We study the following combinatorial counting and sampling problems: can we efficiently sample from the Erd\H{o}s-R\'{e}nyi random graph $G(n,p)$ conditioned on triangle-freeness? Can we efficiently approximate the probability that $G(n,p)$ is triang
Externí odkaz:
http://arxiv.org/abs/2410.22951
Degeneracy plays an important role in understanding Tur\'an- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capture these properties. We define the skeletal degeneracy of a $k$-unif
Externí odkaz:
http://arxiv.org/abs/2401.00359
Consider a host hypergraph $G$ which contains a spanning structure due to minimum degree considerations. We collect three results proving that if the edges of $G$ are sampled at the appropriate rate then the spanning structure still appears with high
Externí odkaz:
http://arxiv.org/abs/2210.03064
We prove that with high probability $\mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $n\equiv 1,3\pmod{6}$, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove
Externí odkaz:
http://arxiv.org/abs/2204.03964
We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares, resolving a conjecture of Linial that there exist Latin squares with a
Externí odkaz:
http://arxiv.org/abs/2202.05088
We prove a 1973 conjecture due to Erd\H{o}s on the existence of Steiner triple systems with arbitrarily high girth.
Comment: Added details to some proofs. Final version, to appear in Annals of Mathematics
Comment: Added details to some proofs. Final version, to appear in Annals of Mathematics
Externí odkaz:
http://arxiv.org/abs/2201.04554
Autor:
Douglas, Michael R., Simkin, Michael, Ben-Eliezer, Omri, Wu, Tianqi, Chin, Peter, Dang, Trung V., Wood, Andrew
A knowledge graph (KG) is a data structure which represents entities and relations as the vertices and edges of a directed graph with edge types. KGs are an important primitive in modern machine learning and artificial intelligence. Embedding-based m
Externí odkaz:
http://arxiv.org/abs/2110.09978
Autor:
Simkin, Michael
The $n$-queens problem is to determine $\mathcal{Q}(n)$, the number of ways to place $n$ mutually non-threatening queens on an $n \times n$ board. We show that there exists a constant $\alpha = 1.942 \pm 3 \times 10^{-3}$ such that $\mathcal{Q}(n) =
Externí odkaz:
http://arxiv.org/abs/2107.13460
Autor:
Luria, Zur, Simkin, Michael
The $n$-queens puzzle is to place $n$ mutually non-attacking queens on an $n \times n$ chessboard. We present a simple two stage randomized algorithm to construct such configurations. In the first stage, a random greedy algorithm constructs an approx
Externí odkaz:
http://arxiv.org/abs/2105.11431
Autor:
Linial, Nati, Simkin, Michael
We describe a new random greedy algorithm for generating regular graphs of high girth: Let $k\geq 3$ and $c \in (0,1)$ be fixed. Let $n \in \mathbb{N}$ be even and set $g = c \log_{k-1} (n)$. Begin with a Hamilton cycle $G$ on $n$ vertices. As long a
Externí odkaz:
http://arxiv.org/abs/1911.09640