6
$\begingroup$

I met the following two combinatorial concepts during a study outside of combinatorics. I am wondering if there are common terminologies in combinatorics.

  1. A finite graph $G$ has the following property:

For any vertex $a$ and edge $\{b,c\}$ of $G$, there is an edge connecting them: there is at least one of $\{a,b\}$ or $\{a,c\}$ in $G$.

  1. Let $P = \lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_k$ be an integer partition of $n$. Suppose that $P$ has the following property:

If there are two index sets $I$ and $J$ such that $\sum_{i \in I}\lambda_i = \sum_{j \in J}\lambda_j$, then the restricted partitions $\{\lambda_i\}_{i \in I}$ and $\{\lambda_j\}_{j \in J}$ are same.

For instance, $5 \ge 3 \ge 2 \ge 2$ does not have the property because $2+3=5$, but $5 \ge 5 \ge 3 \ge 3$ has the property.

Are there common names for these two properties?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ @SamHopkins: These two concepts are related two special cases of `modular' birational contractions of moduli space of stable pointed rational curves. The first one is related to toric case, and the second one is related to $S_n$-invariant case. This question is because of my ignorance on combinatorics - I would like to follow a common name in my paper, if there is any. $\endgroup$
    – Han-Bom Moon
    Aug 2, 2015 at 2:11
  • 1
    $\begingroup$ Sorry, I was confused by the use of "common". (I thought it meant "encompassing both of the properties" rather than "usual".) $\endgroup$
    – Sam Hopkins
    Aug 2, 2015 at 2:16
  • 2
    $\begingroup$ Well the first property is characterised by a forbidden induced subgraph: $\overline{P}_3$. I do not know any usual name for this property, and neither does graphclasses: graphclasses.org/classes/AUTO_2078.html $\endgroup$
    – Daniel Soltész
    Aug 2, 2015 at 2:34
  • 1
    $\begingroup$ The first property says that non-adjacency is a transitive relation (if we count each vertex as non-adjacent to itself). So if you need to invent a name, I'd suggest "co-transitive". $\endgroup$
    – Andreas Blass
    Aug 2, 2015 at 2:38
  • 5
    $\begingroup$ @AndreasBlass Thus the complement graph is the disjoint union of clicques, thus our graph is a complete multipartite graph. Well without specifying for what $k$ is it $k$-partite, so it is still kind of strange. $\endgroup$
    – Daniel Soltész
    Aug 2, 2015 at 2:46

2 Answers 2

Reset to default
9
$\begingroup$

This is only an answer to your first question.

The graphs with your property can be characterised by forbidding as induced subgraph $\overline{P}_3$. By Andreas Blass's comment, your property implies that the complement of the graph is a disjoint union of cliques. These graphs are called complete multipartite graphs.

Sometimes for this kind of question the site http://graphclasses.org/ can be useful.

Improve this answer
$\endgroup$
2
$\begingroup$

The second property is almost exactly the concept of "distinct subset sums", about which there are many beautiful unanswered questions. See, eg, http://www.openproblemgarden.org/op/sets_with_distinct_subset_sums The only difference between what you ask and the classical case is that you allow for repeated values.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.