A note on short cycles in a hypercube (Q2509296): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2063369760 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1605.06572 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Ramsey-type result for the hypercube / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4830805 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cycles of even length in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subgraphs of a hypercube containing no small even cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hexagon-free subgraphs of hypercubes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Arithmetic Progressions of Cycle Lengths in Graphs / rank | |||
Normal rank |
Latest revision as of 21:54, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on short cycles in a hypercube |
scientific article |
Statements
A note on short cycles in a hypercube (English)
0 references
19 October 2006
0 references
The graph \(Q_n\) (called hypercube of dimension \(n\)) is defined as follows: The set of vertices of \(Q_n\) consists of subsets of \(\{1,\dots,n\}\), and the set of edges \(E(Q_n)\) corresponds to pairs of sets with symmetric difference of size \(1\). Let \(f(n,C_l)\) be the largest number of edges in a subgraph of \(Q_n\) with no cycle of length \(l\). It is known for example that \(f(n,C_4)\leq 0.623\cdot | E(Q_n)| \). The authors provide a general upper bound for \(f(n,C_l)\) when \(l=4k+2\) as well as a coloring of \(E(Q_n)\) by four colors containing no induced monochromatic \(C_{10}\).
0 references
Ramsey property
0 references