co.combinatorics – Chromatic number of regular graphs using spectra

There exist inequalities relating the maximum and minimum eigenvalues of the adjacency matrix of a graph with its chromatic numbers, i.e. the Wilf’s and Hoffmann’s inequalities. But, for regular graphs, the upper bound by Wilf’s inequality is quite trivial, that is same as the greedy coloring bound.

Is there a better bound for the chromatic number of a regular graphs using the spectra of, say the adjacency or Laplacian matrices? Thanks beforehand.

co.combinatorics – Weight enumerator classifiers

Let $f(x,y)$ be a polynomial with integer coefficients. What conditions guarantee that this is the weight enumerator of a binary linear code of size $n$ and dimension $k$?

I’m almost certain that the answer to this question is unknown…so instead i’ll settle for anything that is conjectural.

There’s a list of necessary conditions:

  1. $f$ must be homogeneous of degree $n$ with non-negative coefficients.

  2. The $x^n$ coefficient has to be $1$ since the zero vector is the unique weight $0$ vector.

  3. The $y^n$ coefficient has to be $0$ or $1$ since the all $1$’s vector either belongs to the code or doesn’t.

  4. The sum of the coefficients has to be $2^k$ since every vector has a unique weight and so is counted exactly once by some coefficient.

  5. The MacWilliams transform ($g(x,y) = frac{1}{2^k}f(x+y,x-y)$) has to have all of the above properties but with coefficient sum $2^{n-k}$ since if $f$ corresponds to a code then $g$ would correspond to the dual code.

Are there any more necessary conditions missing?

co.combinatorics – On a generalization of the Borsak Ulam theorem / Tucker’s lemma for a map from simplex to it’s boundary

The Borsak Ulam theorem is equivalent to $S^{n-1}$ not being a retract of $B^n$.
How shall i prove the following stronger version:

There is no continuous map $f:Delta_n to partial Delta_n$ such that every face is mapped to itself.

In this case, Tucker’s lemma comes to mind, as it does say something similar.
Any thoughts?

co.combinatorics – How many squares can be formed by $n$ points in general position in the plane?

(This is much in the spirit (but different from) the questions from different posters: How many squares can be formed by using n points? and How many squares can be formed by using n points: revisited?)

Let $A$ be a set of $n$ points in the plane in general position. By general position we mean that no $3$ points are co-linear. What is the maximum number of squares that can be formed with vertices in $A$?

I note that there are trivial upper and lower bounds for this problem:

(Trivial Upper Bound) Given $n$ arbitrary points in the plane, noting that any two points determine at most $3$ squares it follows that there are at most $O(n^2)$ squares with vertices in $A$.

(Trivial Lower Bound) Place four points at the corner of a square, and repeat taking care to avoid all lines generated by pairs of points already placed in the plane until we’ve placed $n$ points. This clearly gives a lower bound of $Omega(n)$.

I can improve the implied constant in both the upper and lower bound by being a bit more clever. The problem, however, is to

Improve (asymptotically) on either the upper or lower bound just given.

co.combinatorics – Discrete Mathematics Logical Equivalence

Hello guys i need help in my quiz because we are now doing online class and i cant understand the lesson because there is no discussion. The teacher only gave us modules.

Use only the laws of logical equivalences to verify (b) and (c) in Problem 2 above. Show your detailed solutions legibly. Refer to example below.  

Example: Verifying (PΛQ) ↔ P ≡ P→Q using laws of logical equivalences:
  
Solution:  
(PΛQ) ↔ P                                 Left hand side of the equivalence 
((PΛQ)→P) Λ ((P→(PΛQ))                    Bi-implication in terms of implication
 ((PΛQ)’ V P) Λ (P’ V (PΛQ))              Implication in terms of ∨
((P’)V(Q’) V P) Λ ((P’VP) Λ (P’VQ))       DeMorgan’s law and  Distributive law 
((P’VP) V Q’) Λ ((P’VP) Λ (P’VQ))         Associative law 
(TVQ’) Λ (T Λ (P’VQ))                     Law of the excluded middle 
(TVQ’) Λ ((TΛP’) V (TΛQ))                 Distributive law 
T Λ (P’VQ)                                Law of the excluded middle and Identity laws
(TΛP’) V (TΛQ)                            Distributive law
P’ V Q                                    Identity laws 
P→Q                                       Implication in Terms of ∨ 
                                          Equivalent to the right-hand side. Thus, verified! 

Can someone explain how did it come to this? I need help understanding this example so i can answer the questions on my own. Really appreciate your help guys 😀

co.combinatorics – On the value of a skew Schur function at the identity

(Asked in MSE but got no response)

The generating function $frac{1}{(1-t)^N}=sum_k {N+k-1choose k}t^k=sum_k h_k(1)t^k$ and the Jacobi-Trudi formula $s_{lambda/mu}=det(h_{lambda_i-i-mu_j+j})$ tell me that the value of the skew Schur function at the identity is
$$ s_{lambda/mu}(1_N)=detleft({N+lambda_i-i-mu_j+j-1choose lambda_i-i-mu_j+j}right).qquad (1)$$

However, I was reading a paper by Chen and Stanley (A Formula for the Specialization of Skew Schur Functions) and they state that
$$s_{lambda/mu}(1,q,q^2,…)=frac{1}{prod_{uinlambda/mu}(N+c(u))_q}detleft(leftlbrack begin{matrix} N+lambda_i-i\lambda_i-i-mu_j+jend{matrix}rightrbrack_qright),qquad (2)$$
where $c(u)$ is the content of the box $u$ in the Young diagram of shape $lambda/mu$ and the $q$-quantities are $(x)_q=1-q^x$, $(a)_q!=(a)_q(a-1)_qcdots$ and $leftlbrack begin{matrix} a\bend{matrix}rightrbrack_q=frac{(a)_q!}{(b)_q!(a-b)_q!}.$

I am not an expert in this $q$-business, and I am confused by this equation. I have a few closely related questions.

  1. since the left hand side of (2) is a polynomial in $q$, it should have a limit when $qto 1$ and this should be the skew Schur at the identity. Is this correct? But what is the number of arguments?

  2. The determinant at the right hand side on (2) has a limit when $qto 1$, but the prefactor does not. How to take the limit $qto 1$ of this equation?

  3. How to obtain equation (1) from equation (2)?

co.combinatorics – How to solve this conditional recurrence relation?(two variable and conditions)

I am trying to solve the following recurrence relation

$4 leq n ;; ; ; ; ;$ and $; ; ; ; 2leq i leq lfloor{frac{n}{2}}rfloor$

$F(2i,n)=$
$begin{cases}
frac{1}{2(2i)-5}F(2i-2,2i-1),& text{if } n=2itext{, } igeq3\
frac{n}{2n-5}F(4,n-1)=frac{n!*3}{4!(2n-5)!!},& text{if } i=4 text{, } ngeq5\
frac{2i+n-4}{2n-5}F(2i,n-1)+frac{n-2i+1}{2n-5}F(2i-2,n-1),& text{otherwise}
end{cases}$

$F(4,4)=1$

I don’t know how to solve a conditional recurrence relation, and I didn’t find anything useful about it. any sugestion would be really helpful.

What I did up to now, as the first two conditions and also f(4,4) are initial and special case of the third condition, I only tried to solve the third one without any initial condition, I used generating function. But now I don’t know how to consider the other conditions and even whether the idea of solving the only third one alone was a good idea or not.

co.combinatorics – Binomial theorem for content polynomials of partitions

Let $lambda$ be a partition, represented by a usual Young diagram in which $1le ile ell(lambda)$ labels the rows and, for each $i$, $1le jle lambda_i$ labels the columns. For each box $square$ in the diagram, $c(square)=j-i$ is its content. The polynomial
$$ P_lambda(x)=prod_{squareinlambda}(x+c(square))=prod_{(i,j)inlambda}(x+j-i)$$
is the content polynomial.

I would like to know some family of coefficients $b^lambda_{munu}$, as a function of three partitions, such that
$$P_lambda(x+y)=sum_{mu,nusubset lambda}b^lambda_{munu}P_mu(x)P_nu(y).$$

(Notice that content polynomials are not linearly independent, so this equation alone is not enough to uniquely determine the coefficients. I ask for some family)

co.combinatorics – bijection mapping a transversal to a transversal

The following must certainly be a standard result, so what I’m looking for is a reference, or the ‘name’ of this theorem. I don’t have any combinatorics books at my fingertips, but I could see this being included therein.

If finite sets X and Y are each partitioned into n equal size subsets {X_i} and {Y_i} for i from 1 to n, and f:X->Y is a bijection, there exists x_i in X_i and y_i in Y_i, for i from 1 to n, such that f(x_i)=y_i.

I was able to come up with an argument for this myself without too much difficulty, but I’d rather not include a proof of a (very likely) well known result.
Thanks.

co.combinatorics – Combinatorial optimization on sum of distances in one dimension

We are given an increasing sequence $S_n$ of $n$ distinct real numbers $x_1, x_2, ldots, x_n$, with $x_1=0$ and $x_n=1$. We define the complementary distance $D(p,q):=1-d(p,q)$, where $d(p,q):=|x_q-x_p|$. Finally, we define the following functions of a threshold value $tauin(0,1)$:

$$R(tau):=left(sum_{substack{1le i<j<kle n: \ x_i<x_j<tau<x_k}}
D(j,i)right)+
left(sum_{substack{1le i<j<kle n: \ x_i<tau<x_j<x_k}}
D(k,j)right)~,
$$

and

$$M(tau):=sum_{substack{1le i<j<kle n: \ x_i<tau<x_k}}
max{D(j,i),D(k,j)}~.
$$


Question: What is (a sufficiently tight lower bound for) the minimum value for the ratio $rho^*:=frac{Rleft(tauright)}{Mleft(tauright)}$ over all possible value of $tauin(0,1)$ and all sequences $S_n$ for all $n$? Do we have $rho^*getfrac23$?

(Can we use random sampling techniques to solve this problem?)



Note: The difference between this problem and the one described in Combinatorial optimization problem on the sums of differences of real numbers is only the final question.