2
$\begingroup$

Assume that $G$ is a (finite) abelian group and $M$ is a matroid whose ground set is $G$. Let $X$ and $Y$ be subsets of $G$, and $H$ is the stabilizer of $X+Y$. That is $X+Y+H=X+Y$. We denote the rank function of $M$ by $r$. Then can we say that $r(X+Y)\geq$ $r(X)+r(Y)-r(H)$? Or under what condition this can be true? I am fine to assume $M$ to be a partition matroid(or even a uniform matroid) and also assume $G$ is cyclic of prime order. (A similar result holds for the cardinality of sumsets of a given group, well-known as Kneser's theorem)

Note: To make the statement plausible, adding the condition of $X+Y$ to be independent won't hurt.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
+50
$\begingroup$

Without any condition on the matroid structure, there is really no reason for your inequality to hold.

For example, take $X=\{a\},Y=\{b\}$ so that $X+Y=\{a+b\}$ where $a,b$ are any nonzero elements of $G$. Then take any matroid structure such that $a+b$ is a loop but $a,b$ and $0$ are not. We have $0=r(X+Y)<r(X)+r(Y)-r(H)=1$.

Maybe you want to add some kind of compatibility condition between the group and matroid structures to make your question more interesting?

EDIT: Even in a very simple and and well-behaved setting (say $G$ cyclic and $M$ uniform), the inequality fails. For example, let $G=\mathbb{Z}/N\mathbb{Z}$ with the $n$-uniform matroid structure, where $n<N/2$. Let $X\subset [0, N/2)$ be any subset of size $n$. Then $r(X+X)=r(X)=r(Y)=n$ and $H$ is trivial so $r(H)=1$. Hence your inequality fails whenever $n>1$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks, Antonie. I just edited my question. I agree that assuming nothing on the group structure and no restriction on the matroid will make things very wild. $\endgroup$
    – Shahab
    Commented Sep 4, 2021 at 16:55
  • $\begingroup$ Is it understood, in the first place, that the matroid is closed under taking pairwise sumsets? And that its structure is compatible with the subset relation of the sets in $G$? $\endgroup$
    – Jukka Kohonen
    Commented Sep 4, 2021 at 21:10
  • $\begingroup$ The matroid is defined over a group, so sumsets are all belong to the ground set, $G$. The matroid itself may not be closed under taking pairwise sumsets. That is, if $X+Y$ is not an independent set, it is legit to discuss $r(X+Y)$ (which is equal to the cardinality of the largest subset of $X+Y$ that is independent in $M$) @Jukka Kohonen $\endgroup$
    – Shahab
    Commented Sep 4, 2021 at 22:28
  • $\begingroup$ Another counterexample: Take a sum-free subset of $A$ of $G$, and let $M$ be a matroid whose vertices set $V(M)$ is $A$. Set $X=Y=A$. Let $r(M)=n$. Then we have: $r(X+Y)=0$ but $r(x)=r(Y)=n$, and $r(H)\leq n$. This violates the claimed inequality $\endgroup$
    – Shahab
    Commented Sep 6, 2021 at 19:13
  • $\begingroup$ Yes @Antoine Labelle, you are right. I however hope that for certain subsets of probably a very small family of matroids it might be the case. Indeed, for situations that $X$ and $Y$ are not full-rank but $X+Y$ is close to being full-rank? $\endgroup$
    – Shahab
    Commented Sep 8, 2021 at 17:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .