All
All

What are you looking for?

All
Projects
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Kneser ranks of random graphs and minimum difference representations

Result description

Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v mapsto A_v$ to the vertices $vin V$ such that $A_u$ and $A_v$ are disjoint if and only if $uvin E$. The smallest such $k$ is called the {em Kneser rank} of $G$ and denoted by $fKn(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0< p< 1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$ such that with high probability [ c_1 n/(log n)< fKn(G) < c_2 n/(log n). ] We apply this to other graph representations defined by Boros, Gurvich and Meshulam. A {em $k$-min-difference representation} of a graph $G$ is an assignment of a set $A_i$ to each vertex $iin V(G)$ such that $ ijin E(G) ,, Leftrightarrow , , min {|A_isetminus A_j|,|A_jsetminus A_i| }geq k. $ The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{min}(G)geq k$. We prove that there are constants $c''_1, c''_2>0$ such that $c''_1 n/(log n)< f_{min}(G) < c''_2n/(log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.

Keywords

intersection graphsclique coversKneser graphsrandom graphs

Alternative languages

  • Result language

    angličtina

  • Original language name

    Kneser ranks of random graphs and minimum difference representations

  • Original language description

    Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there is an assignment of (distinct) $k$-sets $v mapsto A_v$ to the vertices $vin V$ such that $A_u$ and $A_v$ are disjoint if and only if $uvin E$. The smallest such $k$ is called the {em Kneser rank} of $G$ and denoted by $fKn(G)$. As an application of a result of Frieze and Reed concerning the clique cover number of random graphs we show that for constant $0< p< 1$ there exist constants $c_i=c_i(p)>0$, $i=1,2$ such that with high probability [ c_1 n/(log n)< fKn(G) < c_2 n/(log n). ] We apply this to other graph representations defined by Boros, Gurvich and Meshulam. A {em $k$-min-difference representation} of a graph $G$ is an assignment of a set $A_i$ to each vertex $iin V(G)$ such that $ ijin E(G) ,, Leftrightarrow , , min {|A_isetminus A_j|,|A_jsetminus A_i| }geq k. $ The smallest $k$ such that there exists a $k$-min-difference representation of $G$ is denoted by $f_{min}(G)$. Balogh and Prince proved in 2009 that for every $k$ there is a graph $G$ with $f_{min}(G)geq k$. We prove that there are constants $c''_1, c''_2>0$ such that $c''_1 n/(log n)< f_{min}(G) < c''_2n/(log n)$ holds for almost all bipartite graphs $G$ on $n+n$ vertices.

  • Czech name

  • Czech description

Classification

  • Type

    JSC - Article in a specialist periodical, which is included in the SCOPUS database

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

Others

  • Publication year

    2017

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Name of the periodical

    Electronic Notes in Discrete Mathematics

  • ISSN

    1571-0653

  • e-ISSN

  • Volume of the periodical

    61

  • Issue of the periodical within the volume

    August

  • Country of publishing house

    NL - THE KINGDOM OF THE NETHERLANDS

  • Number of pages

    5

  • Pages from-to

    499-503

  • UT code for WoS article

  • EID of the result in the Scopus database

    2-s2.0-85026787337

Basic information

Result type

JSC - Article in a specialist periodical, which is included in the SCOPUS database

JSC

OECD FORD

Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Year of implementation

2017