BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer-valued vectors (d,r) such that (diag(d)−AG)⋅r=0, where the entries of r have gcd 1 and AG is the adjacency matrix of G. In this article we find the arithmetical structures that maximize and minimize the spectral radius of (diag(d)−AG) among all arithmetical structures on the cycle graph Cn.
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 Sn,k be the join of a clique on k vertices with an independent set of n−k vertices and denote by Sn,k+ the graph obtained from Sn,k by adding one edge. We show that for fixed k≥2 and sufficiently large n, if a graph on n vertices has adjacency spectral radius at least as large as Sn,k and is not isomorphic to Sn,k, then it contains all trees on 2k+2 vertices. Similarly, if a sufficiently large graph has spectral radius at least as large as Sn,k+, then it either contains all trees on 2k+3 vertices or is isomorphic to Sn,k+. This answers a two-part conjecture of Nikiforov affirmatively.
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.
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≥3 and t≥2, the minimum number of copies of K1,t in a Ks-saturated graph is Θ(nt/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≥4 and t≥3, the minimum number of copies of K2,t in an n-vertex Ks-saturated graph is at least Ω(nt/5+8/5) and at most O(nt/2+3/2). These results answer a question of Chakraborti and Loh. General estimates on the number of copies of Ka,b in a Ks-saturated graph are also obtained, but finding an asymptotic formula remains open.
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 X1,X2,X3 with ∣X1∣=∣X2∣=∣X3∣ such that no edge intersects all of X1,X2,X3) 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.
Let rex(n,F) denote the maximum number of edges in an n-vertex graph that is regular and does not contain F as a subgraph. We give lower bounds on rex(n,F), that are best possible up to a constant factor, when F is one of C4, K2,t, K3,3 or Ks,t when t>s!.
We study Turán and Ramsey-type problems on edge-colored graphs. An edge-colored graph is called {\em ε-balanced} if each color class contains at least an ε-proportion of its edges. Given a family F of edge-colored graphs, the Ramsey function R(ε,F) is the smallest n for which any ε-balanced Kn must contain a copy of an F∈F, and the Turán function ex(ε,n,F) is the maximum number of edges in an n-vertex ε-balanced graph which avoids all of 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.
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.
Let HsG 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):HsG}. We consider degree Ramsey numbers where G is a fixed even cycle. Kinnersley, Milans, and West showed that RΔ(C2k,s)≥2s, and Kang and Perarnau showed that RΔ(C4,s)=Θ(s2). Our main result is that RΔ(C6,s)=Θ(s3/2) and RΔ(C10,s)=Θ(s5/4). Additionally, we substantially improve the lower bound for RΔ(C2k,s) for general k.
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 p1 and p2 are adjacent if p1 is incident to p2θ in Σ. A well-known example of a polarity graph is the Erdős-Rényi orthogonal polarity graph ERq, 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 ERq, 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 Ω(q3/2). Some related results are also obtained.
In this paper, we obtain two spectral upper bounds for the k-independence number of a graph which is is the maximum size of a set of vertices at pairwise distance greater than k. We construct graphs that attain equality for our first bound and show that our second bound compares favorably to previous bounds on the k-independence number.
The principal ratio of a connected graph, denoted γ(G), is the ratio of the maximum and minimum entries of its first eigenvector. Cioabă and Gregory conjectured that the graph on n vertices maximizing γ(G) is a kite graph: a complete graph with a pendant path. In this paper we prove their conjecture.
An edge-ordering of a graph G=(V,E) is a bijection ϕ:E→{1,2,...,∣E∣}. Given an edge-ordering, a sequence of edges P=e1,e2,...,ek is an increasing path if it is a path in G which satisfies ϕ(ei)<ϕ(ej) for all i<j. For a graph G, let f(G) be the largest integer ℓ such that every edge-ordering of G contains an increasing path of length ℓ. The parameter f(G) was first studied for G=Kn 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).
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(logn), whereas the number of planes of order less than n that our theorem applies to is not bounded above by any polynomial in n.
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.
In this note, we show that for any m∈{1,2,…,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+(2m) vertices with m2+8qm4−O(q3/2m4+m) edges. As an application, we give the best known lower bounds on the Turán number ex(n,C4) for certain values of n. In particular, we disprove a conjecture of Abreu, Balbuena, and Labbate concerning ex(q2−q−2,C4) where q is a power of 2.
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,…,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)≥(1−o(1))d/logd as d→∞, and the proportion of d-regular graphs G for which χc(G)≤(1+o(1))d/logd tends to 1 as ∣V(G)∣→∞.
A {\em product-injective labeling} of a graph G is an injection χ:V(G)→Z such that χ(u)χ(v)=χ(x)χ(y) for any distinct edges uv,xy∈E(G). Let P(G) be the smallest N≥1 such that there exists a product-injective labeling χ:V(G)→[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)∼n if d≤n(logn)−a and P(n,d)∼nlogn if d≥n(logn)b.
Determining the maximum number of edges in an n-vertex C4-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 C4-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.
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 q2−q−2 vertices that does not contain a 4-cycle and has at least 21q3−q2−O(q3/4) edges. This disproves a conjecture of Abreu, Balbuena, and Labbate concerning the Turán number ex(q2−q−2,C4).
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)≥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 Ω(logn), when d is fixed and n→∞. 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)≥cnV(n,d−1)n! 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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.