# Tagged Questions

190 views

### A method of making a graph bipartite

If we take a graph $G$, and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite? ...
35 views

### Sperner family intersection with chains.

Consider a maximal sperner family $F$ of subsets of $X = \{ 1,2,3 \ldots n \}$. I need to prove that this family intersects with each chain of subsets exactly once. Each chain is defined as : ...
34 views

### K- Regular families. Proof of existence.

A family F of subsets is regular if every point lies in a constant number r of the elements of F. Theorem : Let $b,k,n,r$ be positive integer satisfying $bk = nr, k<n, b\leq$ $n\choose{k}$. Then ...
39 views

### Proof of De Bruijn-Erdos theorem

I am reading Cameron's Combinatorics and came across following part of the proof of De Bruijn-Erdos theorem which I am unable to follow. $F$ is the family of set such that any two sets in $F$ ...
174 views

97 views

### Number of edges in graphs having two disjoint cycles of equal length

The question is motivated by this and this two problems. The first problem states that if $G$ is a graph with $n$ vertices and at least $2n-2$ edges then $G$ must contain two distinct cycles of the ...
187 views

### Pigeonhole Principle to Prove a Hamiltonian Graph

I am trying to figure out if a graph can be assumed Hamiltonian or not, or if it's indeterminable with minimal information: A graph has 17 vertices and 129 edges. ...
31 views

### Covering the square with “crosses”.

The problem concerns covering the unit square with translates of a specific figure, which I will refer to as a "cross", using as few translates as possible. The difficulty seems to result from the ...
40 views

### Maximum independent sets of balanced bipartite graph

Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$. Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are ...
28 views

### Threshold function of the property Sperner set

Someone can to help me in the following problem about the threshold function of the property Sperner set? I don't know where to start. Let $\mathcal{F} \subseteq \mathcal{P}([n])$ be a random ...
119 views

### Linear algebra and combinatorics. For a family with even size sets and even intersections prove that $|F| \le 2^{n/2}$

Let $F \subset P(n)$ be a family such that for all i and j $|f_i \cap f_j|$ and $|f_i|$ are even Prove that $|F| \le 2^{n/2}$ Now I think we go by contradiction and say if $|F| \ge 2^{n/2}+1$ ...
41 views

### Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
37 views

### What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.

Motivated by: Tiling an orthogonal polygon with squares, How to prove that the minimum square partition of a 3X2 rectangle has 3 squares, Minimum square partitions for 4x3 and 5x4 rectangles, What is ...
177 views

### Minimum square partitions for 4x3 and 5x4 rectangles

Motivation: Tiling an orthogonal polygon with squares Followup question: What is the first $w$ such that a rectangle, $R_{w\times w−1}$ is minimally-square-partitioned by less than $w$ squares.. Yes, ...
59 views

### Minimum boolean lattice containing all poset of fixed size

I need help with the following: What is the minimum $n$ such that the boolean lattice $2^{[n]}$ contains all posets of size $m$? I noticed that it should contain a chain of length $m$, and the ...
139 views

### LYM Inequality question

Suppose that $F ⊂ P(n)$ is a set system containing no chain with $k + 1$ sets. Prove that $\sum\limits_{r=1}^n \frac{|F_{r}|}{n \choose r} ≤ k$, where $F_{i} = F \cap [n]^{(i)}$ for each i. ...
83 views

### Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$

I'm stuck on this combinatorics question: Let $k \le \frac{n}{2}$, and suppose that $F$ is an antichain in $P(n)$ such that every $A \in F$ has $|A| \le k$. Prove that $|F| \le \binom{n}{k}$. I've ...
39 views

### Balanced independent sets & independent domination number

Let $G=(V,E)$ be a bipartite graph, with partition $V=A \cup B$. Recall that an independent set $I$ of $G$ is a set of vertices sharing no edges. The independent domination number $i(G)$ is deﬁned ...
130 views

### Number of combinations such that each pair of combinations has at most x elements in common?

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I ...
575 views

### How many non-isomorphic ways a convex polygon with $n + 2$ sides can be cut into triangles?

From Wikipedia: The Catalan number $C_n$ is the number of different ways a convex polygon with $n + 2$ sides can be cut into triangles by connecting vertices with straight lines (a form of Polygon ...
58 views

### Has this variation of blocking set been studied before?

Given a collection of sets $F$, a set which intersects all sets in the $F$ in at least one element is called a blocking set (or hitting set). The blocking number $τ(F)$ of a family $F$ is the minimum ...
48 views

### An extremal combinatorial problem over Finite rings

Let $q$ be an odd number and $g_i = (g_{i1} g_{i2} \dots g_{ir}) \in \Bbb Z_q^r$ a list of vectors with $i\in\{1,\ldots,L\}$. Let each $g_i$ have $0 < k < r$ zero entries. What is the maximum ...
136 views

### Show there’s at most $n\choose \left \lfloor\frac{n}{2} \right\rfloor$ subsets $A\subset[n]$ such that $\displaystyle\sum\limits_{i\in{A}} a_i=\alpha$

Let $a_1, a_2, a_3, ... , a_n$ and $\alpha$ be n+1 non-zero real numbers. Prove that there are at most $n\choose \left\lfloor\frac{n}{2}\right\rfloor$ subsets $A\subset[n]$ such that ...
863 views

### Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

The question is in the title. I can see why the bound is sharp (for example, a lot of triangles sharing one common vertex if n is odd, or the same but with one spare edge hanging out if n is even). ...
56 views

68 views

### Question in discrete mathematics *

I have question. Can anyone able to explain to me this problem why if we have 5x the generating function $1+x^5+x^{10}+x^{15} + \ldots$ we have 5 is just constant and multiply with $x$ I know that $x$ ...
76 views

### question in discrete mathematics

I have questions. Can anyone help me to get the idea or figure out this problem. Find a recurrence relation. If an denote the number of words from the alphabet W={A,B,C} of length n with no two ...
151 views

### No induced ordered graph yields large clique/stable set in ordered graph

Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not ...
301 views

### Ramsey-type result for tournaments

I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help. Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let ...
85 views

### Points at Integer Distances in 3-space

With the restriction no three points in a line, no four points on a circle, there is a 7 point configuration of points on the plane such that all pairs of points are at integer distances. [1] For ...