Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn tripartite common graphs
140
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 Sidorenkos 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, v{S}v{t}oviv{c}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.
rate research
Read More
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not cross the circles. We present upper and lower bounds on the minimum number of crossings in tripartite-circle drawings of $K_{m,n,p}$ and the exact value for $K_{2,2,n}$. In contrast to 1- and 2-circle drawings, which may attain the Harary-Hill bound, our results imply that balanced restricted 3-circle drawings of the complete graph are not optimal.
A graph H is common if the number of monochromatic copies of H in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study this notion in the local setting as considered by Csoka, Hubai and Lovasz [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring, and give a complete characterization of graphs H into three categories in regard to a possible behavior of the 12 initial terms in the Taylor series determining the number of monochromatic copies of H in such perturbations: graphs of Class I are locally common, graphs of Class II are not locally common, and graphs of Class III cannot be determined to be locally common or not based on the initial 12 terms. As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.
A graph H is k-common if the number of monochromatic copies of H in a k-edge-coloring of K_n is asymptotically minimized by a random coloring. For every k, we construct a connected non-bipartite k-common graph. This resolves a problem raised by Jagger, Stovicek and Thomason [Combinatorica 16 (1996), 123-141]. We also show that a graph H is k-common for every k if and only if H is Sidorenko and that H is locally k-common for every k if and only if H is locally Sidorenko.
We explore the duality between the simulation and extraction of secret correlations in light of a similar well-known operational duality between the two notions of common information due to Wyner, and Gacs and Korner. For the inverse problem of simulating a tripartite noisy correlation from noiseless secret key and unlimited public communication, we show that Winters (2005) result for the key cost in terms of a conditional version of Wyners common information can be simply reexpressed in terms of the existence of a bipartite protocol monotone. For the forward problem of key distillation from noisy correlations, we construct simple distributions for which the conditional Gacs and Korner common information achieves a tight bound on the secret key rate. We conjecture that this holds in general for non-communicative key agreement models. We also comment on the interconvertibility of secret correlations under local operations and public communication.
Given a graph $G$ with $n$ vertices and a bijective labeling of the vertices using the integers $1,2,ldots, n$, we say $G$ has a peak at vertex $v$ if the degree of $v$ is greater than or equal to 2, and if the label on $v$ is larger than the label of all its neighbors. Fix an enumeration of the vertices of $G$ as $v_1,v_2,ldots, v_{n}$ and a fix a set $Ssubset V(G)$. We want to determine the number of distinct bijective labelings of the vertices of $G$, such that the vertices in $S$ are precisely the peaks of $G$. The set $S$ is called the emph{peak set of the graph} $G$, and the set of all labelings with peak set $S$ is denoted by $PSG$. This definition generalizes the study of peak sets of permutations, as that work is the special case of $G$ being the path graph on $n$ vertices. In this paper, we present an algorithm for constructing all of the bijective labelings in $PSG$ for any $Ssubseteq V(G)$. We also explore peak sets in certain families of graphs, including cycle graphs and joins of graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
