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
Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and Rödl conjectured that for any given μ>0, there exists n0 such that the following holds. Every n-vertex Steiner triple system contains all hypertrees with at most (1−μ)n vertices whenever n≥n0. We prove this conjecture.
For any given graph H, one may define a natural corresponding functional ∥.∥H for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once H is paired with a 2-edge-colouring α to assign conjugates. We say that H is real-norming (resp. complex-norming) if ∥.∥H (resp. ∥.∥H,α for some α) is a norm on the vector space of real-valued (resp. complex-valued) functions. These generalise the Gowers octahedral norms, a widely used tool in extremal combinatorics to quantify quasirandomness. We unify these two seemingly different notions of graph norms in real- and complex-valued settings. Namely, we prove that H is complex-norming if and only if it is real-norming and simply call the property norming. Our proof does not explicitly construct a suitable 2-edge-colouring α but obtains its existence and uniqueness, which may be of independent interest. As an application, we give various example graphs that are not norming. In particular, we show that hypercubes are not norming, which resolves the last outstanding problem posed in Hatami's pioneering work on graph norms.
A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdos, conjectured that every graph is common. The conjectures by Erdos and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture. Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle-trees, which generalises two theorems by Sidorenko and answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle-tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most five vertices give a common graph.
Sidorenko's conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H=K5,5∖C10. It was even unknown whether this graph possesses the strictly stronger, weakly norming property. We take a step towards understanding the graph K5,5∖C10 by proving that it is not weakly norming. More generally, we show that 'twisted' blow-ups of cycles, which include K5,5∖C10 and C6□K2, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that Kt,t minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t>3.
Given a graph H, the extremal number ex(n,H) is the largest number of edges in an H-free graph on n vertices. We make progress on a number of conjectures about the extremal number of bipartite graphs. First, writing Ks,t′ for the subdivision of the bipartite graph Ks,t, we show that ex(n,Ks,t′)=O(n3/2−2s1). This proves a conjecture of Kang, Kim and Liu and is tight up to the implied constant for t sufficiently large in terms of s. Second, for any integers s,k≥1, we show that ex(n,L)=Θ(n1+sk+1s) for a particular graph L depending on s and k, answering another question of Kang, Kim and Liu. This result touches upon an old conjecture of Erdős and Simonovits, which asserts that every rational number r∈(1,2) is realisable in the sense that ex(n,H)=Θ(nr) for some appropriate graph H, giving infinitely many new realisable exponents and implying that 1+1/k is a limit point of realisable exponents for all k≥1. Writing Hk for the k-subdivision of a graph H, this result also implies that for any bipartite graph H and any k, there exists δ>0 such that ex(n,Hk−1)=O(n1+1/k−δ), partially resolving a question of Conlon and Lee. Third, extending a recent result of Conlon and Lee, we show that any bipartite graph H with maximum degree r on one side which does not contain C4 as a subgraph satisfies ex(n,H)=o(n2−1/r).
Sidorenko's conjecture states that for every bipartite graph H on {1,⋯,k}, ∫∏(i,j)∈E(H)h(xi,yj)dμ∣V(H)∣≥(∫h(x,y)dμ2)∣E(H)∣ holds, where μ is the Lebesgue measure on [0,1] and h is a bounded, non-negative, symmetric, measurable function on [0,1]2. An equivalent discrete form of the conjecture is that the number of homomorphisms from a bipartite graph H to a graph G is asymptotically at least the expected number of homomorphisms from H to the Erdős-Rényi random graph with the same expected edge density as G. In this paper, we present two approaches to the conjecture. First, we introduce the notion of tree-arrangeability, where a bipartite graph H with bipartition A∪B is tree-arrangeable if neighborhoods of vertices in A have a certain tree-like structure. We show that Sidorenko's conjecture holds for all tree-arrangeable bipartite graphs. In particular, this implies that Sidorenko's conjecture holds if there are two vertices a1,a2 in A such that each vertex a∈A satisfies N(a)⊆N(a1) or N(a)⊆N(a2), and also implies a recent result of Conlon, Fox, and Sudakov \cite{CoFoSu}. Second, if T is a tree and H is a bipartite graph satisfying Sidorenko's conjecture, then it is shown that the Cartesian product T□H of T and H also satisfies Sidorenko's conjecture. This result implies that, for all d≥2, the d-dimensional grid with arbitrary side lengths satisfies Sidorenko's conjecture.
Rank-width of a graph G, denoted by rw(G), is a width parameter of graphs introduced by Oum and Seymour (2006). We investigate the asymptotic behavior of rank-width of a random graph G(n,p). We show that, asymptotically almost surely, (i) if 0<p<1 is a constant, then rw(G(n,p)) = \lceil n/3 \rceil-O(1), (ii) if 1/n<< p <1/2, then rw(G(n,p))= \lceil n/3\rceil-o(n), (iii) if p = c/n and c > 1, then rw(G(n,p)) > r n for some r = r(c), and (iv) if p <= c/n and c<1, then rw(G(n,p)) <=2. As a corollary, we deduce that G(n,p) has linear tree-width whenever p=c/n for each c>1, answering a question of Gao (2006).
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.