BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Michael Simkin

Michael Simkin contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CO

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2023arXiv

Ramsey and Turán numbers of sparse hypergraphs

Degeneracy plays an important role in understanding Turán- 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$-uniform hypergraph as the degeneracy of its $1$-skeleton (i.e., the graph formed by replacing every $k$-edge by a $k$-clique). We prove that skeletal degeneracy controls hypergraph Turán and Ramsey numbers in a similar manner to (graphical) degeneracy. Specifically, we show that $k$-uniform hypergraphs with bounded skeletal degeneracy have linear Ramsey number. This is the hypergraph analogue of the Burr-Erdős conjecture (proved by Lee). In addition, we give upper and lower bounds of the same shape for the Turán number of a $k$-uniform $k$-partite hypergraph in terms of its skeletal degeneracy. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the `random greedy process' introduced by Lee in his resolution of the Burr-Erdős conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Substructures in Latin squares

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 arbitrarily high girth. As a consequence, we see that the number of order-$n$ Latin squares with no intercalate (i.e., no $2\times2$ Latin subsquare) is at least $(e^{-9/4}n-o(n))^{n^{2}}$. Equivalently, $\mathbb{P}\left[\mathbf{N}=0\right]\ge e^{-n^{2}/4-o(n^{2})}=e^{-(1+o(1))\mathbb{E}\mathbf{N}}$, where $\mathbf{N}$ is the number of intercalates in a uniformly random order-$n$ Latin square. In fact, extending recent work of Kwan, Sah, and Sawhney, we resolve the general large-deviation problem for intercalates in random Latin squares, up to constant factors in the exponent: for any constant $0<δ\le1$ we have $\mathbb{P}[\mathbf{N}\le(1-δ)\mathbb{E}\mathbf{N}]=\exp(-Θ(n^{2}))$ and for any constant $δ>0$ we have $\mathbb{P}[\mathbf{N}\ge(1+δ)\mathbb{E}\mathbf{N}]=\exp(-Θ(n^{4/3}\log n))$. Finally, as an application of some new general tools for studying substructures in random Latin squares, we show that in almost all order-$n$ Latin squares, the number of cuboctahedra (i.e., the number of pairs of possibly degenerate $2\times2$ submatrices with the same arrangement of symbols) is of order $n^{4}$, which is the minimum possible. As observed by Gowers and Long, this number can be interpreted as measuring ``how associative&#39;&#39; the quasigroup associated with the Latin square is.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Threshold for Steiner triple systems

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 the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A randomized construction of high girth regular graphs

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 as the smallest degree $δ(G)<k$, choose, uniformly at random, two vertices $u,v \in V(G)$ of degree $δ(G)$ whose distance is at least $g-1$. If there are no such vertex pairs, abort. Otherwise, add the edge $uv$ to $E(G)$. We show that with high probability this algorithm yields a $k$-regular graph with girth at least $g$. Our analysis also implies that there are $\left( Ω(n) \right)^{kn/2}$ labeled $k$-regular $n$-vertex graphs with girth at least $g$.

0 citations0 reviewsNo code linkedOpen access