Source author record

Simona Boyadzhiyska

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms

Catalog footprint

Research overview

4works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Fixed-point cycles and EFX allocations

We study edge-labelings of the complete bidirected graph $\overset{\tiny\leftrightarrow}{K}_n$ with functions from the set $[d] = \{1, \dots, d\}$ to itself. We call a cycle in $\overset{\tiny\leftrightarrow}{K}_n$ a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given $d$ , we ask for the largest value of $n$ , denoted $R_f(d)$ , for which there exists a fixed-point-free labeling of $\overset{\tiny\leftrightarrow}{K}_n$ . Determining $R_f(d)$ for all $d >0$ is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra, who proved that $d \leq R_f(d) \leq d^4+d$ and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound $R_f(d) \leq d^{2 + o(1)}$ , yielding an efficient ${(1-\varepsilon)}$ -EFX allocation with $n$ agents and $O(n^{0.67})$ unallocated goods for any constant $\varepsilon \in (0,1/2]$ ; this improves the bound of $O(n^{0.8})$ of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. Additionally, we prove the stronger upper bound $2d-2$ , in the case where all edge-labels are permulations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of $\mathbb{Z}_d$ , was recently considered by Alon and Krivelevich and by Mészáros and Steiner. Our result improves the bounds obtained by these authors and extends them to labelings from an arbitrary (not necessarily commutative) group, while also simplifying the proof.

preprint2022arXiv

Ramsey equivalence for asymmetric pairs of graphs

A graph $F$ is Ramsey for a pair of graphs $(G,H)$ if any red/blue-coloring of the edges of $F$ yields a copy of $G$ with all edges colored red or a copy of $H$ with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case $G=H$ , received considerable attention. This led to the open question whether there are connected graphs $G$ and $G'$ such that $(G,G)$ and $(G',G')$ are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several non-trivial families of Ramsey equivalent pairs of connected graphs. Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form $(T,K_t)$ , where $T$ is a tree and $K_t$ is a complete graph. We show that, if $T$ belongs to a certain family of trees, including all non-trivial stars, then $(T,K_t)$ is Ramsey equivalent to a family of pairs of the form $(T,H)$ , where $H$ is obtained from $K_t$ by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for $(T,H)$ to be Ramsey equivalent to $(T,K_t)$ , $H$ must have roughly this form. On the other hand, we prove that for many other trees $T$ , including all odd-diameter trees, $(T,K_t)$ is not equivalent to any such pair, not even to the pair $(T, K_t\cdot K_2)$ , where $K_t\cdot K_2$ is a complete graph $K_t$ with a single edge attached.

preprint2021arXiv

Subspace coverings with multiplicities

We study the problem of determining the minimum number $f(n,k,d)$ of affine subspaces of codimension $d$ that are required to cover all points of $\mathbb{F}_2^n\setminus \{\vec{0}\}$ at least $k$ times while covering the origin at most $k-1$ times. The case $k=1$ is a classic result of Jamison, which was independently obtained by Brouwer and Schrijver for $d = 1$ . The value of $f(n,1,1)$ also follows from a well-known theorem of Alon and Füredi about coverings of finite grids in affine spaces over arbitrary fields. Here we determine the value of this function exactly in various ranges of the parameters. In particular, we prove that for $k \ge 2^{n-d-1}$ we have $f(n,k,d)=2^d k - \left \lfloor \frac{k}{2^{n-d}} \right \rfloor$ , while for $n > 2^{2^d k-k-d+1}$ we have $f(n,k,d)= n + 2^dk-d-2$ , and also study the transition between these two ranges. While previous work in this direction has primarily employed the polynomial method, we prove our results through more direct combinatorial and probabilistic arguments, and also exploit a connection to coding theory.

preprint2020arXiv

Minimal Ramsey graphs with many vertices of small degree

Given any graph $H$ , a graph $G$ is said to be $q$ -Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$ . Further, such a graph $G$ is said to be minimal $q$ -Ramsey for $H$ if additionally no proper subgraph $G'$ of $G$ is $q$ -Ramsey for $H$ . In 1976, Burr, Erdős, and Lovász initiated the study of the parameter $s_q(H)$ , defined as the smallest minimum degree among all minimal $q$ -Ramsey graphs for $H$ . In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$ -Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$ -Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$ -abundant. Among other results, we prove that every cycle is $s_q$ -abundant for any integer $q\geq 2$ . We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.

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.