Search ResultsShowing 1-20 of 24
-
arXiv:2403.13726 (Published 2024-03-20)
Rainbow considerations around the Hales-Jewett theorem
Categories: math.COFor positive integers $t$ and $n$ let $C_t^n$ be the $n$-cube over $t$ elements, that is, the set of ordered $n$-tuples over the alphabet $\{0,\dots, t-1\}$. We address the question of whether a balanced finite coloring of $C_t^n$ guarantees the presence of a rainbow geometric or combinatorial line. For every even $t\geq 4$ and every $n$, we provide a $\left(\frac{t}{2}\right)^n$--coloring of $C_t^n$ such that all color classes have the same size, and without rainbow combinatorial or geometric lines.
-
arXiv:2204.04269 (Published 2022-04-08)
The evolution of unavoidable bi-chromatic patterns and extremal cases of balanceability
Comments: 16 pages, 2 figuresCategories: math.COWe study the color patterns that, for $n$ sufficiently large, are unavoidable in $2$-colorings of the edges of a complete graph $K_n$ with respect to $\min \{e(R), e(B)\}$, where $e(R)$ and $e(B)$ are the numbers of red and, respectively, blue edges. More precisely, we determine how such unavoidable patterns evolve from the case without restriction in the coloring, namely that $\min \{e(R), e(B)\} \ge 0$ (given by Ramsey's theorem), to the highest possible restriction, namely that $|e(R) - e(B)| \le 1$. We also investigate the effect of forbidding certain sub-structures in each color. In particular, we show that, in $2$-colorings whose graphs induced by each of the colors are both free from an induced matching on $r$ edges, the appearance of the unavoidable patterns is already granted with a much weaker restriction on $\min \{e(R), e(B)\}$. We finish analyzing the consequences of these results to the balancing number $bal(n,G)$ of a graph $G$ (i.e. the minimum $k$ such that every $2$-edge coloring of $K_n$ with $\min \{e(R), e(B)\} > k$ contains a copy of $G$ with half the edges in each color), and show that, for every $\varepsilon > 0$, there are graphs $G$ with $bal(n,G) \ge c n^{2-\varepsilon}$, which is the highest order of magnitude that is possible to achieve, as well as graphs where $bal(n,G) \le c(G)$, where $c(G)$ is a constant that depends only $G$. We characterize the latter ones.
-
Sidon-Ramsey and $B_{h}$-Ramsey numbers
Comments: 11 pagesCategories: math.COFor a given positive integer $k$, the Sidon-Ramsey number $\SR(k)$ is defined as the minimum value of $n$ such that, in every partition of the set $[1, n]$ into $k$ parts, there exists a part that contains two distinct pairs of numbers with the same sum. In other words, there is a part that is not a Sidon set. In this paper, we investigate the asymptotic behavior of this parameter and two generalizations of it. The first generalization involves replacing pairs of numbers with $h$-tuples, such that in every partition of $[1, n]$ into $k$ parts, there exists a part that contains two distinct $h$-tuples with the same sum. Alternatively, there is a part that is not a $B_h$ set. The second generalization considers the scenario where the interval $[1, n]$ is substituted with a non-necessarily symmetric $d$-dimensional box of the form $\prod_{i=1}^d[1,n_i]$. For the general case of $h\geq 3$ and non-symmetric boxes, before applying our method to obtain the Ramsey-type result, we needed to establish an upper bound for the corresponding density parameter.
-
arXiv:2109.07539 (Published 2021-09-15)
Erdős-Ginzburg-Ziv type generalizations for linear equations and linear inequalities in three variables
Categories: math.COFor any linear inequality in three variables $\mathcal{L}$, we determine (if it exist) the smallest integer $R(\mathcal{L}, \mathbb{Z}/3\mathbb{Z})$ such that: for every mapping $\chi :[1,n] \to \{0,1,2\}$, with $n\geq R(\mathcal{L}, \mathbb{Z}/3\mathbb{Z})$, there is a solution $(x_1,x_2,x_3)\in [1,n]^3$ of $\mathcal{L}$ with $\chi(x_1)+\chi(x_2)+\chi(x_3)\equiv 0$ (mod $3$). Moreover, we prove that $R(\mathcal{L}, \mathbb{Z}/3\mathbb{Z})=R(\mathcal{L}, 2)$, where $R(\mathcal{L}, 2)$ denotes the classical $2$-color Rado number, that is, the smallest integer (provided it exist) such that for every $2$-coloring of $[1,n]$, with $n\geq R(\mathcal{L}, 2)$, there exist a monochromatic solution of $\mathcal{L}$. Thus, we get an Erd\H{o}s-Ginzburg-Ziv type generalization for all lineal inequalities in three variables having a solution in the positive integers. We also show a number of families of linear equations in three variables $\mathcal{L}$ such that they do not admit such Erd\H{o}s-Ginzburg-Ziv type generalization, named $R(\mathcal{L}, \mathbb{Z}/3\mathbb{Z})\neq R(\mathcal{L}, 2)$. At the end of this paper some questions are proposed.
-
arXiv:2104.09707 (Published 2021-04-20)
Recursive constructions of amoebas
Comments: 11 pages, 3 figures to be published in the LAGOS 2021 proceedingsCategories: math.COGlobal amoebas are a wide and rich family of graphs that emerged from the study of certain Ramsey-Tur\'an problems in $2$-colorings of the edges of the complete graph $K_n$ that deal with the appearance of unavoidable patterns once a certain amount of edges in each color is guaranteed. Indeed, it turns out that, as soon as such coloring constraints are satisfied and if $n$ is sufficiently large, then every global amoeba can be found embedded in $K_n$ such that it has half its edges in each color. Even more surprising, every bipartite global amoeba $G$ is unavoidable in every tonal-variation, meaning that, for any pair of integers $r, b$ such that $r + b $ is the number of edges of $G$, there is a subgraph of $K_n$ isomorphic to $G$ with $r$ edges in the first color and $b$ edges in the second. The feature that makes global amoebas work are one-by-one edge replacements that leave the structure of the graph invariant. By means of a group theoretical approach, the dynamics of this feature can be modeled. As a counterpart to the global amoebas that "live" inside a possibly large complete graph $K_n$, we also consider local amoebas which are spanning subgraphs of $K_n$ with the same feature. In an effort to highlight their richness and versatility, we present here three different recursive constructions of amoebas, two of them yielding interesting families per se and one of them offering a wide range of possibilities.
-
arXiv:2007.11769 (Published 2020-07-23)
Graphs isomorphisms under edge-replacements and the family of amoebas
Comments: 21 pages, 9 figuresCategories: math.COLet $G$ be a graph of order $n$ and let $e\in E(G)$ and $e'\in E(\overline{G}) \cup \{e\}$. If the graph $G-e+e'$ is isomorphic to $G$, we say that $e\to e'$ is a \emph{feasible edge-replacement}. We call $G$ a \emph{local amoeba} if, for any two copies $G_1$, $G_2$ of $G$ that are embedded in $K_n$, $G_1$ can be transformed into $G_2$ by a chain of feasible edge-replacements. On the other hand, $G$ is called \emph{global amoeba} if there is an integer $T \ge 1$ such that $G \cup tK_1$ is a local amoeba for all $t \ge T$. We study global and local amoebas under an underlying algebraic theoretical setting. In this way, a deeper understanding of their structure and their intrinsic properties as well as how these two families relate with each other comes into light. Moreover, it is shown that any connected graph can be a connected component of an amoeba, and a construction of a family of amoeba trees with a Fibonacci-like structure and with arbitrary large maximum degree is presented.
-
arXiv:2005.07813 (Published 2020-05-15)
Zero-sum squares in bounded discrepancy {-1,1}-matrices
Categories: math.COFor $n\ge 5$, we prove that every $n\times n$ $\{-1,1\}$-matrix $M=(a_{ij})$ with discrepancy $\sum a_{ij} \le n$ contains a zero-sum square except for the diagonal matrix (up to symmetries). Here, a square is a $2\times 2$ sub-matrix of $M$ with entries $a_{i,j}, a_{i+s,s}, a_{i,j+s}, a_{i+s,j+s}$ for some $s\ge 1$, and the diagonal matrix is a matrix with all entries above the diagonal equal to $-1$ and all remaining entries equal to $1$. In particular, we show that for $n\ge 5$ every zero-sum $n\times n$ $\{-1,1\}$-matrix contains a zero-sum square.
-
arXiv:1912.06302 (Published 2019-12-13)
Colored unavoidable patterns and balanceable graphs
We study a Tur\'an-type problem on edge-colored complete graphs. We show that for any $r$ and $t$, any sufficiently large $r$-edge-colored complete graph on $n$ vertices with $\Omega(n^{2-\frac{1}{t}})$ edges in each color contains an $(r,t)$-unavoidable graph, where an $(r,t)$-unavoidable graph is essentially a $t$-blow-up of an $r$-colored complete graph where all $r$ colors are present. The result is tight up to the implied constant factor, assuming the well-known conjecture that $ex(K_{t,t})=\Theta(n^{2-{1/t}})$. Next, we study a related problem where the corresponding Tur\'an threshold is linear. In particular, we show that any $3$-edge-coloring of a large enough complete graph with $kn+o(n)$ edges in each color contains a path on $3k$ edges with an equal number of edges from each color. This is tight up to a constant factor of $2$.
-
arXiv:1812.11872 (Published 2018-12-31)
A rainbow version of Mantel's Theorem
Mantel's Theorem asserts that a simple $n$ vertex graph with more than $\frac{1}{4}n^2$ edges has a triangle (three mutually adjacent vertices). Here we consider a rainbow variant of this problem. We prove that whenever $G_1, G_2, G_3$ are simple graphs on a common set of $n$ vertices and $|E(G_i)| > ( \frac{ 26 - 2 \sqrt{7} }{81})n^2 \approx 0.2557 n^2$ for $1 \le i \le 3$, then there exist distinct vertices $v_1,v_2,v_3$ so that (working with the indices modulo 3) we have $v_i v_{i+1} \in E(G_i)$ for $1 \le i \le 3$. We provide an example to show this bound is best possible. This also answers a question of Diwan and Mubayi. We include a new short proof of Mantel's Theorem we obtained as a byproduct.
-
arXiv:1811.02455 (Published 2018-11-06)
On the Number of Order Types in Integer Grids of Small Size
Luis E. Caraballo, José-Miguel Díaz-Báñez, Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Jesús Leaños, Amanda MontejanoLet $\{p_1,\dots,p_n\}$ and $\{q_1,\dots,q_n\}$ be two sets of $n$ labeled points in general position in the plane. We say that these two point sets have the same order type if for every triple of indices $(i,j,k)$, $p_k$ is above the directed line from $p_i$ to $p_j$ if and only if $q_k$ is above the directed line from $q_i$ to $q_j$. In this paper we give the first non-trivial lower bounds on the number of different order types of $n$ points that can be realized in integer grids of polynomial
-
arXiv:1810.12375 (Published 2018-10-29)
Unavoidable chromatic patterns in 2-colorings of the complete graph
Comments: 26 pagesCategories: math.COWe consider unavoidable chromatic patterns in $2$-colorings of the edges of the complete graph. Several such problems are explored being a junction point between Ramsey theory, extremal graph theory (Tur\'an type problems), zero-sum Ramsey theory, and interpolation theorems in graph theory. A role-model of these problems is the following: Let $G$ be a graph with $e(G)$ edges. We say that $G$ is omnitonal if there exists a function ${\rm ot}(n,G)$ such that the following holds true for $n$ sufficiently large: For any $2$-coloring $f: E(K_n) \to \{red, blue \}$ such that there are more than ${\rm ot}(n,G)$ edges from each color, and for any pair of non-negative integers $r$ and $b$ with $r+b = e(G)$, there is a copy of $G$ in $K_n$ with exactly $r$ red edges and $b$ blue edges. We give a structural characterization of omnitonal graphs from which we deduce that omnitonal graphs are, in particular, bipartite graphs, and prove further that, for an omnitonal graph $G$, ${\rm ot}(n,G) = \mathcal{O}(n^{2 - \frac{1}{m}})$, where $m = m(G)$ depends only on $G$. We also present a class of graphs for which ${\rm ot}(n,G) = ex(n,G)$, the celebrated Tur\'an numbers. Many more results and problems of similar flavor are presented.
-
arXiv:1809.10088 (Published 2018-09-26)
Non-monochromatic Triangles in a 2-Edge-Coloured Graph
Categories: math.COLet $G = (V,E)$ be a simple graph and let $\{R,B\}$ be a partition of $E$. We prove that whenever $|E| + \min\{ |R|, |B| \} > { |V| \choose 2 }$, there exists a subgraph of $G$ isomorphic to $K_3$ which contains edges from both $R$ and $B$. We conjecture a natural generalization to partitions with more blocks.
-
arXiv:1806.00825 (Published 2018-06-03)
Short rainbow cycles in sparse graphs
Matt DeVos, Sebastián González Hermosillo de la Maza, Krystal Guo, Daryl Funk, Tony Huynh, Bojan Mohar, Amanda MontejanoComments: 6 pages, 2 figuresLet $G$ be a simple $n$-vertex graph and $c$ be a colouring of $E(G)$ with $n$ colours, where each colour class has size at least $2$. We prove that $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{2} \rceil$, which is best possible. Our result settles a special case of a strengthening of the Caccetta-H\"aggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids.
-
arXiv:1708.09777 (Published 2017-08-31)
Zero-sum $K_m$ over $\mathbb{Z}$ and the story of $K_4$
We prove the following results solving a problem raised in [Y. Caro, R. Yuster, On zero-sum and almost zero-sum subgraphs over $\mathbb{Z}$, Graphs Combin. 32 (2016), 49--63]. For a positive integer $m\geq 2$, $m\neq 4$, there are infinitely many values of $n$ such that the following holds: There is a weighting function $f:E(K_n)\to \{-1,1\}$ (and hence a weighting function $f: E(K_n)\to \{-1,0,1\}$), such that $\sum_{e\in E(K_n)}f(e)=0$ but, for every copy $H$ of $K_m$ in $K_n$, $\sum_{e\in E(H)}f(e)\neq 0$. On the other hand, for every integer $n\geq 5$ and every weighting function $f:E(K_n)\to \{-1,1\}$ such that $|\sum_{e\in E(K_n)}f(e)|\leq \binom{n}{2}-h(n)$, where $h(n)=2(n+1)$ if $n \equiv 0$ (mod $4$) and $h(n)=2n$ if $n \not\equiv 0$ (mod $4$), there is always a copy $H$ of $K_4$ in $K_n$ for which $\sum_{e\in E(H)}f(e)=0$, and the value of $h(n)$ is sharp.
-
arXiv:1612.06523 (Published 2016-12-20)
Zero-sum subsequences in bounded-sum $\{-1, 1\}$-sequences
Comments: 29 pagesThe following result gives the flavor of this paper: Let $t$, $k$ and $q$ be integers such that $q\geq 0$, $0\leq t < k$ and $t \equiv k \,({\rm mod}\, 2)$, and let $s\in [0,t+1]$ be the unique integer satisfying $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Then for any integer $n$ such that \[n \ge \max\left\{k,\frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s\right\}\] and any function $f:[n]\to \{-1,1\}$ with $|\sum_{i=1}^nf(i)| \le q$, there is a set $B \subseteq [n]$ of $k$ consecutive integers with $|\sum_{y\in B}f(y)| \le t$. Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This and other similar results involving different subsequences are presented, including decompositions of sequences into subsequences of bounded weight.
-
arXiv:1509.03696 (Published 2015-09-12)
On transversal and $2$-packing numbers in straight line systems on $\mathbb{R}^{2}$
Comments: 22 pages, 7 figuresCategories: math.COA linear system is a pair $(X,\mathcal{F})$ where $\mathcal{F}$ is a finite family of subsets on a ground set $X$, and it satisfies that $|A\cap B|\leq 1$ for every pair of distinct subsets $A,B \in \mathcal{F}$. As an example of a linear system are the straight line systems, which family of subsets are straight line segments on $\mathbb{R}^{2}$. By $\tau$ and $\nu_2$ we denote the size of the minimal transversal and the 2--packing numbers of a linear system respectively. A natural problem is asking about the relationship of these two parameters; it is not difficult to prove that there exists a quadratic function $f$ holding $\tau\leq f(\nu_2)$. However, for straight line system we believe that $\tau\leq\nu_2-1$. In this paper we prove that for any linear system with $2$-packing numbers $\nu_2$ equal to $2, 3$ and $4$, we have that $\tau\leq\nu_2$. Furthermore, we prove that the linear systems that attains the equality have transversal and $2$-packing numbers equal to $4$, and they are a special family of linear subsystems of the projective plane of order $3$. Using this result we confirm that all straight line systems with $\nu_2\in\{2,3,4\}$ satisfies $\tau\leq\nu_2-1$.
-
arXiv:1502.04413 (Published 2015-02-16)
The structure of rainbow-free colorings for linear equations on three variables in Zp
Categories: math.COLet p be a prime number and Zp be the cyclic group of order p. A coloring of Zp is called rainbow-free with respect to a certain equation, if it contains no rainbow solution of the same, that is, a solution whose elements have pairwise distinct colors. In this paper we describe the structure of rainbow-free 3-colorings of Zp with respect to all linear equations on three variables. Consequently, we determine those linear equations on three variables for which every 3-coloring (with nonempty color classes) of Zp contains a rainbow solution of it.
-
A Rainbow Ramsey Analogue of Rado's Theorem
We present a Rainbow Ramsey version of the well-known Ramsey-type theorem of Richard Rado. We use techniques from the Geometry of Numbers. We also disprove two conjectures proposed in the literature.
-
arXiv:1402.5739 (Published 2014-02-24)
The chromatic number of comparability 3-hypergraphs
Categories: math.COBeginning with the concepts of orientation for a 3-hypergraph and transitivity for an oriented 3-hypergraph, it is natural to study the class of comparability 3-hypergraphs (those that can be transitively oriented). In this work we show three different behaviors in respect to the relationship between the chromatic number and the clique number of a comparability 3-hypergraph, this is in contrast with the fact that a comparability simple graph is a perfect graph.
-
A New Proof of Kemperman's Theorem
Let $G$ be an additive abelian group and let $A,B \subseteq G$ be finite and nonempty. The pair $(A,B)$ is called critical if the sumset $A+B = {a+b \mid $a \in A$ and $b\in B$}$ satisfies $|A+B| < |A| + |B|$. Vosper proved a theorem which characterizes all critical pairs in the special case when $|G|$ is prime. Kemperman generalized this by proving a structure theorem for critical pairs in an arbitrary abelian group. Here we give a new proof of Kemperman's Theorem.