|
Combinatorics, Probability and Computing
Journal Prestige (SJR): 0.839  Citation Impact (citeScore): 1 Number of Followers: 5  Hybrid journal (It can contain Open Access articles)ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163 Published by Cambridge University Press  [353 journals]
|
- A class of graphs of zero Turán density in a hypercube
-
Free pre-print version: Loading...
Authors: Axenovich; Maria
Pages: 404 - 410
Abstract: For a graph
and a hypercube 
, 
is the largest number of edges in an 
-free subgraph of 
. If 
, 
is said to have a positive Turán density in a hypercube or simply a positive Turán density; otherwise, it has zero Turán density. Determining 
and even identifying whether 
has a positive or zero Turán density remains a widely open question for general 
. By relating extremal numbers in a hypercube and certain corresponding hypergraphs, Conlon found a large class of graphs, ones having so-called partite representation, that have zero Turán density. He asked whether this gives a characterisation, that is, whether a graph has zero Turán density if and only if it has partite representation. Here, we show that, as suspected by Conlon, this is not the case. We give an example of a class of graphs which have no partite representation, but on the other hand, have zero Turán density. In addition, we show that any graph whose every block has partite representation has zero Turán density in a hypercube.
PubDate: 2024-03-05
DOI: 10.1017/S0963548324000063
-
- Spanning trees in graphs without large bipartite holes
-
Free pre-print version: Loading...
Authors: Han; Jie, Hu, Jie, Ping, Lidan, Wang, Guanghui, Wang, Yi, Yang, Donglei
Pages: 270 - 285
Abstract: We show that for any
and 
, there exists 
such that for sufficiently large 
, every 
-vertex graph 
satisfying that 
and 
for every pair of disjoint vertex sets 
of size 
contains all spanning trees with maximum degree at most 
. This strengthens a result of Böttcher, Han, Kohayakawa, Montgomery, Parczyk, and Person.
PubDate: 2023-11-14
DOI: 10.1017/S0963548323000378
-
- Large cliques or cocliques in hypergraphs with forbidden order-size pairs
-
Free pre-print version: Loading...
Authors: Axenovich; Maria, Bradač, Domagoj, Gishboliner, Lior, Mubayi, Dhruv, Weber, Lea
Pages: 286 - 299
Abstract: The well-known Erdős-Hajnal conjecture states that for any graph
, there exists 
such that every 
-vertex graph 
that contains no induced copy of 
has a homogeneous set of size at least 
. We consider a variant of the Erdős-Hajnal problem for hypergraphs where we forbid a family of hypergraphs described by their orders and sizes. For graphs, we observe that if we forbid induced subgraphs on 
vertices and 
edges for any positive 
and 
, then we obtain large homogeneous sets. For triple systems, in the first nontrivial case 
, for every 
, we give bounds on the minimum size of a homogeneous set in a triple system where the number of edges spanned by every four vertices is not in
PubDate: 2023-11-16
DOI: 10.1017/S0963548323000433
-
- Threshold graphs maximise homomorphism densities
-
Free pre-print version: Loading...
Authors: Blekherman; Grigoriy, Patel, Shyamal
Pages: 300 - 318
Abstract: Given a fixed graph
and a constant 
, we can ask what graphs 
with edge density 
asymptotically maximise the homomorphism density of 
in 
. For all 
for which this problem has been solved, the maximum is always asymptotically attained on one of two kinds of graphs: the quasi-star or the quasi-clique. We show that for any 
the maximising 
is asymptotically a threshold graph, while the quasi-clique and the quasi-star are the simplest threshold graphs, having only two parts. This result gives us a unified framework to derive a number of results on graph homomorphism maximisation, some of which were also found quite recently and independently using several different approaches. We show that there exist graphs 
and densities 
such that the optimising graph 
is neither the quasi-star nor the quasi-clique (Day and Sarkar, SIAM J. Discrete Math. 35(1), 294–306, 2021). We also show that for
PubDate: 2023-11-29
DOI: 10.1017/S096354832300041X
-
- On minimum spanning trees for random Euclidean bipartite graphs
-
Free pre-print version: Loading...
Authors: Correddu; Mario, Trevisan, Dario
Pages: 319 - 350
Abstract: We consider the minimum spanning tree problem on a weighted complete bipartite graph
whose 
vertices are random, i.i.d. uniformly distributed points in the unit cube in 
dimensions and edge weights are the 
-th power of their Euclidean distance, with 
. In the large 
limit with 
and 
, we show that the maximum vertex degree of the tree grows logarithmically, in contrast with the classical, non-bipartite, case, where a uniform bound holds depending on 
only. Despite this difference, for 
, we are able to prove that the total edge costs normalized by the rate 
converge to a limiting constant that can be represented as a series of integrals, thus extending a classical result of Avram and Bertsimas to the bipartite case and confirming a conjecture of Riva, Caracciolo and Malatesta.
PubDate: 2023-11-30
DOI: 10.1017/S0963548323000445
-
- Product structure of graph classes with bounded treewidth
-
Free pre-print version: Loading...
Authors: Campbell; Rutger, Clinch, Katie, Distel, Marc, Gollin, J. Pascal, Hendrey, Kevin, Hickingbotham, Robert, Huynh, Tony, Illingworth, Freddie, Tamitegama, Youri, Tan, Jane, Wood, David R.
Pages: 351 - 376
Abstract: We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class
to be the minimum non-negative integer 
such that, for some function 
, for every graph 
there is a graph 
with 
such that 
is isomorphic to a subgraph of 
. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 
; the class of 
-minor-free graphs has underlying treewidth 
(for 
); and the class of
PubDate: 2023-12-07
DOI: 10.1017/S0963548323000457
-
- Percolation on irregular high-dimensional product graphs
-
Free pre-print version: Loading...
Authors: Diskin; Sahar, Erde, Joshua, Kang, Mihyun, Krivelevich, Michael
Pages: 377 - 403
Abstract: We consider bond percolation on high-dimensional product graphs
, where 
denotes the Cartesian product. We call the 
the base graphs and the product graph 
the host graph. Very recently, Lichev (J. Graph Theory, 99(4):651–670, 2022) showed that, under a mild requirement on the isoperimetric properties of the base graphs, the component structure of the percolated graph 
undergoes a phase transition when 
is around 
, where 
is the average degree of the host graph.In the supercritical regime, we strengthen Lichev’s result by showing that the giant component is in fact unique, with all other components of order 
, and determining the sharp asymptotic order of the giant. Furthermore, we answer two questions posed by Lichev (J. Graph Theory, 99(4):651–670, 2022): firstly, we provide a construction showing that the requirement of bounded degree is necessary for the likely emergence of a linear order component; secondly, we show that the isoperimetric requirement on the base graphs can be, in fact, super-exponentially small in the dimension. Finally, in the subcritical regime, we give an example showing that in the case of irregular high-dimensional product graphs, there can be a polynomially large component with high probability, very much unlike the quantitative behaviour seen in the Erdős-Rényi random graph and in the percolated hypercube, and in fact in any regular high-dimensional product graphs, as shown by the authors in a companion paper (Percolation on high-dimensional product graphs. arXiv:2209.03722, 2022).
PubDate: 2023-12-20
DOI: 10.1017/S0963548323000469
-
