Source author record

Sam Spiro

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics math.PR

Catalog footprint

Research overview

8works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A Smoother Notion of Spread Hypergraphs

Alweiss, Lovett, Wu, and Zhang introduced $q$ -spread hypergraphs in their breakthrough work regarding the sunflower conjecture, and since then $q$ -spread hypergraphs have been used to give short proofs of several outstanding problems in probabilistic combinatorics. A variant of $q$ -spread hypergraphs was implicitly used by Kahn, Narayanan, and Park to determine the threshold for when a square of a Hamiltonian cycle appears in the random graph $G_{n,p}$ . In this paper we give a common generalization of the original notion of $q$ -spread hypergraphs and the variant used by Kahn et al.

preprint2022arXiv

Complementary Vanishing Graphs

Given a graph $G$ with vertices $\{v_1,\ldots,v_n\}$ , we define $\mathcal{S}(G)$ to be the set of symmetric matrices $A=[a_{i,j}]$ such that for $i\ne j$ we have $a_{i,j}\ne 0$ if and only if $v_iv_j\in E(G)$ . Motivated by the Graph Complement Conjecture, we say that a graph $G$ is complementary vanishing if there exist matrices $A \in \mathcal{S}(G)$ and $B \in \mathcal{S}(\overline{G})$ such that $AB=O$ . We provide combinatorial conditions for when a graph is or is not complementary vanishing, and we characterize which graphs are complementary vanishing in terms of certain minimal complementary vanishing graphs. In addition to this, we determine which graphs on at most $8$ vertices are complementary vanishing.

preprint2022arXiv

Zero Forcing with Random Sets

Given a graph $G$ and a real number $0\le p\le 1$ , we define the random set $B_p(G)\subset V(G)$ by including each vertex independently and with probability $p$ . We investigate the probability that the random set $B_p(G)$ is a zero forcing set of $G$ . In particular, we prove that for large $n$ , this probability for trees is upper bounded by the corresponding probability for a path graph. Given a minimum degree condition, we also prove a conjecture of Boyer et.\ al.\ regarding the number of zero forcing sets of a given size that a graph can have.

preprint2021arXiv

Linear Bounds for Cycle-free Saturation Games

Given a family of graphs $\mathcal{F}$ , we define the $\mathcal{F}$ -saturation game as follows. Two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that creates a subgraph in $\mathcal{F}$ . The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $\textrm{sat}_g(n,\mathcal{F})$ denote the number of edges that are in the final graph when both players play optimally. In general there are very few non-trivial bounds on the order of magnitude of $\textrm{sat}_g(n,\mathcal{F})$ . In this work, we find collections of infinite families of cycles $\mathcal{C}$ such that $\textrm{sat}_g(n,\mathcal{C})$ has linear growth rate.

preprint2020arXiv

An Averaging Processes on Hypergraphs

Consider the following iterated process on a hypergraph $H$ . Each vertex $v$ has an initial vertex weight. At each step, we uniformly at random select an edge $F$ in $H$ , and for each vertex $v$ in $F$ we replace the weight of $v$ by the average value of the vertex weights over all vertices in $F$ . This is a generalization of an interactive process on graphs, first proposed by Aldous and Lanoue. In this paper, we use the eigenvalues of a Laplacian for hypergraphs to bound the rate of convergence for the iterated averaging process.

preprint2020arXiv

Counting Labeled Threshold Graphs with Eulerian Numbers

A threshold graph is any graph which can be constructed from the empty graph by repeatedly adding a new vertex that is either adjacent to every vertex or to no vertices. The Eulerian number $\genfrac{\langle}{\rangle}{0pt}{}{n}{k}$ counts the number of permutations of size $n$ with exactly $k$ ascents. Implicitly Beissinger and Peled proved that the number of labeled threshold graphs on $n\ge 2$ vertices is $\sum_{k=1}^{n-1}(n-k)\genfrac{\langle}{\rangle}{0pt}{}{n-1}{k-1}2^k.$ Their proof used generating functions. We give a direct combinatorial proof of this result.

preprint2020arXiv

Forbidding $K_{2,t}$ traces in triple systems

Let $H$ and $F$ be hypergraphs. We say $H$ contains $F$ as a trace if there exists some set $S \subseteq V(H)$ such that $H|_S:=\{E\cap S: E \in E(H)\}$ contains a subhypergraph isomorphic to $F$ . In this paper we give an upper bound on the number of edges in a $3$ -uniform hypergraph that does not contain $K_{2,t}$ as a trace when $t$ is large. In particular, we show that $\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$ Moreover, we show $\frac{1}{2} n^{3/2} + o(n^{3/2}) \leq \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leq \frac{5}{6} n^{3/2} + o(n^{3/2})$ .

preprint2020arXiv

Triangle-free Subgraphs of Hypergraphs

In this paper, we consider an analog of the well-studied extremal problem for triangle-free subgraphs of graphs for uniform hypergraphs. A loose triangle is a hypergraph $T$ consisting of three edges $e,f$ and $g$ such that $|e \cap f| = |f \cap g| = |g \cap e| = 1$ and $e \cap f \cap g = \emptyset$ . We prove that if $H$ is an $n$ -vertex $r$ -uniform hypergraph with maximum degree $\triangle$ , then as $\triangle \rightarrow \infty$ , the number of edges in a densest $T$ -free subhypergraph of $H$ is at least $\frac{e(H)}{\triangle^{\frac{r-2}{r-1} + o(1)}}.$ For $r = 3$ , this is tight up to the $o(1)$ term in the exponent. We also show that if $H$ is a random $n$ -vertex triple system with edge-probability $p$ such that $pn^3\rightarrow\infty$ as $n\rightarrow\infty$ , then with high probability as $n \rightarrow \infty$ , the number of edges in a densest $T$ -free subhypergraph is $\min\Bigl\{(1-o(1))p{n\choose3},p^{\frac{1}{3}}n^{2-o(1)}\Bigr\}.$ We use the method of containers together with probabilistic methods and a connection to the extremal problem for arithmetic progressions of length three due to Ruzsa and Szemerédi.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Sam Spiro

Research overview

Is this your work?

8 publications

A Smoother Notion of Spread Hypergraphs

Complementary Vanishing Graphs

Zero Forcing with Random Sets

Linear Bounds for Cycle-free Saturation Games

An Averaging Processes on Hypergraphs

Counting Labeled Threshold Graphs with Eulerian Numbers

Forbidding $K_{2,t}$ traces in triple systems

Triangle-free Subgraphs of Hypergraphs

See the researcher in context

Building this map preview

Sam Spiro

Research overview

Is this your work?

8 publications

A Smoother Notion of Spread Hypergraphs

Complementary Vanishing Graphs

Zero Forcing with Random Sets

Linear Bounds for Cycle-free Saturation Games

An Averaging Processes on Hypergraphs

Counting Labeled Threshold Graphs with Eulerian Numbers

Forbidding K2,tK_{2,t}K2,t​ traces in triple systems

Triangle-free Subgraphs of Hypergraphs

See the researcher in context

Building this map preview

Forbidding $K_{2,t}$ traces in triple systems