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
A conjecture of Bandelt and Dress states that the maximum quartet distance between any two phylogenetic trees on n leaves is at most (32+o(1))(4n). Using the machinery of flag algebras we improve the currently known bounds regarding this conjecture, in particular we show that the maximum is at most (0.69+o(1))(4n). We also give further evidence that the conjecture is true by proving that the maximum distance between caterpillar trees is at most (32+o(1))(4n).
We present a general approach connecting biased Maker-Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker-Breaker games. In particular, we show that for b=o(n), Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a (1:b) game on E(Kn). As another application, we show that for b=Θ(n/lnn), playing a (1:b) game on E(Kn), Maker can build a graph which contains copies of all spanning trees having maximum degree Δ=O(1) with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T).
The number of proper q-colorings of a graph G, denoted by PG(q), is an important graph parameter that plays fundamental role in graph theory, computational complexity theory and other related fields. We study an old problem of Linial and Wilf to find the graphs with n vertices and m edges which maximize this parameter. This problem has attracted much research interest in recent years, however little is known for general m,n,q. Using analytic and combinatorial methods, we characterize the asymptotic structure of extremal graphs for fixed edge density and q. Moreover, we disprove a conjecture of Lazebnik, which states that the Turán graph Ts(n) has more q-colorings than any other graph with the same number of vertices and edges. Indeed, we show that there are infinite many counterexamples in the range q=O(s2/logs). On the other hand, when q is larger than some constant times s2/logs, we confirm that the Turán graph Ts(n) asymptotically is the extremal graph achieving the maximum number of q-colorings. Furthermore, other (new and old) results on various instances of the Linial-Wilf problem are also established.
For a given graph G of minimum degree at least k, let Gp denote the random spanning subgraph of G obtained by retaining each edge independently with probability p=p(k). We prove that if p≥klogk+loglogk+ωk(1), where ωk(1) is any function tending to infinity with k, then Gp asymptotically almost surely contains a cycle of length at least k+1. When we take G to be the complete graph on k+1 vertices, our theorem coincides with the classic result on the threshold probability for the existence of a Hamilton cycle in the binomial random graph.
Answering in a strong form a question posed by Bollobás and Scott, in this paper we determine the discrepancy between two random k-uniform hypergraphs, up to a constant factor depending solely on k.
Fifty years ago Erdős asked to determine the minimum number of k-cliques in a graph on n vertices with independence number less than l. He conjectured that this minimum is achieved by the disjoint union of l−1 complete graphs of size l−1n. This conjecture was disproved by Nikiforov who showed that the balanced blow-up of a 5-cycle has fewer 4-cliques than the union of 2 complete graphs of size 2n. In this paper we solve Erdős' problem for (k,l)=(3,4) and (k,l)=(4,3). Using stability arguments we also characterize the precise structure of extremal examples, confirming Erdős' conjecture for (k,l)=(3,4) and showing that a blow-up of a 5-cycle gives the minimum for (k,l)=(4,3).
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.