wovepaper — the arXiv observatory

papers

Publications (17)

math.CO2022

Substructures in Latin squares

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney +1

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,…

math.CO2023

Ramsey and TurÃ¡n numbers of sparse hypergraphs

Jacob Fox, Maya Sankar, Michael Simkin +2

Degeneracy plays an important role in understanding TurÃ¡n- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capt…

math.CO2020

A randomized construction of high girth regular graphs

Nati Linial, Michael Simkin

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 N$ be even and set $g = c \log_…

math.CO2019

On the Threshold Problem for Latin Boxes

Zur Luria, Michael Simkin

Let $m \leq n \leq k$ . An $m \times n \times k$ 0-1 array is a Latin box if it contains exactly $mn$ ones, and has at most one $1$ in each line. As a special case, Latin boxes in w…

math.CO2016

Monotone Subsequences in High-Dimensional Permutations

Nathan Linial, Michael Simkin

This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the ErdÅs-Szekeres theorem: For every $k \geq 1$ , every order- $n$ $k$ -dimens…

math.CO2026

Non-existence probabilities and lower tails in the critical regime via Belief Propagation

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of…

math.CO2021

A lower bound for the $n$ -queens problem

Zur Luria, Michael Simkin

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 configuratio…

math.CO2023

A Toolkit for Robust Thresholds

Huy Tuan Pham, Ashwin Sah, Mehtaab Sawhney +1

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 th…

math.CO2025

On fractional triangle decompositions of random graphs

Ghaura Mahabaduge, Michael Simkin

We prove that with high probability $G (n, p)$ with $p \geq n^{- 4/11 + o (1)}$ admits a fractional triangle decomposition (FTD), i.e., a nonnegative weighting of its triangles such th…

math.CO2022

Threshold for Steiner triple systems

Ashwin Sah, Mehtaab Sawhney, Michael Simkin

We prove that with high probability $G^{(3)} (n, n^{- 1 + o (1)})$ contains a spanning Steiner triple system for $n \equiv 1, 3 (mod 6)$ , establishing the exponent for the thresho…

math.CO2022

The number of $n$ -queens configurations

Michael Simkin

The $n$ -queens problem is to determine $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 const…

math.CO2017

$(n, k, k - 1)$ -Steiner Systems in Random Hypergraphs

Michael Simkin

Let $H$ be a random $k$ -uniform $n$ -vertex hypergraph where every $k$ -tuple belongs to $H$ independently with probability $p$ . We show that for some $ε_{k} > 0$ , if $p \geq…

math.CO2024

High-Girth Steiner Triple Systems

Matthew Kwan, Ashwin Sah, Mehtaab Sawhney +1

We prove a 1973 conjecture due to ErdÅs on the existence of Steiner triple systems with arbitrarily high girth.

math.CO2020

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Roman Glebov, Zur Luria, Michael Simkin

Consider the random process in which the edges of a graph $G$ are added one by one in a random order. A classical result states that if $G$ is the complete graph $K_{2 n}$ or the co…

cs.DS2024

Sampling and counting triangle-free graphs near the critical density

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We study the following combinatorial counting and sampling problems: can we efficiently sample from the ErdÅs-RÃ©nyi random graph $G (n, p)$ conditioned on triangle-freeness? Can we…

cs.AI2021

What is Learned in Knowledge Graph Embeddings?

Michael R. Douglas, Michael Simkin, Omri Ben-Eliezer +4

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…

math.PR2024

Lower tails for triangles inside the critical window

Matthew Jenssen, Will Perkins, Aditya Potukuchi +1

We study the probability that the random graph $G (n, p)$ is triangle-free. When $p = o (n^{- 1/2})$ or $p = I ¨ (n^{- 1/2})$ the asymptotics of the logarithm of this probability are known…

Publications (17)

Substructures in Latin squares

Ramsey and TurÃ¡n numbers of sparse hypergraphs

A randomized construction of high girth regular graphs

On the Threshold Problem for Latin Boxes

Monotone Subsequences in High-Dimensional Permutations

Non-existence probabilities and lower tails in the critical regime via Belief Propagation

A lower bound for the n-queens problem

A Toolkit for Robust Thresholds

On fractional triangle decompositions of random graphs

Threshold for Steiner triple systems

The number of n-queens configurations

(n,k,k−1)-Steiner Systems in Random Hypergraphs

High-Girth Steiner Triple Systems

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Sampling and counting triangle-free graphs near the critical density

What is Learned in Knowledge Graph Embeddings?

Lower tails for triangles inside the critical window

A lower bound for the $n$ -queens problem

The number of $n$ -queens configurations

$(n, k, k - 1)$ -Steiner Systems in Random Hypergraphs