All Questions
Tagged with algebraic-combinatorics discrete-mathematics
13
questions
1
vote
1
answer
144
views
No minors isomorphic to $U_{0,1}$ and $U_{1,2}.$
I am trying to find all the matroids having no minors isomorphic to $U_{0,1}$ and $U_{1,2}.$
I know that the matroid $U_{0,n}$ is a matroid of rank zero with n edges and so it is just a vertex with n ...
- 95
0
votes
1
answer
95
views
Determining all self-dual uniform matroids.
I want to determine all self-dual uniform matroids; I know that the dual of a uniform matroid $U_{r,n}$ is $U_{n - r,n}$ by Example $2.1.4$ in James Oxley, second edition, "Matroid Theory". ...
- 3,139
0
votes
1
answer
52
views
The relation between contraction and deletion in a matroid.
Here is the relation I have seen a lot in the books, but I am not sure why it is always true:
If $T \subseteq E(M)$ then $$M \setminus T = (M^* / T)^* \quad\quad (*)$$
I know that contraction is ...
- 3,139
0
votes
1
answer
108
views
The relation between the closure and the contraction of a matroid M.
Here is the relation I am trying to justify:
$cl_{ M/T}(X) = cl_M(X \cup T) - T$ for all $X \subseteq E - T.$
Why this relation true?
Any proof will be greatly appreciated!
**Here are all what I know ...
- 3,139
5
votes
1
answer
91
views
Are there interesting combinatorial proofs which use more sophisticated grouping than sign-reversing involutions?
There are many combinatorial proofs which establish interesting identities by designing suitable "sign-reversing involutions" on a set of relevant signed objects.
For example, Benjamin and ...
- 729
9
votes
1
answer
542
views
Let $B\subset A = \{1,2,3,...,99,100\}$ and $|B|= 48$. Prove that exist $x,y\in B$, $x\ne y$ such that $11\mid x+y$.
Let $B\subset A = \{1,2,3,...,99,100\}$ and $|B|= 48$.
Prove that exist $x,y\in B$, $x\ne y$ such that $11\mid x+y$.
Proof: Let $P_0:= \{11,22,...,99\}$ and for $i=
1,2,...49$ and $11\nmid i$ make ...
- 90.7k
0
votes
1
answer
1k
views
Computing a rook polynomial
I have this $3\times 3$ square above, where the $5$ white squares form a board $B$,
and I am trying to calculating the rook polynomial of $B$, using the following formula :
the answer is given as $...
- 327
22
votes
3
answers
735
views
A conference uses $4$ main languages. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.
A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.
Source: ...
- 90.7k
3
votes
1
answer
184
views
To show two formal power series equal
I am wondering whether the following two formal power series are equal:
$A(x)=\Pi_{k=1}^{\infty}\frac{1}{1-x^{2k-1}}$, $B(x)=\Pi_{k=1}^{\infty}(1+x^k)$.
- 454
0
votes
1
answer
275
views
Calculating the Most Reduced Sets in a Set of Sets
I'm having trouble solving this problem efficiently:
Let's say we have the following sets
{1, 2, 3}
{1, 2}
{2, 3}
{1}
We want to eliminate those sets which are ...
- 103
1
vote
1
answer
767
views
Proof that Paley Graphs are strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$
A Paley graph is strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$. I need to prove that, and obtain the parameters too. Proving it is regular valency $\frac{p-1}{2}$ is ...
- 421
2
votes
0
answers
64
views
Orbital dimension of the action of $S_n$ on 2-subsets
I have a question on a proof in a paper on the orbital dimension of a permutation group.
Let $G \le S^\Omega$ be a permutation group. A base for $G$ is a subset $\Sigma \subseteq \Omega$ for which ...
- 4,095
4
votes
1
answer
8k
views
Use of rook polynomials
Use rook polynomials to count the number of permutations of $(1,2,3,4)$ in which $1$ is not in the second position, $2$ is not in the fourth position, and $3$ is not in the first or fourth position. ...
- 61