6
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $\alpha \leq |V|* \frac{-\lambda}{d-\lambda}$, where $\lambda$ is the smallest eigenvalue of the ...
5
Adding to the allure of this deadly siren song is the fact that there are constructions of this sort for the Moore graph of degree $3$ (the Petersen Graph with 10 vertices and independence number $4$) and the Moore Graph of degree $7$ ( the Hoffman-Singleton graph with $50$ points and independence number $15$.) The only other possible degrees are $2$ (a ...
4
The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube $\{0,1\}^n$ except the origin $(0,0,\dots,0)$, ...
3
The answer is no. This is equivalent to stating that for any linear hypergraph $H=(\kappa,E)$ with $\kappa$ infinite (note that for $\kappa$ finite, $G=I(H)$ would be finite), we have $\chi(I(H))\leq\kappa$. This follows immediately once we show $|V(I(H))|=|E|\leq\kappa$.
For $\alpha<\kappa$ let $E_\alpha=\{e\in E:\alpha\in e\}$. If we remove $\alpha$ ...
1
Let $G=K_\omega$ be a clique on infinitely many vertices and $H$ a disjoint union of $K_n$ for each $n\in\omega$. I claim $\text{Flt}(G,H)$ has no minimal elements.
Let $f:V(G)\to V(H)$ be arbitrary. Take some vertices $v,w\in V(G)$ with $f(v)\in K_n$ and $f(w)\in K_m$ with $n\neq m$. Consider a map $g:V(H)\to V(H)$ which does the following: if $k\neq n,m$ ...
1
Consider the graph $G$ with vertices $ \left\{ (x,A) |x ∈\mathbb{N} \right\} \cup \left\{ (x,B) |x ∈\mathbb{N} \right\} \cup \left\{ (x,y) |x ∈\mathbb{N}, y ∈\mathbb{N},y \leq x \right\}$ with two vertices $(w,x)$ and $(y,z)$ connected iff $w=y$ or both $x$ and $z$ are letters.
For each $n\geq 2$, one can decide whether to remove the edge $(n,n-1)$ or not;...
Only top voted, non community-wiki answers of a minimum length are eligible
