Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.01459 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915368846491648 |
|---|---|
| author | Chen, Yijia Flum, Jörg Liu, Mingjun |
| author_facet | Chen, Yijia Flum, Jörg Liu, Mingjun |
| contents | The CFI-graphs, named after Cai, Fürer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are colored graphs, and the coloring plays a role in many of their applications. As usual, it is not hard to remove the coloring by some extra graph gadgets, but at the cost of blowing up the size of the graphs and changing some parameters of them as well. This might lead to suboptimal combinatorial bounds important to their applications. Since then for some uncolored variants of the CFI-graphs it has been shown that they serve the same purposes. We show that this already applies to the graphs obtained from the original CFI-graphs by forgetting the colors. Moreover, we will see that there is a first-order formula $φ(x,y)$ expressing in almost all uncolored CFI-graphs that $x$ and $y$ have the same color in the corresponding colored graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01459 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Some remarks on the uncolored versions of the original CFI-graphs Chen, Yijia Flum, Jörg Liu, Mingjun Discrete Mathematics Logic in Computer Science Combinatorics The CFI-graphs, named after Cai, Fürer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are colored graphs, and the coloring plays a role in many of their applications. As usual, it is not hard to remove the coloring by some extra graph gadgets, but at the cost of blowing up the size of the graphs and changing some parameters of them as well. This might lead to suboptimal combinatorial bounds important to their applications. Since then for some uncolored variants of the CFI-graphs it has been shown that they serve the same purposes. We show that this already applies to the graphs obtained from the original CFI-graphs by forgetting the colors. Moreover, we will see that there is a first-order formula $φ(x,y)$ expressing in almost all uncolored CFI-graphs that $x$ and $y$ have the same color in the corresponding colored graphs. |
| title | Some remarks on the uncolored versions of the original CFI-graphs |
| topic | Discrete Mathematics Logic in Computer Science Combinatorics |
| url | https://arxiv.org/abs/2507.01459 |