BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Michael Tait

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

ResearcherUnclaimed source record
math.COInformation Theorymath.ITmath.NTmath.SP

Catalog footprint

What is connected

21works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

21 published item(s)

preprint2023arXiv

Spectral Radii of Arithmetical Structures on Cycle Graphs

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer-valued vectors $(\mathbf{d},\mathbf{r})$ such that $(\text{diag}(\mathbf{d})-A_G)\cdot \mathbf{r}=\textbf{0},$ where the entries of $\mathbf{r}$ have $\gcd$ 1 and $A_G$ is the adjacency matrix of $G$. In this article we find the arithmetical structures that maximize and minimize the spectral radius of $(\text{diag}(\mathbf{d})-A_G)$ among all arithmetical structures on the cycle graph $\mathcal{C}_n.$

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A spectral Erdős-Sós theorem

The famous Erdős-Sós conjecture states that every graph of average degree more than $t-1$ must contain every tree on $t+1$ vertices. In this paper, we study a spectral version of this conjecture. For $n>k$, let $S_{n,k}$ be the join of a clique on $k$ vertices with an independent set of $n-k$ vertices and denote by $S_{n,k}^+$ the graph obtained from $S_{n,k}$ by adding one edge. We show that for fixed $k\geq 2$ and sufficiently large $n$, if a graph on $n$ vertices has adjacency spectral radius at least as large as $S_{n,k}$ and is not isomorphic to $S_{n,k}$, then it contains all trees on $2k+2$ vertices. Similarly, if a sufficiently large graph has spectral radius at least as large as $S_{n,k}^+$, then it either contains all trees on $2k+3$ vertices or is isomorphic to $S_{n,k}^+$. This answers a two-part conjecture of Nikiforov affirmatively.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sparsity of Graphs that Allow Two Distinct Eigenvalues

The parameter $q(G)$ of a graph $G$ is the minimum number of distinct eigenvalues over the family of symmetric matrices described by $G$. It is shown that the minimum number of edges necessary for a connected graph $G$ to have $q(G)=2$ is $2n-4$ if $n$ is even, and $2n-3$ if $n$ is odd. In addition, a characterization of graphs for which equality is achieved in either case is given.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Minimizing the number of complete bipartite graphs in a $K_s$-saturated graph

A graph $G$ is $F$-saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$. We prove that for $s \geq 3$ and $t \geq 2$, the minimum number of copies of $K_{1,t}$ in a $K_s$-saturated graph is $Θ( n^{t/2})$. More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s \geq 4$ and $t \geq 3$, the minimum number of copies of $K_{2,t}$ in an $n$-vertex $K_s$-saturated graph is at least $Ω( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$. These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$-saturated graph are also obtained, but finding an asymptotic formula remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large monochromatic components in 3-edge-colored Steiner triple systems

It is known that in any $r$-coloring of the edges of a complete $r$-uniform hypergraph, there exists a spanning monochromatic component. Given a Steiner triple system on $n$ vertices, what is the largest monochromatic component one can guarantee in an arbitrary 3-coloring of the edges? Gyárfás proved that $(2n+3)/3$ is an absolute lower bound and that this lower bound is best possible for infinitely many $n$. On the other hand, we prove that for almost all Steiner triple systems the lower bound is actually $(1-o(1))n$. We obtain this result as a consequence of a more general theorem which shows that the lower bound depends on the size of a largest \emph{3-partite hole} (that is, sets $X_1, X_2, X_3$ with $|X_1|=|X_2|=|X_3|$ such that no edge intersects all of $X_1, X_2, X_3$) in the Steiner triple system (Gyárfás previously observed that the upper bound depends on this parameter). Furthermore, we show that this lower bound is tight unless the coloring has a particular structure. We also suggest a variety of other Ramsey problems in the setting of Steiner triple systems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Turán and Ramsey-type results for unavoidable subgraphs

We study Turán and Ramsey-type problems on edge-colored graphs. An edge-colored graph is called {\em $\varepsilon$-balanced} if each color class contains at least an $\varepsilon$-proportion of its edges. Given a family $\mathcal{F}$ of edge-colored graphs, the Ramsey function $R(\varepsilon, \mathcal{F})$ is the smallest $n$ for which any $\varepsilon$-balanced $K_n$ must contain a copy of an $F\in\mathcal{F}$, and the Turán function $\mathrm{ex}(\varepsilon, n, \mathcal{F})$ is the maximum number of edges in an $n$-vertex $\varepsilon$-balanced graph which avoids all of $\mathcal{F}$. In this paper, we consider this Turán function for several classes of edge-colored graphs, we show that the Ramsey function is linear for bounded degree graphs, and we prove a theorem that gives a relationship between the two parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Szemerédi-Trotter type theorem, sum-product estimates in finite quasifields, and related results

We prove a Szemerédi-Trotter type theorem and a sum-product estimate in the setting of finite quasifields. These estimates generalize results of the fourth author, of Garaev, and of Vu. We generalize results of Gyarmati and Sárközy on the solvability of the equations $a + b = cd$ and $ab + 1 = cd$ over a finite field. Other analogous results that are known to hold in finite fields are generalized to finite quasifields.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Degree Ramsey numbers for even cycles

Let $H\xrightarrow{s} G$ denote that any $s$-coloring of $E(H)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_Δ(G, s)$, is $\min \{Δ(H): H \xrightarrow{s} G \}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_Δ(C_{2k},s) \geq 2s$, and Kang and Perarnau showed that $R_Δ(C_4, s) = Θ(s^2)$. Our main result is that $R_Δ(C_6, s) = Θ(s^{3/2})$ and $R_Δ(C_{10}, s) = Θ(s^{5/4})$. Additionally, we substantially improve the lower bound for $R_Δ(C_{2k}, s)$ for general $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Independent sets in polarity graphs

Given a projective plane $Σ$ and a polarity $θ$ of $Σ$, the corresponding polarity graph is the graph whose vertices are the points of $Σ$, and two distinct points $p_1$ and $p_2$ are adjacent if $p_1$ is incident to $p_2^{ θ}$ in $Σ$. A well-known example of a polarity graph is the Erdős-Rényi orthogonal polarity graph $ER_q$, which appears frequently in a variety of extremal problems. Eigenvalue methods provide an upper bound on the independence number of any polarity graph. Mubayi and Williford showed that in the case of $ER_q$, the eigenvalue method gives the correct upper bound in order of magnitude. We prove that this is also true for other families of polarity graphs. This includes a family of polarity graphs for which the polarity is neither orthogonal nor unitary. We conjecture that any polarity graph of a projective plane of order $q$ has an independent set of size $Ω(q^{3/2})$. Some related results are also obtained.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Increasing paths in edge-ordered graphs: the hypercube and random graphs

An edge-ordering of a graph $G=(V,E)$ is a bijection $ϕ:E\to\{1,2,...,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,e_k$ is an increasing path if it is a path in $G$ which satisfies $ϕ(e_i)<ϕ(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $\ell$ such that every edge-ordering of $G$ contains an increasing path of length $\ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On a problem of Neumann

A conjecture widely attributed to Neumann is that all finite non-desarguesian projective planes contain a Fano subplane. In this note, we show that any finite projective plane of even order which admits an orthogonal polarity contains a Fano subplane. The number of planes of order less than $n$ previously known to contain a Fano subplane was $O(\log n)$, whereas the number of planes of order less than $n$ that our theorem applies to is not bounded above by any polynomial in $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the distance spectra of graphs

The distance matrix of a graph $G$ is the matrix containing the pairwise distances between vertices. The distance eigenvalues of $G$ are the eigenvalues of its distance matrix and they form the distance spectrum of $G$. We determine the distance spectra of halved cubes, double odd graphs, and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Small dense subgraphs of polarity graphs and the extremal number for the 4-cycle

In this note, we show that for any $m \in \{1,2, \dots , q +1 \}$, if $G$ is a polarity graph of a projective plane of order $q$ that has an oval, then $G$ contains a subgraph on $m + \binom{m}{2}$ vertices with $m^2+\frac{m^4}{8q} - O ( \frac{m^4}{q^{3/2} } +m )$ edges. As an application, we give the best known lower bounds on the Turán number $\mathrm{ex}(n, C_4)$ for certain values of $n$. In particular, we disprove a conjecture of Abreu, Balbuena, and Labbate concerning $\mathrm{ex}(q^2-q-2, C_4)$ where $q$ is a power of $2$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On Coupon Colorings of Graphs

Let $G$ be a graph with no isolated vertices. A {\em $k$-coupon coloring} of $G$ is an assignment of colors from $[k] := \{1,2,\dots,k\}$ to the vertices of $G$ such that the neighborhood of every vertex of $G$ contains vertices of all colors from $[k]$. The maximum $k$ for which a $k$-coupon coloring exists is called the {\em coupon coloring number} of $G$, and is denoted $χ_{c}(G)$. In this paper, we prove that every $d$-regular graph $G$ has $χ_{c}(G) \geq (1 - o(1))d/\log d$ as $d \rightarrow \infty$, and the proportion of $d$-regular graphs $G$ for which $χ_c(G) \leq (1 + o(1))d/\log d$ tends to $1$ as $|V(G)| \rightarrow \infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On sets of integers with restrictions on their products

A {\em product-injective labeling} of a graph $G$ is an injection $χ: V(G) \to \mathbb{Z}$ such that $χ(u)χ(v) \not= χ(x)χ(y)$ for any distinct edges $uv, xy\in E(G)$. Let $P(G)$ be the smallest $N \geq 1$ such that there exists a product-injective labeling $χ: V(G) \rightarrow [N]$. Let $P(n,d)$ be the maximum possible value of $P(G)$ over $n$-vertex graphs $G$ of maximum degree at most $d$. In this paper, we determine the asymptotic value of $P(n,d)$ for all but a small range of values of $d$ relative to $n$. Specifically, we show that there exist constants $a,b > 0$ such that $P(n,d) \sim n$ if $d \leq \sqrt{n}(\log n)^{-a}$ and $P(n,d) \sim n\log n$ if $d \geq \sqrt{n}(\log n)^{b}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Orthogonal polarity graphs and Sidon sets

Determining the maximum number of edges in an $n$-vertex $C_4$-free graph is a well-studied problem that dates back to a paper of Erdős from 1938. One of the most important families of $C_4$-free graphs are the Erdős-Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose-Chowla Sidon set is isomorphic to a large induced subgraph of the Erdős-Rényi orthogonal polarity graph. Using this isomorphism we prove that the Petersen graph is a subgraph of every sufficiently large Erdős-Rényi orthogonal polarity graph.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Sidon Sets and graphs without 4-cycles

The problem of determining the maximum number of edges in an $n$-vertex graph that does not contain a 4-cycle has a rich history in extremal graph theory. Using Sidon sets constructed by Bose and Chowla, for each odd prime power $q$ we construct a graph with $q^2 - q - 2$ vertices that does not contain a 4-cycle and has at least $\frac{1}{2}q^3 - q^2 - O(q^{3/4})$ edges. This disproves a conjecture of Abreu, Balbuena, and Labbate concerning the Turán number $\mathrm{ex}(q^2 - q - 2, C_4)$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Permutation Codes

Given positive integers $n$ and $d$, let $M(n,d)$ denote the maximum size of a permutation code of length $n$ and minimum Hamming distance $d$. The Gilbert-Varshamov bound asserts that $M(n,d) \geq n!/V(n,d-1)$ where $V(n,d)$ is the volume of a Hamming sphere of radius $d$ in $§_n$. Recently, Gao, Yang, and Ge showed that this bound can be improved by a factor $Ω(\log n)$, when $d$ is fixed and $n \to \infty$. Herein, we consider the situation where the ratio $d/n$ is fixed and improve the Gilbert-Varshamov bound by a factor that is \emph{linear in $n$}. That is, we show that if $d/n < 0.5$, then $$ M(n,d)\geq cn\,\frac{n!}{V(n,d-1)} $$ where $c$ is a positive constant that depends only on $d/n$. To establish this result, we follow the method of Jiang and Vardy. Namely, we recast the problem of bounding $M(n,d)$ into a graph-theoretic framework and prove that the resulting graph is locally sparse.

0 citations0 reviewsNo code linkedOpen access