Article in volume
Authors:
Title:
On small balanceable, strongly-balanceable and omnitonal graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1219-1235
Received: 2019-08-22 , Revised: 2020-06-02 , Accepted: 2020-06-02 , Available online: 2020-07-01 , https://doi.org/10.7151/dmgt.2342
Abstract:
In Ramsey Theory for graphs we are given a graph $G$ and we are required to find
the least $n_0$ such that, for any $n\geq n_0$, any red/blue colouring of the
edges of $K_n$ gives a subgraph $G$ all of whose edges are blue or all are red.
Here we shall be requiring that, for any red/blue colouring of the edges of
$K_n$, there must be a copy of $G$ such that its edges are partitioned equally
as red or blue (or the sizes of the colour classes differs by one in the case
when $G$ has an odd number of edges). This introduces the notion of balanceable
graphs and the balance number of $G$ which, if it exists, is the minimum integer
bal$(n, G)$ such that, for any red/blue colouring of $E(K_n)$ with more than
bal$(n, G)$ edges of either colour, $K_n$ will contain a balanced coloured copy
of $G$ as described above. The strong balance number sbal$(n,G)$ is analogously
defined when $G$ has an odd number of edges, but in this case we require that
there are copies of $G$ with both one more red edge and one more blue edge.
These parameters were introduced by Caro, Hansberg and Montejano. These authors
also introduce the more general omnitonal number ot$(n, G)$ which requires
copies of $G$ containing a complete distribution of the number of red and blue
edges over $E(G)$.
In this paper we shall catalogue bal$(n, G)$, sbal$(n, G)$ and ot$(n,G)$ for
all graphs $G$ on at most four edges. We shall be using some of the key results
of Caro et al. which we here reproduce in full, as well as some new results
which we prove here. For example, we shall prove that the union of two
bipartite graphs with the same number of edges is always balanceable.
Keywords:
edge-colouring, zero-sum Ramsey, balanceable graphs, omnitonal graphs
References:
- C. Augspurger, M. Minter, K. Shoukry, P. Sissokho and K. Voss, Avoiding zero-sum subsequences of prescribed length over the integers (2016).
arXiv: 1603.03978 - A. Berger, An analogue of the Erdős-Ginzburg-Ziv theorem over $\mathbb{Z}$, Discrete Math. 342 (2019) 815–820.
https://doi.org/10.1016/j.disc.2018.11.018 - B. Bollobás, Extremal Graph Theory (Courier Corporation, 2004).
- M. Bowen, A. Hansberg, A. Montejano and A. Müyesser, Colored unavoidable patterns and balanceable graphs (2019).
arXiv: 1912.06302 - Y. Caro, A. Hansberg and A. Montejano, Amoebas (2019), in preparation.
- Y. Caro, A. Hansberg and A. Montejano, Unavoidable chromatic patterns in $2$-colorings of the complete graph (2019).
arXiv: 1810.12375 - Y. Caro, A. Hansberg and A. Montejano, Zero-sum ${K}_m$ over $\mathbb{Z}$ and the story of ${K}_4$, Graphs Combin. 35 (2019) 855–865.
https://doi.org/10.1007/s00373-019-02040-3 - Y. Caro, A. Hansberg and A. Montejano, Zero-sum subsequences in bounded-sum $\{- 1, 1\}$-sequences, J. Combin. Theory Ser. A 161 (2019) 387–419.
https://doi.org/10.1016/j.jcta.2018.09.001 - Y. Caro and R. Yuster, On zero-sum and almost zero-sum subgraphs over $\mathbb{Z}$, Graphs Combin. 32 (2016) 49–63.
https://doi.org/10.1007/s00373-015-1541-6 - E.J. Cockayne and P.J. Lorimer, The Ramsey number for stripes, J. Aust. Math. Soc. 19 (1975) 252–256.
https://doi.org/10.1017/S1446788700029554 - P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta Math. Hungar. 10 (1959) 337–356.
https://doi.org/10.1007/BF02024498 - R.J. Faudree and R.H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974) 313–329.
https://doi.org/10.1016/0012-365X(74)90151-4 - Z. Füredi and M. Simonovits, The history of degenerate $($bipartite$)$ extremal graph problems, in: Erdős Centennial, Bolyai Soc. Math. Stud. 25, L. Lovász, I.Z. Ruzsa and V.T. Sós (Ed(s)), (Springer, Berlin, Heidelberg 2013) 169–264.
https://doi.org/10.1007/978-3-642-39286-3_7 - A. Girão and B. Narayanan, Turán theorems for unavoidable patterns (2019).
arXiv: 1907.00964 - O. Pikhurko, A note on the Turán function of even cycles, Proc. Amer. Math. Soc. 140 (2012) 3687–3692.
https://doi.org/10.1090/S0002-9939-2012-11274-2 - A. Robertson, Zero-sum analogues of van der Waerden's theorem on arithmetic progressions, J. Comb. 11 (2020) 231–248.
https://doi.org/10.4310/JOC.2020.v11.n2.a1 - A. Robertson, Zero-sum generalized Schur numbers (2018).
arXiv: 1802.03382 - A. Sun, Zero-sum subsequences in bounded-sum $\{-r, s \}$-sequences (2019).
arXiv: 1907.06623 - D.B. West, Introduction to Graph Theory (Math. Classics, Pearson, 2017).
Close