BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Maria Axenovich

Maria Axenovich contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete MathematicsQuantitative Methods

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
16works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

16 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;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&#39;s conjecture up to a linear factor.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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 &#34;small&#34; 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).

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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)}$.

0 citations0 reviewsNo code linkedOpen access
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&#39;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 &#34;wide&#34; Steiner tree containing all the precolored vertices.

0 citations0 reviewsNo code linkedOpen access
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 &#34;yes&#34; if $G$ is not a star and $H$ does not contain a pendent edge.

0 citations0 reviewsNo code linkedOpen access