Independence numbers of Johnson-type graphs

DOI10.1007/S00574-023-00350-YzbMATH Open1518.05186arXiv1907.06752OpenAlexW2961195811MaRDI QIDQ6115445FDOQ6115445

Authors: Danila Cherkashin, Sergei Kiselev 

Publication date: 12 July 2023

Published in: Bulletin of the Brazilian Mathematical Society. New Series (Search for Journal in Brave)

Abstract: We consider a family of distance graphs in $mathbb{R}^n$ and find its independent numbers in some cases. Define graph $J_{pm}(n,k,t)$ in the following way: the vertex set consists of all vectors from ${-1,0,1}^n$ with $k$ nonzero coordinates; edges connect the pairs of vertices with scalar product $t$. We find the independence number of $J_{pm}(n,k,t)$ for $n>n_0(k,t)$ in the cases $t=0$ and $t=-1$; these cases for $k=3$ are solved completely. Also the independence number is found for negative odd $t$ and $n>n_0(k,t)$.

Full work available at URL: https://arxiv.org/abs/1907.06752

Recommendations

• Independence numbers and chromatic numbers of some distance graphs
• Distance independence in graphs
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• Independence numbers of random subgraphs of a distance graph
• Independence numbers of random subgraphs of distance graphs

zbMATH Keywords

independence numberdistance graphsintersecting familiesErdös-Ko-Rado theorem

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On a packing and covering problem
• Forbidding just one intersection
• Intersection theorems with geometric consequences
• On the ratio of optimal integral and fractional covers
• Borsuk's problem and the chromatic numbers of some metric spaces
• Coloring some finite sets in \(\mathbb R^n\)
• A counterexample to Borsuk’s conjecture
• Title not available (Why is that?)
• On the chromatic number of a space
• The realization of distances within sets in Euclidean space
• The complete intersection theorem for systems of finite sets
• Kneser's conjecture, chromatic number, and homotopy
• A fast algorithm for the maximum clique problem
• More-than-nearly-perfect packings and partial designs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Covers in uniform intersecting families and a counterexample to a conjecture of Lovász
• On a combinatorial conjecture of Erdös
• An upper bound for the size of a \(k\)-uniform intersecting family with covering number \(k\)
• On hypergraph cliques with chromatic number 3
• On the difference between asymptotically good packings and coverings
• Uniform eventown problems
• A stability result for families with fixed diameter
• Title not available (Why is that?)
• Chromatic numbers of Kneser-type graphs
• Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
• Correction to the article: ``Intersection theorems for \((0,\pm1)\)-vectors and \(s\)-cross-intersecting families
• Families of vectors without antipodal pairs
• Title not available (Why is that?)
• Un problème de partition de l'ensemble des parties à trois éléments d'un ensemble fini
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹

This page was built for publication: Independence numbers of Johnson-type graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115445)