Abstract A graph $$H$$ is common if the number of monochromatic copies of $$H$$ in a 2-edge-colouring of the complete graph $$K_n$$ is asymptotically minimised by the random colouring. Burr and Rosta, extending a famous conjecture of Erdős, conjectured that every graph is common. The conjectures of Erdős and of Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples of common graphs had not seen much progress since then, although very recently a few more graphs were verified to be common by the flag algebra method or the recent progress on Sidorenko’s conjecture. Our contribution here is to provide several new classes of tripartite common graphs. The first example is the class of so-called triangle trees, which generalises two theorems by Sidorenko and answers a question of 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 $$5$$ vertices yields a common graph.
more »
« less
Bounding the tripartite‐circle crossing number of complete tripartite graphs
- Award ID(s):
- 1839918
- PAR ID:
- 10318839
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 100
- Issue:
- 1
- ISSN:
- 0364-9024
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The seismology component of this experiment will consist of a 2.5 dimensional transect that will cross from Bangladesh into Myanmar. We will install as many stations as possible on hard rock sites to minimize noise, although this will not be possible in low-lying deltaic areas. The array will consist of three lines. The middle line will be closely spaced in order to image shallow crustal features. It will have a station spacing of 5-10 km in Bangladesh expanding to 15 km in eastern Myanmar. To image the detachment megathrust at 10-20 km depth in the accretionary prism, a 100-km-long section spanning the Bangladesh and India border will have station spacing of 5 km or less. Two flanking lines located ~40 km on either side will have ~40 km spacing. This 80 km wide swath is critical for earthquake locations and body- and surface-wave tomography. The stations will operate for ~2 years, providing ample recordings from a wide backazimuth distribution of local, regional, and teleseismic events, and ambient noise for analysismore » « less
An official website of the United States government

