Source author record

Trevor Pinto

Trevor Pinto appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.AT math.PR

Catalog footprint

What is connected

4works

3topics

2close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2020arXiv

Random Uniform and Pure Random Simplicial Complexes

In this paper we introduce a method which allows us to study properties of the random uniform simplicial complex. That is, we assign equal probability to all simplicial complexes with a given number of vertices and then consider properties of a complex under this measure. We are able to determine or present bounds for a number of topological and combinatorial properties. We also study the random pure simplicial complex of dimension $d$, generated by letting any subset of size $d+1$ of a set of $n$ vertices be a facet with probability $p$ and considering the simplicial complex generated by these facets. We compare the behaviour of these models for suitable values of $d$ and $p$. Finally we use the equivalence between simplicial complexes and monotone boolean functions to study the behaviour of typical such functions. Specifically we prove that most monotone boolean functions are evasive, hence proving that the well known Evasiveness conjecture is generically true for monotone boolean functions without symmetry assumptions.

preprint2016arXiv

Saturated Subgraphs of the Hypercube

We say $G$ is \emph{$(Q_n,Q_m)$-saturated} if it is a maximal $Q_m$-free subgraph of the $n$-dimensional hypercube $Q_n$. A graph, $G$, is said to be $(Q_n,Q_m)$-semi-saturated if it is a subgraph of $Q_n$ and adding any edge forms a new copy of $Q_m$. The minimum number of edges a $(Q_n,Q_m)$-saturated graph (resp. $(Q_n,Q_m)$-semi-saturated graph) can have is denoted by $sat(Q_n,Q_m)$ (resp. $s\text{-}sat(Q_n,Q_m)$). We prove that $ \lim_{n\to\infty}\frac{sat(Q_n,Q_m)}{e(Q_n)}=0$, for fixed $m$, disproving a conjecture of Santolupo that, when $m=2$, this limit is $\frac{1}{4}$. Further, we show by a different method that $sat(Q_n, Q_2)=O(2^n)$, and that $s\text{-}sat(Q_n, Q_m)=O(2^n)$, for fixed $m$. We also prove the lower bound $s-sat(Q_n,Q_2)\geq \frac{m+1}{2}\cdot 2^n$, thus determining $sat(Q_n,Q_2)$ to within a constant factor, and discuss some further questions.

preprint2015arXiv

The proofs of two directed paths conjectures of Bollobás and Leader

Let $A$ and $B$ be disjoint sets, of size $2^k$, of vertices of $Q_n$, the $n$-dimensional hypercube. In 1997, Bollobás and Leader proved that there must be $(n-k)2^k$ edge-disjoint paths between such $A$ and $B$. They conjectured that when $A$ is a down-set and $B$ is an up-set, these paths may be chosen to be directed (that is, the vertices in the path form a chain). We use a novel type of compression argument to prove stronger versions of these conjectures, namely that the largest number of edge-disjoint paths between a down-set $A$ and an up-set $B$ is the same as the largest number of directed edge-disjoint paths between $A$ and $B$. Bollobás and Leader made an analogous conjecture for vertex-disjoint paths and we prove a strengthening of this by similar methods. We also prove similar results for all other sizes of $A$ and $B$.

preprint2014arXiv

Biclique Covers and Partitions

The biclique cover number (resp. biclique partition number) of a graph $G$, $\mathrm{bc}(G$) (resp. $\mathrm{bp}(G)$), is the least number of biclique (complete bipartite) subgraphs that are needed to cover (resp. partition) the edges of $G$. The \emph{local biclique cover number} (resp. local biclique partition number) of a graph $G$, $\mathrm{lbc}(G$) (resp. $\mathrm{lbp}(G)$), is the least $r$ such that there is a cover (resp. partition) of the edges of $G$ by bicliques with no vertex in more than $r$ of these bicliques. We show that $\mathrm{bp}(G)$ may be bounded in terms of $\mathrm{bc}(G)$, in particular, $\mathrm{bp}(G)\leq \frac{1}{2}(3^\mathrm{bc(G)}-1)$. However, the analogous result does not hold for the local measures. Indeed, in our main result, we show that $\mathrm{lbp}(G)$ can be arbitrarily large, even for graphs with $\mathrm{lbc}(G)=2$. For such graphs, $G$, we try to bound $\mathrm{lbp}(G)$ in terms of additional information about biclique covers of $G$. We both answer and leave open questions related to this. There is a well known link between biclique covers and subcube intersection graphs. We consider the problem of finding the least $r(n)$ for which every graph on $n$ vertices can be represented as a subcube intersection graph in which every subcube has dimension $r$. We reduce this problem to the much studied question of finding the least $d(n)$ such that every graph on $n$ vertices is the intersection graph of subcubes of a $d$-dimensional cube.