Source author record

Maria Axenovich

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Computational Geometry Quantitative Methods

Catalog footprint

Research overview

35works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Generalized Turán densities in the hypercube

A classical extremal, or Turán-type problem asks to determine ${\rm ex}(G, H)$ , the largest number of edges in a subgraph of a graph $G$ which does not contain a subgraph isomorphic to $H$ . Alon and Shikhelman introduced the so-called generalized extremal number ${\rm ex}(G,T,H)$ , defined to be the maximum number of subgraphs isomorphic to $T$ in a subgraph of $G$ that contains no subgraphs isomorphic to $H$ . In this paper we investigate the case when $G = Q_n$ , the hypercube of dimension $n$ , and $T$ and $H$ are smaller hypercubes or cycles.

preprint2022arXiv

Interval colorings of graphs -- coordinated and unstable no-wait schedules

A proper edge-coloring of a graph is an interval coloring if the labels on the edges incident to any vertex form an interval of consecutive integers. Interval thickness s(G) of a graph G is the smallest number of interval colorable graphs edge-decomposing G. We prove that s(G)=o(n) for any graph G on n vertices. This improves the previously known bound of 2n/5 by Asratian, Casselgren, and Petrosyan. While we do not have a single example of a graph with interval thickness strictly greater than 2, we construct bipartite graphs whose interval spectrum has arbitrarily many arbitrarily large gaps. Here, an interval spectrum of a graph is the set of all integers t such that the graph has an interval coloring using t colors. Interval colorings of bipartite graphs naturally correspond to no-wait schedules, say for parent-teacher conferences, where a conversation between any teacher and any parent lasts the same amount of time. Our results imply that any such conference with $n$ participants can be coordinated in o(n) no-wait periods. In addition, we show that for any integers t and T, t<T, there is a set of pairs of parents and teachers wanting to talk to each other, such that any no-wait schedules are unstable -- they could last t hours and could last T hours, but there is no possible no-wait schedule lasting x hours if t<x<T.

preprint2022arXiv

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Erdős, Füredi, Rothschild and Sós initiated a study of classes of graphs that forbid every induced subgraph on a given number $m$ of vertices and number $f$ of edges. Extending their notation to $r$ -graphs, we write $(n,e) \to_r (m,f)$ if every $r$ -graph $G$ on $n$ vertices with $e$ edges has an induced subgraph on $m$ vertices and $f$ edges. The \emph{forcing density} of a pair $(m,f)$ is $σ_r(m,f) =\left. \limsup\limits_{n \to \infty} \frac{|\{e : (n,e) \to_r (m,f)\}|}{\binom{n}{r}} \right. .$ In the graph setting it is known that there are infinitely many pairs $(m, f)$ with positive forcing density. Weber asked if there is a pair of positive forcing density for $r\geq 3$ apart from the trivial ones $(m, 0)$ and $(m, \binom{m}{r})$ . Answering her question, we show that $(6,10)$ is such a pair for $r=3$ and conjecture that it is the unique such pair. Further, we find necessary conditions for a pair to have positive forcing density, supporting this conjecture.

preprint2021arXiv

Long path and cycle decompositions of even hypercubes

We consider edge decompositions of the $n$ -dimensional hypercube $Q_n$ into isomorphic copies of a given graph $H$ . While a number of results are known about decomposing $Q_n$ into graphs from various classes, the simplest cases of paths and cycles of a given length are far from being understood. A conjecture of Erde asserts that if $n$ is even, $\ell < 2^n$ and $\ell$ divides the number of edges of $Q_n$ , then the path of length $\ell$ decomposes $Q_n$ . Tapadia et al.\ proved that any path of length $2^mn$ , where $2^m<n$ , satisfying these conditions decomposes $Q_n$ . Here, we make progress toward resolving Erde's conjecture by showing that cycles of certain lengths up to $2^{n+1}/n$ decompose $Q_n$ . As a consequence, we show that $Q_n$ can be decomposed into copies of any path of length at most $2^{n}/n$ dividing the number of edges of $Q_n$ , thereby settling Erde's conjecture up to a linear factor.

preprint2021arXiv

Sum-distinguishing number of sparse hypergraphs

A vertex labeling of a hypergraph is sum distinguishing if it uses positive integers and the sums of labels taken over the distinct hyperedges are distinct. Let s(H) be the smallest integer N such that there is a sum-distinguishing labeling of H with each label at most N. The largest value of s(H) over all hypergraphs on n vertices and m hyperedges is denoted s(n,m). We prove that s(n,m) is almost-quadratic in m as long as m is not too large. More precisely, the following holds: If n < m < n^{O(1)} then s(n,m)= m^2/w(m), where w(m) is a function that goes to infinity and is smaller than any polynomial in m. The parameter s(n,m) has close connections to several other graph and hypergraph functions, such as the irregularity strength of hypergraphs. Our result has several applications, notably: 1. We answer a question of Gyarfas et al. whether there are n-vertex hypergraphs with irregularity strength greater than 2n. In fact we show that there are n-vertex hypergraphs with irregularity strength at least n^{2-o(1)}. 2. Our results imply that s*(n)=n^2/w(n) where s*(n) is the distinguishing closed-neighborhood number, i.e., the smallest integer N such that any n-vertex graph allows for a vertex labeling with positive integers at most N so that the sums of labels on distinct closed neighborhoods of vertices are distinct.

preprint2020arXiv

Bipartite independence number in graphs with bounded maximum degree

We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole of size $t$ in a bipartite graph $G$ is a copy of $K_{t, t}$ in the bipartite complement of $G$ . Let $f(n, Δ)$ be the largest $k$ for which every $n \times n$ bipartite graph with maximum degree $Δ$ in one of the parts has a bi-hole of size $k$ . Determining $f(n, Δ)$ is thus the bipartite analogue of finding the largest independent set in graphs with a given number of vertices and bounded maximum degree. Our main result determines the asymptotic behavior of $f(n, Δ)$ . More precisely, we show that for large but fixed $Δ$ and $n$ sufficiently large, $f(n, Δ) = Θ(\frac{\log Δ}Δ n)$ . We further address more specific regimes of $Δ$ , especially when $Δ$ is a small fixed constant. In particular, we determine $f(n, 2)$ exactly and obtain bounds for $f(n, 3)$ , though determining the precise value of $f(n, 3)$ is still open.

preprint2020arXiv

Induced Ramsey number for a star versus a fixed graph

For graphs G and H, let the induced Ramsey number IR(H,G) be the smallest number of vertices in a graph F such that any coloring of the edges of F in red and blue, there is either a red induced copy of H or a blue induced copy of G. In this note we consider the case when G=Sn is a star on n edges, for large n, and H is a fixed graph. We prove that (r-1)n < IR(H, Sn) < (r-1)(r-1)n + cn, for any c>0, sufficiently large n, and r denoting the chromatic number of H. The lower bound is asymptotically tight for any fixed bipartite H. The upper bound is attained up to a constant factor, for example by a clique H.

preprint2018arXiv

Induced Saturation of Graphs

A graph $G$ is $H$ -saturated for a graph $H$ , if $G$ does not contain a copy of $H$ but adding any new edge to $G$ results in such a copy. An $H$ -saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively. A graph $G$ is $H$ -induced-saturated if $G$ does not have an induced subgraph isomorphic to $H$ , but adding an edge to $G$ from its complement or deleting an edge from $G$ results in an induced copy of $H$ . It is not immediate anymore that $H$ -induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no $P_4$ -induced-saturated graph. Behrens et.al. (2016) proved that if $H$ belongs to a few simple classes of graphs such as a class of odd cycles of length at least $5$ , stars of size at least $2$ , or matchings of size at least $2$ , then there is an $H$ -induced-saturated graph. This paper addresses the existence question for $H$ -induced-saturated graphs. It is shown that Cartesian products of cliques are $H$ -induced-saturated graphs for $H$ in several infinite families, including large families of trees. A complete characterization of all connected graphs $H$ for which a Cartesian product of two cliques is an $H$ -induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided.

preprint2018arXiv

Polychromatic Colorings on the Integers

We show that for any set $S\subseteq \mathbb{Z}$ , $|S|=4$ there exists a 3-coloring of $\mathbb{Z}$ in which every translate of $S$ receives all three colors. This implies that $S$ has a codensity of at most $1/3$ , proving a conjecture of Newman [D. J. Newman, Complements of finite sets of integers, Michigan Math. J. 14 (1967) 481--486]. We also consider related questions in $\mathbb{Z}^d$ , $d\geq 2$ .

preprint2016arXiv

$Q_2$ -free families in the Boolean lattice

For a family $\mathcal{F}$ of subsets of [n]=\{1, 2, ..., n} ordered by inclusion, and a partially ordered set P, we say that $\mathcal{F}$ is P-free if it does not contain a subposet isomorphic to P. Let $ex(n, P)$ be the largest size of a P-free family of subsets of [n]. Let $Q_2$ be the poset with distinct elements a, b, c, d, a<b, c<d; i.e., the 2-dimensional Boolean lattice. We show that $2N -o(N) \leq ex(n, Q_2)\leq 2.283261N +o(N),$ where $N = \binom{n}{\lfloor n/2 \rfloor}$ . We also prove that the largest $Q_2$ -free family of subsets of [n] having at most three different sizes has at most 2.20711N members.

preprint2016arXiv

A note on short cycles in a hypercube

How many edges can a quadrilateral-free subgraph of a hypercube have? This question was raised by Paul Erdős about $27$ years ago. His conjecture that such a subgraph asymptotically has at most half the edges of a hypercube is still unresolved. Let $f(n,C_l)$ be the largest number of edges in a subgraph of a hypercube $Q_n$ containing no cycle of length $l$ . It is known that $f(n, C_l) = o(|E(Q_n)|)$ , when $l= 4k$ , $k\geq 2$ and that $f(n, C_6) \geq \frac{1}{3} |E(Q_n)|$ . It is an open question to determine $f(n, C_l)$ for $l=4k+2$ , $k\geq 2$ . Here, we give a general upper bound for $f(n,C_l)$ when $l=4k+2$ and provide a coloring of $E(Q_n)$ by $4$ colors containing no induced monochromatic $C_{10}$ .

preprint2016arXiv

A version of Szemerédi's regularity lemma for multicolored graphs and directed graphs that is suitable for induced graphs

In this manuscript we develop a version of Szemerédi's regularity lemma that is suitable for analyzing multicolorings of complete graphs and directed graphs. In this, we follow the proof of Alon, Fischer, Krivelevich and M. Szegedy [Combinatorica, 20(4) (2000), 451--476] who prove a similar result for graphs. The purpose is to extend classical results on dense hereditary properties, such as the speed of the property or edit distance, to the above-mentioned combinatorial objects.

preprint2016arXiv

Avoiding patterns in matrices via a small number of changes

Let ${\cal A}=\{A_1,\ldots, A_r\}$ be a partition of a set $\{1,\ldots,m\}\times\{1,\ldots, n\}$ into $r$ nonempty subsets, and $A=(a_{ij})$ be an $m\times n$ matrix. We say that $A$ has a pattern ${\cal A}$ provided that $a_{ij}=a_{i'j'}$ if and only if $(i,j),(i',j')\in A_t$ for some $t\in\{1,\ldots,r\}$ . In this note we study the following function $f$ defined on the set of all $m\times n$ matrices $M$ with $s$ distinct entries: $f(M; {\cal A})$ is the smallest number of positions where the entries of $M$ need to be changed such that the resulting matrix does not have any submatrix with pattern ${\cal A}$ . We give an asymptotically tight value for $$ f(m,n; s, {\cal A}) = \max\{f(M; {\cal A}): M \mbox{ is an } m\times n\mbox{ matrix with at most } s \mbox{ distinct entries}\} . $$

preprint2016arXiv

Avoiding rainbow induced subgraphs in vertex-colorings

For a fixed graph $H$ on $k$ vertices, and a graph $G$ on at least $k$ vertices, we write $G\rightarrow H$ if in any vertex-coloring of $G$ with $k$ colors, there is an induced subgraph isomorphic to $H$ whose vertices have distinct colors. In other words, if $G\rightarrow H$ then a totally multicolored induced copy of $H$ is unavoidable in any vertex-coloring of $G$ with $k$ colors. In this paper, we show that, with a few notable exceptions, for any graph $H$ on $k$ vertices and for any graph $G$ which is not isomorphic to $H$ , $G\not\!\rightarrow H$ . We explicitly describe all exceptional cases. This determines the induced vertex-anti-Ramsey number for all graphs and shows that totally multicolored induced subgraphs are, in most cases, easily avoidable.

preprint2016arXiv

Brooks Type Results for Conflict-Free Colorings and {a, b}-factors in graphs

A vertex-coloring of a hypergraph is conflict-free, if each edge contains a vertex whose color is not repeated on any other vertex of that edge. Let $f(r, Δ)$ be the smallest integer $k$ such that each $r$ -uniform hypergraph of maximum vertex degree $Δ$ has a conflict-free coloring with at most $k$ colors. As shown by Tardos and Pach, similarly to a classical Brooks' type theorem for hypergraphs, $f(r, Δ)\leq Δ+1$ . Compared to Brooks' theorem, according to which there is only a couple of graphs/hypergraphs that attain the $Δ+1$ bound, we show that there are several infinite classes of uniform hypergraphs for which the upper bound is attained. We provide bounds on $f(r, Δ)$ in terms of~ $Δ$ for large~ $Δ$ and establish the connection between conflict-free colorings and so-called $\{t, r-t\}$ -factors in $r$ -regular graphs. Here, a $\{t, r-t\}$ -factor is a factor in which each degree is either $t$ or $r-t$ . Among others, we disprove a conjecture of Akbari and Kano~[Graphs and Combinatorics 30(4):821--826, 2014] stating that there is a $\{t,r-t\}$ -factor in every $r$ -regular graph for odd $r$ and any odd $t<\frac{r}{3}$ .

preprint2016arXiv

Chromatic number of ordered graphs with forbidden ordered subgraphs

It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., graphs with a linear ordering on their vertex set, and the function f(H) = sup{chi(G) | G in Forb(H)} where Forb(H) denotes the set of all ordered graphs that do not contain a copy of H. If H contains a cycle, then as in the case of unordered graphs, f(H) is infinity. However, in contrast to the unordered graphs, we describe an infinite family of ordered forests H with infinite f(H). An ordered graph is crossing if there are two edges uv and u'v' with u < u' < v < v'. For connected crossing ordered graphs H we reduce the problem of determining whether f(H) is finite to a family of so-called monotonically alternating trees. For non-crossing H we prove that f(H) is finite if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which we call bonnets. For such forests H, we show that f(H) <= 2^|V(H)| and that f(H) <= 2|V(H)|-3 if H is connected.

preprint2016arXiv

High girth hypergraphs with unavoidable monochromatic or rainbow edges

A classical result of Erdős and Hajnal claims that for any integers $k, r, g \geq 2$ there is an $r$ -uniform hypergraph of girth at least $g$ with chromatic number at least $k$ . This implies that there are sparse hypergraphs such that in any coloring of their vertices with at most $k-1$ colors there is a monochromatic hyperedge. We show that for any integers $r, g\geq 2$ there is an $r$ -uniform hypergraph of girth at least $g$ such that in any coloring of its vertices there is either a monochromatic or a rainbow (totally multicolored) edge. We give a probabilistic and a deterministic proof of this result.

preprint2016arXiv

Multicolor and directed edit distance

The editing of a combinatorial object is the alteration of some of its elements such that the resulting object satisfies a certain fixed property. The edit problem for graphs, when the edges are added or deleted, was first studied independently by the authors and Kézdy [J. Graph Theory (2008), 58(2), 123--138] and by Alon and Stav [Random Structures Algorithms (2008), 33(1), 87--104]. In this paper, a generalization of graph editing is considered for multicolorings of the complete graph as well as for directed graphs. Specifically, the number of edge-recolorings sufficient to be performed on any edge-colored complete graph to satisfy a given hereditary property is investigated. The theory for computing the edit distance is extended using random structures and so-called types or colored homomorphisms of graphs.

preprint2016arXiv

On the editing distance of graphs

An edge-operation on a graph $G$ is defined to be either the deletion of an existing edge or the addition of a nonexisting edge. Given a family of graphs $\mathcal{G}$ , the editing distance from $G$ to $\mathcal{G}$ is the smallest number of edge-operations needed to modify $G$ into a graph from $\mathcal{G}$ . In this paper, we fix a graph $H$ and consider ${\rm Forb}(n,H)$ , the set of all graphs on $n$ vertices that have no induced copy of $H$ . We provide bounds for the maximum over all $n$ -vertex graphs $G$ of the editing distance from $G$ to ${\rm Forb}(n,H)$ , using an invariant we call the {\it binary chromatic number} of the graph $H$ . We give asymptotically tight bounds for that distance when $H$ is self-complementary and exact results for several small graphs $H$ .

preprint2016arXiv

On the strong chromatic number of graphs

The strong chromatic number, $χ_S(G)$ , of an $n$ -vertex graph $G$ is the smallest number $k$ such that after adding $k\lceil n/k\rceil-n$ isolated vertices to $G$ and considering {\bf any} partition of the vertices of the resulting graph into disjoint subsets $V_1, \ldots, V_{\lceil n/k\rceil}$ of size $k$ each, one can find a proper $k$ -vertex-coloring of the graph such that each part $V_i$ , $i=1, \ldots, \lceil n/k\rceil$ , contains exactly one vertex of each color. For any graph $G$ with maximum degree $Δ$ , it is easy to see that $χ_S(G)\geqΔ+1$ . Recently, Haxell proved that $χ_S(G) \leq 3Δ-1$ . In this paper, we improve this bound for graphs with large maximum degree. We show that $χ_S(G)\leq 2Δ$ if $Δ\geq n/6$ and prove that this bound is sharp.

preprint2016arXiv

On weighted Ramsey numbers

The weighted Ramsey number, ${\rm wR}(n,k)$ , is the minimum $q$ such that there is an assignment of nonnegative real numbers (weights) to the edges of $K_n$ with the total sum of the weights equal to ${n\choose 2}$ and there is a Red/Blue coloring of edges of the same $K_n$ , such that in any complete $k$ -vertex subgraph $H$ , of $K_n$ , the sum of the weights on Red edges in $H$ is at most $q$ and the sum of the weights on Blue edges in $H$ is at most $q$ . This concept was introduced recently by Fujisawa and Ota. We provide new bounds on ${\rm wR}(n,k)$ , for $k\geq 4$ and $n$ large enough and show that determining ${\rm wR}(n,3)$ is asymptotically equivalent to the problem of finding the fractional packing number of monochromatic triangles in colorings of edges of complete graphs with two colors.

preprint2016arXiv

Sub-Ramsey numbers for arithmetic progressions

Let the integers $1,\ldots,n$ be assigned colors. Szemerédi's theorem implies that if there is a dense color class then there is an arithmetic progression of length three in that color. We study the conditions on the color classes forcing totally multicolored arithmetic progressions of length 3. Let $f(n)$ be the smallest integer $k$ such that there is a coloring of $\{1, \ldots, n\}$ without totally multicolored arithmetic progressions of length three and such that each color appears on at most $k$ integers. We provide an exact value for $f(n)$ when $n$ is sufficiently large, and all extremal colorings. In particular, we show that $f(n)= 8n/17 + O(1)$ . This completely answers a question of Alon, Caro and Tuza.

preprint2015arXiv

Boolean lattices: Ramsey properties and embeddings

A subposet $Q'$ of a poset $Q$ is a copy of a poset $P$ if there is a bijection $f$ between elements of $P$ and $Q'$ such that $x\leq y$ in $P$ iff $f(x)\leq f(y)$ in $Q'$ . For posets $P, P'$ , let the poset Ramsey number $R(P,P')$ be the smallest $N$ such that no matter how the elements of the Boolean lattice $Q_N$ are colored red and blue, there is a copy of $P$ with all red elements or a copy of $P'$ with all blue elements. We provide some general bounds on $R(P,P')$ and focus on the situation when $P$ and $P'$ are both Boolean lattices. In addition, we give asymptotically tight bounds for the number of copies of $Q_n$ in $Q_N$ and for a multicolor version of a poset Ramsey number.

preprint2015arXiv

Conditions on Ramsey non-equivalence

Given a graph H, a graph G is called a Ramsey graph of H if there is a monochromatic copy of H in every coloring of the edges of G with two colors. Two graphs G, H are called Ramsey equivalent if they have the same set of Ramsey graphs. Fox et al. [J. Combin. Theory Ser. B 109 (2014), 120--133] asked whether there are two non-isomorphic connected graphs that are Ramsey equivalent. They proved that a clique is not Ramsey equivalent to any other connected graph. Results of Nesetril et al. showed that any two graphs with different clique number [Combinatorica 1(2) (1981), 199--202] or different odd girth [Comment. Math. Univ. Carolin. 20(3) (1979), 565--582] are not Ramsey equivalent. These are the only structural graph parameters we know that "distinguish" two graphs in the above sense. This paper provides further supportive evidence for a negative answer to the question of Fox et al. by claiming that for wide classes of graphs, chromatic number is a distinguishing parameter. In addition, it is shown here that all stars and paths and all connected graphs on at most 5 vertices are not Ramsey equivalent to any other connected graph. Moreover two connected graphs are not Ramsey equivalent if they belong to a special class of trees or to classes of graphs with clique-reduction properties.

preprint2015arXiv

Density of Range Capturing Hypergraphs

For a finite set $X$ of points in the plane, a set $S$ in the plane, and a positive integer $k$ , we say that a $k$ -element subset $Y$ of $X$ is captured by $S$ if there is a homothetic copy $S'$ of $S$ such that $X\cap S' = Y$ , i.e., $S'$ contains exactly $k$ elements from $X$ . A $k$ -uniform $S$ -capturing hypergraph $H = H(X,S,k)$ has a vertex set $X$ and a hyperedge set consisting of all $k$ -element subsets of $X$ captured by $S$ . In case when $k=2$ and $S$ is convex these graphs are planar graphs, known as convex distance function Delaunay graphs. In this paper we prove that for any $k\geq 2$ , any $X$ , and any convex compact set $S$ , the number of hyperedges in $H(X,S,k)$ is at most $(2k-1)|X| - k^2 + 1 - \sum_{i=1}^{k-1}a_i$ , where $a_i$ is the number of $i$ -element subsets of $X$ that can be separated from the rest of $X$ with a straight line. In particular, this bound is independent of $S$ and indeed the bound is tight for all "round" sets $S$ and point sets $X$ in general position with respect to $S$ . This refines a general result of Buzaglo, Pinchasi and Rote stating that every pseudodisc topological hypergraph with vertex set $X$ has $O(k^2|X|)$ hyperedges of size $k$ or less.

preprint2015arXiv

Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Recently, Borodin, Kostochka, and Yancey (On $1$ -improper $2$ -coloring of sparse graphs. Discrete Mathematics, 313(22), 2013) showed that the vertices of each planar graph of girth at least $7$ can be $2$ -colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least $6$ admits a vertex coloring in $2$ colors such that each monochromatic component is a path of length at most $14$ . Moreover, we show a list version of this result. On the other hand, for each positive integer $t\geq 3$ , we construct a planar graph of girth $4$ such that in any coloring of vertices in $2$ colors there is a monochromatic path of length at least $t$ . It remains open whether each planar graph of girth $5$ admits a $2$ -coloring with no long monochromatic paths.

preprint2014arXiv

Spectrum of mixed bi-uniform hypergraphs

A mixed hypergraph is a triple $H=(V,\mathcal{C},\mathcal{D})$ , where $V$ is a set of vertices, $\mathcal{C}$ and $\mathcal{D}$ are sets of hyperedges. A vertex-coloring of $H$ is proper if $C$ -edges are not totally multicolored and $D$ -edges are not monochromatic. The feasible set $S(H)$ of $H$ is the set of all integers, $s$ , such that $H$ has a proper coloring with $s$ colors. Bujtás and Tuza [Graphs and Combinatorics 24 (2008), 1--12] gave a characterization of feasible sets for mixed hypergraphs with all $C$ - and $D$ -edges of the same size $r$ , $r\geq 3$ . In this note, we give a short proof of a complete characterization of all possible feasible sets for mixed hypergraphs with all $C$ -edges of size $\ell$ and all $D$ -edges of size $m$ , where $\ell, m \geq 2$ . Moreover, we show that for every sequence $(r(s))_{s=\ell}^n$ , $n \geq \ell$ , of natural numbers there exists such a hypergraph with exactly $r(s)$ proper colorings using $s$ colors, $s = \ell,\ldots,n$ , and no proper coloring with more than $n$ colors. Choosing $\ell = m=r$ this answers a question of Bujtás and Tuza, and generalizes their result with a shorter proof.

preprint2013arXiv

Multicolor Ramsey numbers for triple systems

Given an $r$ -uniform hypergraph $H$ , the multicolor Ramsey number $r_k(H)$ is the minimum $n$ such that every $k$ -coloring of the edges of the complete $r$ -uniform hypergraph $K_n^r$ yields a monochromatic copy of $H$ . We investigate $r_k(H)$ when $k$ grows and $H$ is fixed. For nontrivial 3-uniform hypergraphs $H$ , the function $r_k(H)$ ranges from $\sqrt{6k}(1+o(1))$ to double exponential in $k$ . We observe that $r_k(H)$ is polynomial in $k$ when $H$ is $r$ -partite and at least single-exponential in $k$ otherwise. Erdős, Hajnal and Rado gave bounds for large cliques $K_s^r$ with $s\ge s_0(r)$ , showing its correct exponential tower growth. We give a proof for cliques of all sizes, $s>r$ , using a slight modification of the celebrated stepping-up lemma of Erdős and Hajnal. For 3-uniform hypergraphs, we give an infinite family with sub-double-exponential upper bound and show connections between graph and hypergraph Ramsey numbers. Specifically, we prove that $r_k(K_3)\le r_{4k}(K_4^3-e)\le r_{4k}(K_3)+1,$ where $K_4^3-e$ is obtained from $K_4^3$ by deleting an edge. We provide some other bounds, including single-exponential bounds for $F_5=\{abe,abd,cde\}$ as well as asymptotic or exact values of $r_k(H)$ when $H$ is the bow $\{abc,ade\}$ , kite $\{abc,abd\}$ , tight path $\{abc,bcd,cde\}$ or the windmill $\{abc,bde,cef,bce\}$ . We also determine many new "small" Ramsey numbers and show their relations to designs. For example, the lower bound for $r_6(kite)=8$ is demonstrated by decomposing the triples of $[7]$ into six partial STS (two of them are Fano planes).

preprint2013arXiv

Online and size anti-Ramsey numbers

A graph is properly edge-colored if no two adjacent edges have the same color. The smallest number of edges in a graph any of whose proper edge colorings contains a totally multicolored copy of a graph H is the size anti-Ramsey number AR_s(H) of H. This number in offline and online setting is investigated here.

preprint2013arXiv

Twins in graphs

A basic pigeonhole principle insures an existence of two objects of the same type if the number of objects is larger than the number of types. Can such a principle be extended to a more complex combinatorial structure? Here, we address such a question for graphs. We call two disjoint subsets $A, B$ of vertices \emph{\textbf{twins}} if they have the same cardinality and induce subgraphs of the same size. Let $t(G)$ be the largest $k$ such that $G$ has twins on $k$ vertices each. We provide the bounds on $t(G)$ in terms of the number of edges and vertices using discrepancy results for induced subgraphs. In addition, we give conditions under which $t(G)= |V(G)|/2$ and show that if $G$ is a forest then $t(G) \geq |V(G)|/2 - 1$ .

preprint2012arXiv

A regularity lemma and twins in words

For a word $S$ , let $f(S)$ be the largest integer $m$ such that there are two disjoints identical (scattered) subwords of length $m$ . Let $f(n, Σ) = \min \{f(S): S \text{is of length} n, \text{over alphabet} Σ\}$ . Here, it is shown that $2f(n, \{0,1\}) = n-o(n)$ using the regularity lemma for words. I.e., any binary word of length $n$ can be split into two identical subwords (referred to as twins) and, perhaps, a remaining subword of length $o(n)$ . A similar result is proven for $k$ identical subwords of a word over an alphabet with at most $k$ letters.

preprint2012arXiv

Fork-forests in bi-colored complete bipartite graphs

Motivated by the problem in [6], which studies the relative efficiency of propositional proof systems, 2-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of $G=K_{n,n}$ are colored with black and white such that the number of black edges differs from the number of white edges by at most 1, then there are at least $n(1-1/\sqrt{2})$ vertex-disjoint forks with centers in the same partite set of $G$ . Here, a fork is a graph formed by two adjacent edges of different colors. The bound is sharp. Moreover, an algorithm running in time $O(n^2 \log n \sqrt{n α(n^2,n) \log n})$ and giving a largest such fork forest is found.

preprint2012arXiv

On homometric sets in graphs

For a vertex set $S\subseteq V(G)$ in a graph $G$ , the {\em distance multiset}, $D(S)$ , is the multiset of pairwise distances between vertices of $S$ in $G$ . Two vertex sets are called {\em homometric} if their distance multisets are identical. For a graph $G$ , the largest integer $h$ , such that there are two disjoint homometric sets of order $h$ in $G$ , is denoted by $h(G)$ . We slightly improve the general bound on this parameter introduced by Albertson, Pach and Young (2010) and investigate it in more detail for trees and graphs of bounded diameter. In particular, we show that for any tree $T$ on $n$ vertices $h(T) \geq \sqrt[3]{n}$ and for any graph $G$ of fixed diameter $d$ , $h(G) \geq cn^{1/ (2d-2)}$ .

preprint2011arXiv

List precoloring extension in planar graphs

A celebrated result of Thomassen states that not only can every planar graph be colored properly with five colors, but no matter how arbitrary palettes of five colors are assigned to vertices, one can choose a color from the corresponding palette for each vertex so that the resulting coloring is proper. This result is referred to as 5-choosability of planar graphs. Albertson asked whether Thomassen's theorem can be extended by precoloring some vertices which are at a large enough distance apart in a graph. Here, among others, we answer the question in the case when the graph does not contain short cycles separating precolored vertices and when there is a "wide" Steiner tree containing all the precolored vertices.

preprint2010arXiv

A note on monotonicity of mixed Ramsey numbers

For two graphs, $G$ , and $H$ , an edge-coloring of a complete graph is $(G,H)$ -good if there is no monochromatic subgraph isomorphic to $G$ and no rainbow subgraph isomorphic to $H$ in this coloring. The set of number of colors used by some $(G,H)$ -colorings of $K_n$ is called a mixed-Ramsey spectrum. This note addresses a fundamental question of whether the spectrum is an interval. It is shown that the answer is "yes" if $G$ is not a star and $H$ does not contain a pendent edge.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Maria Axenovich

Research overview

Is this your work?

35 publications

Generalized Turán densities in the hypercube

Interval colorings of graphs -- coordinated and unstable no-wait schedules

Unavoidable order-size pairs in hypergraphs -- positive forcing density

Long path and cycle decompositions of even hypercubes

Sum-distinguishing number of sparse hypergraphs

Bipartite independence number in graphs with bounded maximum degree

Induced Ramsey number for a star versus a fixed graph

Induced Saturation of Graphs

Polychromatic Colorings on the Integers

Q2Q_2Q2​-free families in the Boolean lattice

A note on short cycles in a hypercube

A version of Szemerédi's regularity lemma for multicolored graphs and directed graphs that is suitable for induced graphs

Avoiding patterns in matrices via a small number of changes

Avoiding rainbow induced subgraphs in vertex-colorings

Brooks Type Results for Conflict-Free Colorings and {a, b}-factors in graphs

Chromatic number of ordered graphs with forbidden ordered subgraphs

High girth hypergraphs with unavoidable monochromatic or rainbow edges

Multicolor and directed edit distance

On the editing distance of graphs

On the strong chromatic number of graphs

On weighted Ramsey numbers

Sub-Ramsey numbers for arithmetic progressions

Boolean lattices: Ramsey properties and embeddings

Conditions on Ramsey non-equivalence

Density of Range Capturing Hypergraphs

Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Spectrum of mixed bi-uniform hypergraphs

Multicolor Ramsey numbers for triple systems

Online and size anti-Ramsey numbers

Twins in graphs

A regularity lemma and twins in words

Fork-forests in bi-colored complete bipartite graphs

On homometric sets in graphs

List precoloring extension in planar graphs

A note on monotonicity of mixed Ramsey numbers

See the researcher in context

Building this map preview

$Q_2$ -free families in the Boolean lattice