text:
Many-body delocalization dynamics in long Aubry-André quasiperiodic chains

Submission summary

 As Contributors: Elmer Doggen Arxiv Link: https://arxiv.org/abs/1901.06971v1 Date submitted: 2019-01-23 Submitted by: Doggen, Elmer Submitted to: SciPost Physics Domain(s): Theor. & Comp. Subject area: Condensed Matter Physics - Theory

Abstract

We theoretically study quench dynamics in an interacting one-dimensional spin chain with a quasi-periodic on-site field, also known as the interacting Aubry-Andr\'e model of many-body localization. Using the time-dependent variational principle we assess the late-time behaviour for chains up to $L = 50$. The choice of periodicity of the quasi-periodic potential influences the dynamics, which is explained in terms of properties of the non-interacting problem. Furthermore, the decay of antiferromagnetic order is faster than a power law, and finite-size effects on the value of the critical disorder are weaker than in the purely random case.

Current status:
Editor-in-charge assigned

Submission & Refereeing History

Submission 1901.06971v1 on 23 January 2019

Reports on this Submission

Show/hide Reports view

Strengths

1- Application of TDVP to the quasiperiodic (QP) interacting system

Weaknesses

1- Proper convergence of the method with time-step and bond-dimension is not established
2- Conclusion about the drift of the dynamical exponent is drawn from a regime were the data doesn't appear to be converged
3- The study doesn't bring much new information compared to literature.
4- Poor presentation, which doesn't allow to read the results conveniently

Report

The authors numerically study the dynamics in a quasiperiodic (QP) interacting spin chain, which shows a MBL like transition as a function of the strength of the QP potential.

In their introduction the authors claim:

"The aim of the present work is to investigate the differences between purely random
and quasi-periodic disorder at system sizes inaccessible to exact diagonalization, using the
newly developed numerical technique of the time-dependent variational principle as applied
to matrix product states"

This statement is however misleading, since dynamics in QP interacting systems was studied using MPS based method in both [37] (L=100-200) and 10.1073/pnas.1800589115, for systems of up to 800 sites (cf, to L=50 that the authors use in this work). In fact one of the accents of 10.1073/pnas.1800589115 is on finite-size effects and comparison to the disordered case.

However, my main concern is not even with the originality of the work, but with the validity of its results. The authors use a very low bond dimension (xi<64, compared to xi=1000-2000, many time used in TEBD), and their method (1-site TDVP) doesn't allow them to estimate the discarded weight. Moreover, the comparison between the two shown bond-dimensions are done on a logarithmic scale and for different "disorder" realizations, which doesn't allow to estimate the time until which the results are reliable.

From Fig 1 it is obvious that this time is not longer than t~100 (which is also probably a conservative estimate). This can also seen from the comparison to TEBD, which the authors provide in their reply. Although the graph is also on a log-log scale, for W=4, the divergence with TEBD occurs already at t<100, where TEBD results appear to converge, as far as one ca n judge from this plot. While one can see that TEBD saturates the bond dimension 256 already at times t=20, the actually meaningful information is the accumulated discarded weight, which the authors don't provide.

As on can see from Fig 3 for t<100 and W=4, the drift in the dynamical exponent, which is one of the main results of the work is not significant, and in any case probably lies within the error bars (which are not shown for some reason). For W>5 the oscillations in the exponent do not allow to extract a coherent message, though the convergence issues I raised above, are presumably better there.

Another issue, which is not discussed in the paper is the convergence with respect to the time-step. Following a request by the first referee the authors do specify the time-step dt=0.1, in their reply, but don't provide any evidence that this time-step is sufficient to go to t=300 and W=8 for example.

In view of the above I agree with the report of the first referee that the conclusions of this work are most probably based on not converged data, and are therefore doubtful. I therefore do not think that the paper stands by the standards of SciPost.

Requested changes

See report

• validity: low
• significance: low
• originality: low
• clarity: high
• formatting: reasonable
• grammar: excellent

Strengths

1. Application of time-dependent variational technique with matrix product states to the problem of MBL with quasi-periodic disorder
2. Introducing distribution of spin densities as a possible experimental observable.

Weaknesses

1. Results seem not to be converged - that makes the claims of faster than power-law decay of imbalance doubtful.
2. The effect found and discussed, the dependence of the system behavior on periodicity of quasi-periodic potential is not new.

Report

The manuscript addresses many-body localization (MBL) in quasi-periodic on-site disorder in isotropic Heisenberg chain model - a paradigmatic model used for MBL studies. While the manuscript lists some of earlier works on this very topic [20,23,26] it misses, however, at least one early study PRB 87, 134202 (2013). Those earlier studies used typically exact diagonalization combined with the finite size scaling to estimate the transition to MBL. The present work considers experimentally accessible observables such as imbalance and distribution of spin densities whose time dynamics is evaluated using time-dependent variational principle with matrix product states. The authors report as their main finding (abstract and conclusion) the strong dependence of the system properties on the periodicity of the quasi-periodic potential which they trace to properties of the non-interacting problem. They stress that the decay of the anti-ferromagnetic order is faster than a power law (I believe on the delocalized side of the MBL transition).

The field of MBL is quite well established by now so making a significant contribution in the field is not as straightforward as say 5 years ago. In my opinion the work presented while providing some incremental value to the field, certainly does not meet the Scipost Physics criterion: "Articles provide in-depth, detailed reports of groundbreaking research within one or more subject areas."

The main claim, a strong dependence of the system dynamics on the periodicity of the quasi-periodic potential is a bit trivial and not new. It is explained more than 10 years ago in detail in V. Guearrera et al. New. J. Phys. 9, 107 (2007). In fact the on-site energy difference distribution (plotted in Fig.2 right panel of the manuscript) may be easily found analytically as proportional to $1/\sqrt{1-x^2}$ distribution with the amplitude of the effective disorder $W\sin(\pi\Phi)$ as it follows from that paper. Similar strong dependence on the quasi-periodicity was found in an interaction free problem by Major et al. Phys. Rev. A 98 053633 (2018).

While the application of the variational principle MPS approach to time dynamics seems to be an original contribution, this has been already reported in [22] for a purely random case. So one can hardly give credit for that. Especially, as time dependent dynamics using MPS (with e.g. TEBD) for MBL has been studied in a routine way, see [8], also
J. H. Bardarson, F. Pollmann, and J. E. Moore, Phys. Rev. Lett. 109, 017202 (2012)
P. Sierant, D. Delande, and J. Zakrzewski,Phys. Rev. A 95, 021601(R) (2017)
for different implementations.

The variational approach might have some advantage for long times due to the inherent energy conservation, the problem deserves a separate careful study in the MBL regime and close to it - comparisons as those in 1901.05824 do not suggest a clear advantage of the variational approach.

There is a strong believe that the system studied shows the mobility edge - the transition to MBL depends on energy (see Luitz et al Phys. Rev. B 91, 081103 (2015)). The present study considers a single initial anti-ferromagnetic state whose energy depends strongly on the disorder realization. This may affect the value of the critical disorder obtained. The question of the mobility edge is entirely ignored in the manuscript.

Apart from these general remarks I believe that the authors should (in some future submission) consider the following remarks
1. Results for $\chi=32$ and $\chi=64$ seem unconverged (Fig. 1a and Fig.1b). Why not show convergent results for sufficiently large $\chi$?
2. The present Fig.1 is unreadable - it requires huge enlarging to distinguish different curves.
3. Let me mention that standard TEBD results with $\chi=250$ do not agree with those reported in Fig.1.
4. Why the authors do not provide information that would allow a reader to reproduce their results? What was the time step in time-dependent integration? What was the accuracy criterion (none - just $\chi$ was defined is one of the options)?
5. The faster than power-law decay of the imbalance on the delocalized side, the main conclusion of the manuscript, is deduced from not converged results.
6. The claim for the critical disorder to be $W_c=5$ is a rough estimate only. The text suggest error bar of the order of 0.5. Can the authors do better with the converged results?
7. Authors claim a weak dependence on the system size for quasi-periodic potential in the introduction but they do not substantiate this claim further - showing just a single curve for $L=16$. How $W_c$ depends on the system size?

Requested changes

see above

• validity: low
• significance: low
• originality: ok
• clarity: ok
• formatting: good
• grammar: perfect

Author Elmer Doggen on 2019-03-07 (in reply to Report 1 on 2019-02-15)
Category:

Following a possibility provided by SciPost, we provide a preliminary response to the Referee's comments (Report 1). We will finalize the response and resubmit the paper, once the Editor-in-Charge invites us to do so upon the end of the refereeing round.

We thank the Referee for a detailed report. The referee's comments motivated us to improve the rigour of our results with some additional numerical computations, which will be added to a future submission. In addition, we will improve the presentation of our work and the clarity of our plots, as well as providing more details about our numerical method and the benefits thereof compared to older methods like time-evolving block decimation (TEBD). On the other hand, we disagree with the referee's assessment of our work as having low significance and validity. We address all critical remarks of the referee below.

REFEREE:
"The manuscript addresses many-body localization (MBL) in quasi-periodic on-site disorder in isotropic Heisenberg chain model - a paradigmatic model used for MBL studies. While the manuscript lists some of earlier works on this very topic [20,23,26] it misses, however, at least one early study PRB 87, 134202 (2013)."

We thank the referee for pointing out this reference that is indeed relevant - a future submission will include a citation.

REFEREE:
"Those earlier studies used typically exact diagonalization combined with the finite size scaling to estimate the transition to MBL. The present work considers experimentally accessible observables such as imbalance and distribution of spin densities whose time dynamics is evaluated using time-dependent variational principle with matrix product states. The authors report as their main finding (abstract and conclusion) the strong dependence of the system properties on the periodicity of the quasi-periodic potential which they trace to properties of the non-interacting problem. They stress that the decay of the anti-ferromagnetic order is faster than a power law (I believe on the delocalized side of the MBL transition)."

There are in fact three main conclusions that are listed clearly in the summary and are mentioned also in the abstract: the dependence of the MBL transition on $\Phi$, the faster-than-power law decay on the delocalized side and the relatively weak dependence of the transition on system size. We will improve the wording in the abstract to make this clearer.

REFEREE:
"The field of MBL is quite well established by now so making a significant contribution in the field is not as straightforward as say 5 years ago. In my opinion the work presented while providing some incremental value to the field, certainly does not meet the Scipost Physics criterion: "Articles provide in-depth, detailed reports of groundbreaking research within one or more subject areas." "

We disagree with this assessment. In our view our study provides an important addition to the existing literature by studying larger systems up to late times, which is of obvious relevance to current experiments. The differences between the MBL transition in quasiperiodic and purely random systems is currently under active discussion and our work provides much needed numerical analysis to help settle this debate.

REFEREE:
"The main claim, a strong dependence of the system dynamics on the periodicity of the quasi-periodic potential is a bit trivial and not new. It is explained more than 10 years ago in detail in V. Guearrera et al. New. J. Phys. 9, 107 (2007). In fact the on-site energy difference distribution (plotted in Fig.2 right panel of the manuscript) may be easily found analytically as proportional to $1/\sqrt{1−x^2}$ distribution with the amplitude of the effective disorder $W\sin(\pi \Phi)$ as it follows from that paper. Similar strong dependence on the quasi-periodicity was found in an interaction free problem by Major et al. Phys. Rev. A 98 053633 (2018). "

We thank the referee for pointing out the important reference New. J. Phys. 9, 107 (2007), of which we were not aware. The effective disorder mentioned in that work matches with our Fig. 2b after correcting with an additional factor of 2 due to their potential using a squared sine. Our "main claim" is not about the single-particle problem; indeed, that the periodicity strongly affects dynamics was pointed out, as mentioned in our manuscript, also in Ref. [36], Phys. Rev. A 80, 021603 (2009) for the extended AA model. Rather, one of the key results is that this single-particle feature carries over to the many-problem directly and leads to an apparent dependence of the critical disorder on the periodicity $\Phi$ - a non-trivial and to our knowledge new result contrary to the non-interacting case where the critical disorder is always $W = 2$ (in our units) for almost any irrational $\Phi$. That there are still interesting results from recent publications such as in [Phys. Rev. A 98 053633] even for the non-interacting problem underscores that there is still much to learn in the interacting problem.

REFEREE:
"While the application of the variational principle MPS approach to time dynamics seems to be an original contribution, this has been already reported in [22] for a purely random case. So one can hardly give credit for that. "

In Ref. [22] we demonstrated that our method works well for the MBL problem with purely random disorder, allowing to reliably study large systems and long times on the ergodic side of the transition. Hence, it is natural and important to use it also for the quasi-periodic case and compare the results.

REFEREE:
"Especially, as time dependent dynamics using MPS (with e.g. TEBD) for MBL has been studied in a routine way, see [8], also
J. H. Bardarson, F. Pollmann, and J. E. Moore, Phys. Rev. Lett. 109, 017202 (2012)
P. Sierant, D. Delande, and J. Zakrzewski,Phys. Rev. A 95, 021601(R) (2017)
for different implementations.

The variational approach might have some advantage for long times due to the inherent energy conservation, the problem deserves a separate careful study in the MBL regime and close to it - comparisons as those in 1901.05824 do not suggest a clear advantage of the variational approach."

We thank the referee for pointing out these references, which will be cited appropriately. Our method provides considerable advantages over TEBD specifically for the MBL problem (see also our response to point 3 below). Indeed, the main advantage of the method is the inherent energy conservation, as opposed to the non-conservation of energy in e.g. TEBD. As a side note, in the language of 1901.05824 we use a 1TDVP algorithm, not a 2TDVP algorithm. The latter does not conserve energy for otherwise energy-conserving Hamiltonian dynamics due to the truncation step induced by the two-site approach.

REFEREE:
"There is a strong believe that the system studied shows the mobility edge - the transition to MBL depends on energy (see Luitz et al Phys. Rev. B 91, 081103 (2015)). The present study considers a single initial anti-ferromagnetic state whose energy depends strongly on the disorder realization. This may affect the value of the critical disorder obtained. The question of the mobility edge is entirely ignored in the manuscript."

A dependence of the critical disorder on energy in this system is indeed interesting, but we do not expect the essential properties of the MBL transition to depend on energy (as long as we are not too close to the ground state). A large majority of studies of MBL only target the middle of the spectrum and likewise ignore the question of a mobility edge. We thus leave the investigation of the energy-dependence of the critical point and verification of the universal character of the transition to future work.

REFEREE:
"Apart from these general remarks I believe that the authors should (in some future submission) consider the following remarks
1. Results for $\chi=32$ and $\chi=64$ seem unconverged (Fig. 1a and Fig.1b). Why not show convergent results for sufficiently large $\chi$?"

We might have shown only $\chi = 64$ and terminate the lines where convergence with bond dimension is lost, but opted to show results for both $\chi = 32$ and $\chi = 64$ for transparency. We believe that this additional information is useful for a reader. Concerning the value of $\chi$: we find that our TDVP implementation is slower than TEBD using the same $\chi$, so we cannot compute results for these long times with $\chi$ much higher than $64$ with realistic computational resources. This is due to the implicit time integration scheme used in the split-step 1TDVP algorithm, meaning we have to solve a set of equations at each time step. For this purpose evoMPS uses an iterative scheme, which does not always converge quickly. This is a "price" that one pays for the energy conservation in this scheme. The energy conservation, is, however, very important: the energy-non-conserving TEBD scheme becomes unreliable at shorter times (despite large values of $\chi$) - at least for this system - see our response to question 3 below.

REFEREE:
"2. The present Fig.1 is unreadable - it requires huge enlarging to distinguish different curves. "

Indeed, in each of the panels of Fig. 1 there are two curves that lay essentially on top of each other. In the left ($W=4$) and middle ($W=5$) panel this happens because the convergence with bond dimension has been reached, and we want to demonstrate this. In the right ($W=8$) panel these are two curves with lengths $L=16$ and $L=50$; here this demonstrates very weak length dependence. We will update our figures in a resubmission to enhance clarity (by adding some insets) and will also make clarifying comments in the figure caption.

REFEREE:
"3. Let me mention that standard TEBD results with $\chi=250$ do not agree with those reported in Fig.1."

Indeed, the results from TEBD and TDVP on the delocalized side of the transition begin to deviate for long times. This is related to the non-conservation of energy in the TEBD method.
Motivated by the referee's comment, we have computed dynamics for $\Phi = [\sqrt{5}-1]/2$ and $W=4$ (delocalized side of the transition) using TEBD with $\chi = 128$ and $\chi = 256$. The plots are added as attachments, with TDVP results ($\chi = 64$) shown in blue and TEBD results in green and red. In addition to the imbalance, we show there also the energy as well the bond dimension used by TEBD (which saturates at the maximum value, which is 128 for one plot and 256 for the other).
Here the TEBD results are computed using the OSMPS library using default convergence parameters using around 150 realizations. As is visible from the plots, TEBD results start to deviate significantly from TDVP exactly where large errors in the energy become apparent in the TEBD results. The corresponding time is $t \approx 70$ for TEBD bond dimension 128, and somewhat later for TEBD bond dimension 256, so that the TEBD results are reliable for longer times when TEBD bond dimension is increased, as expected.

REFEREE:
"4. Why the authors do not provide information that would allow a reader to reproduce their results? What was the time step in time-dependent integration? What was the accuracy criterion (none - just $\chi$ was defined is one of the options)?"

As was briefly mentioned in the manuscript, our implementation of the method follows Ref. [22] and the bond dimension is indeed the only parameter used to establish convergence. We agree, however, with the Referee that a more detailed exposition of the method will be beneficial for the reader. We will provide some more details and references about the numerical method and how it compares to "traditional" MPS methods in a resubmission. The time-step used is 0.1 in lattice units. We use open source MPS libraries and are happy to share our implementations thereof upon reasonable request.

REFEREE:
"5. The faster than power-law decay of the imbalance on the delocalized side, the main conclusion of the manuscript, is deduced from not converged results."

The faster-than-power law decay is apparent in the converged results. In Fig. 3 we show the "flowing power law" $\beta$, which is an effective time-dependent power law. As is seen from the results, for $\Phi = (\sqrt{5}-1)/2$ convergence with $\chi$ is achieved up to $t \approx 200$, and a clear increase in $\beta(t)$ (roughly by a factor 2.5) is observed already by this time. Note that we did not observe this trend for purely random disorder in Ref. [22], so that we see a clear difference between purely random and quasiperiodic systems within the same approach. The non-converged results in the left panel of Fig. 1 also show a strong curvature, i.e. a faster-than-power law decay. While it is expected that the curvature remains when the converged is reached, we do not draw any conclusions from those results. We will further clarify this in the text in the new version.

REFEREE:
"6. The claim for the critical disorder to be $W_c=5$ is a rough estimate only. The text suggest error bar of the order of 0.5. Can the authors do better with the converged results?"

We still find a very weak decay of imbalance for $W = 4.5$, $L = 50$, and no visible decay for $W=5$, which yields the estimate for the critical disorder and the error bar of order 0.5. It is very difficult to improve the error bar substantially and, at the same time, reliably. In fact, 10% is a pretty good accuracy for determination of the MBL transition. We remind the referee that, for the purely random case, the best value obtained by Luitz et al. from exact diagonalization was $\approx 3.7$, whereas the true transition (based on our previous results in Ref. [22]) is in fact near 5.5, i.e. at 50% higher disorder. In many cases, small error bars quoted in the literature do not correspond to reality.

REFEREE:
"7. Authors claim a weak dependence on the system size for quasi-periodic potential in the introduction but they do not substantiate this claim further - showing just a single curve for $L=16$. How $W_c$ depends on the system size?"

In the case of purely random disorder, the apparent position of the transition changed from $W = 3.5-4$ for $L = 16$ to $W \approx 5.5$ using $L=50$ and $L = 100$, which is a 50% increase. For the quasi-periodic case, we do not observe such a strong increase: the value remains the same within 10% accuracy. We will add a plot to a future resubmission showing more results for different $L$ and $W$, to show this more clearly.


text:
Test if two binomial distribution are significantly different from each other

I obtained two groups of data from my experiment and calculated the binomial distribution for each group, trying to see if they are significantly different from each other. However, the z sore I got was way smaller than -4, which was a little bit odd to me. Here is how I did my calculation:

The control group: # of trails n1=34; # of successes k1=2, success rate p1=2/34=5.9% The experimental group: # of trails n2=25; # of successes k2=2, success rate p2=2/25=8.0%

average p=6.8% standard error=0.0044 test statistic z=(5.9%-8%)/standard error=-4.77 It's a two-tailed test. I couldn't find a p-value corresponding to the z score I got (-4.77) on the table. Does that mean my p-value was just really small or I made mistakes here?

• Your calculations are erroneous: you appear to have typed an extra zero in the standard error. Your approach is incorrect, as well, for several reasons: a Z-test is inapplicable and the method of computing the SE is not appropriate. Search our site for http://stats.stackexchange.com/search?q=two+sample+binomial+test, for instance. – whuber May 16 '16 at 20:40
• – Quinn Asena May 16 '16 at 22:28
• What is the process of acquiring the data? Why do you believe that the data is binomial distrbuted? – Sextus Empiricus Feb 25 at 13:52
• You are using $$\frac{p_1-p_2}{\text{s.e.} (\bar{p})}$$ Where did you got the idea to use the difference in succesrate divided by the standard error of the average succes rate? (the test which seems most close is the 'z-test to compare the equivalence of two proportions' but it is using an estimate for the standard deviation instead of an estimate for the standard error, and also it does not work well with low number of expected counts) – Sextus Empiricus Feb 25 at 14:02

In any case, the normal approximation is not applicable when there are barely any successes observed. You should be using the exact binomial distribution to do this calculation. The R function prop.test will do that test. If I'm not mistaken, you will find a p-value of 1 when you do that.

format: plain


text:
Graph coloring¶

This module gathers all methods related to graph coloring. Here is what it can do :

Proper vertex coloring

 all_graph_colorings() Compute all $$n$$-colorings a graph first_coloring() Return the first vertex coloring found number_of_n_colorings() Compute the number of $$n$$-colorings of a graph numbers_of_colorings() Compute the number of colorings of a graph chromatic_number() Return the chromatic number of the graph vertex_coloring() Compute vertex colorings and chromatic numbers

Fractional relaxations

 fractional_chromatic_number() Return the fractional chromatic number of the graph fractional_chromatic_index() Return the fractional chromatic index of the graph

Other colorings

 grundy_coloring() Compute Grundy numbers and Grundy colorings b_coloring() Compute b-chromatic numbers and b-colorings edge_coloring() Compute chromatic index and edge colorings round_robin() Compute a round-robin coloring of the complete graph on $$n$$ vertices linear_arboricity() Compute the linear arboricity of the given graph acyclic_edge_coloring() Compute an acyclic edge coloring of the current graph

AUTHORS:

• Tom Boothby (2008-02-21): Initial version

• Carlo Hamalainen (2009-03-28): minor change: switch to C++ DLX solver

• Nathann Cohen (2009-10-24): Coloring methods using linear programming

Methods¶

class sage.graphs.graph_coloring.Test

Bases: object

This class performs randomized testing for all_graph_colorings.

Since everything else in this file is derived from all_graph_colorings, this is a pretty good randomized tester for the entire file. Note that for a graph $$G$$, G.chromatic_polynomial() uses an entirely different algorithm, so we provide a good, independent test.

random(tests=1000)

Call self.random_all_graph_colorings().

In the future, if other methods are added, it should call them, too.

random_all_graph_colorings(tests=2)

Verify the results of all_graph_colorings() in three ways:

1. all colorings are unique

2. number of m-colorings is $$P(m)$$ (where $$P$$ is the chromatic polynomial of the graph being tested)

3. colorings are valid – that is, that no two vertices of the same color share an edge.

sage.graphs.graph_coloring.acyclic_edge_coloring(g, hex_colors=False, value_only=False, k=0, solver=None, verbose=0, integrality_tolerance=0.001)

Compute an acyclic edge coloring of the current graph.

An edge coloring of a graph is a assignment of colors to the edges of a graph such that :

• the coloring is proper (no adjacent edges share a color)

• For any two colors $$i,j$$, the union of the edges colored with $$i$$ or $$j$$ is a forest.

The least number of colors such that such a coloring exists for a graph $$G$$ is written $$\chi'_a(G)$$, also called the acyclic chromatic index of $$G$$.

It is conjectured that this parameter cannot be too different from the obvious lower bound $$\Delta(G) \leq \chi'_a(G)$$, $$\Delta(G)$$ being the maximum degree of $$G$$, which is given by the first of the two constraints. Indeed, it is conjectured that $$\Delta(G)\leq \chi'_a(G)\leq \Delta(G) + 2$$.

INPUT:

• hex_colors – boolean (default: False):

• If hex_colors = True, the function returns a dictionary associating to each color a list of edges (meant as an argument to the edge_colors keyword of the plot method).

• If hex_colors = False (default value), returns a list of graphs corresponding to each color class.

• value_only – boolean (default: False):

• If value_only = True, only returns the acyclic chromatic index as an integer value

• If value_only = False, returns the color classes according to the value of hex_colors

• k – integer; the number of colors to use.

• If k > 0, computes an acyclic edge coloring using $$k$$ colors.

• If k = 0 (default), computes a coloring of $$G$$ into $$\Delta(G) + 2$$ colors, which is the conjectured general bound.

• If k = None, computes a decomposition using the least possible number of colors.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

Linear Programming

EXAMPLES:

The complete graph on 8 vertices cannot be acyclically edge-colored with less $$\Delta + 1$$ colors, but it can be colored with $$\Delta + 2 = 9$$:

sage: from sage.graphs.graph_coloring import acyclic_edge_coloring
sage: g = graphs.CompleteGraph(8)
sage: colors = acyclic_edge_coloring(g)

Each color class is of course a matching

sage: all(max(gg.degree()) <= 1 for gg in colors)
True

These matchings being a partition of the edge set:

sage: all(any(gg.has_edge(e) for gg in colors) for e in g.edge_iterator(labels=False))
True

Besides, the union of any two of them is a forest

sage: all(g1.union(g2).is_forest() for g1 in colors for g2 in colors)
True

If one wants to acyclically color a cycle on $$4$$ vertices, at least 3 colors will be necessary. The function raises an exception when asked to color it with only 2:

sage: g = graphs.CycleGraph(4)
sage: acyclic_edge_coloring(g, k=2)
Traceback (most recent call last):
...
ValueError: this graph cannot be colored with the given number of colors

The optimal coloring give us $$3$$ classes:

sage: colors = acyclic_edge_coloring(g, k=None)
sage: len(colors)
3

sage.graphs.graph_coloring.all_graph_colorings(G, n, count_only=False, hex_colors=False, vertex_color_dict=False)

Compute all $$n$$-colorings of a graph.

This method casts the graph coloring problem into an exact cover problem, and passes this into an implementation of the Dancing Links algorithm described by Knuth (who attributes the idea to Hitotumatu and Noshita).

INPUT:

• G – a graph

• n – a positive integer; the number of colors

• count_only – boolean (default: False); when set to True, it returns 1 for each coloring

• hex_colors – boolean (default: False); when set to False, colors are labeled [0, 1, …, $$n - 1$$], otherwise the RGB Hex labeling is used

• vertex_color_dict – boolean (default: False); when set to True, it returns a dictionary {vertex: color}, otherwise it returns a dictionary {color: [list of vertices]}

The construction works as follows. Columns:

• The first $$|V|$$ columns correspond to a vertex – a $$1$$ in this column indicates that this vertex has a color.

• After those $$|V|$$ columns, we add $$n*|E|$$ columns – a $$1$$ in these columns indicate that a particular edge is incident to a vertex with a certain color.

Rows:

• For each vertex, add $$n$$ rows; one for each color $$c$$. Place a $$1$$ in the column corresponding to the vertex, and a $$1$$ in the appropriate column for each edge incident to the vertex, indicating that that edge is incident to the color $$c$$.

• If $$n > 2$$, the above construction cannot be exactly covered since each edge will be incident to only two vertices (and hence two colors) - so we add $$n*|E|$$ rows, each one containing a $$1$$ for each of the $$n*|E|$$ columns. These get added to the cover solutions “for free” during the backtracking.

Note that this construction results in $$n*|V| + 2*n*|E| + n*|E|$$ entries in the matrix. The Dancing Links algorithm uses a sparse representation, so if the graph is simple, $$|E| \leq |V|^2$$ and $$n <= |V|$$, this construction runs in $$O(|V|^3)$$ time. Back-conversion to a coloring solution is a simple scan of the solutions, which will contain $$|V| + (n-2)*|E|$$ entries, so runs in $$O(|V|^3)$$ time also. For most graphs, the conversion will be much faster – for example, a planar graph will be transformed for $$4$$-coloring in linear time since $$|E| = O(|V|)$$.

REFERENCES:

http://www-cs-staff.stanford.edu/~uno/papers/dancing-color.ps.gz

EXAMPLES:

sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: n = 0
sage: for C in all_graph_colorings(G, 3, hex_colors=True):
....:     parts = [C[k] for k in C]
....:     for P in parts:
....:         l = len(P)
....:         for i in range(l):
....:             for j in range(i + 1, l):
....:                 if G.has_edge(P[i], P[j]):
....:                     raise RuntimeError("Coloring Failed.")
....:     n+=1
sage: print("G has %s 3-colorings." % n)
G has 12 3-colorings.

sage.graphs.graph_coloring.b_coloring(g, k, value_only=True, solver=None, verbose=0, integrality_tolerance=0.001)

Compute b-chromatic numbers and b-colorings.

This function computes a b-coloring with at most $$k$$ colors that maximizes the number of colors, if such a coloring exists.

Definition :

Given a proper coloring of a graph $$G$$ and a color class $$C$$ such that none of its vertices have neighbors in all the other color classes, one can eliminate color class $$C$$ assigning to each of its elements a missing color in its neighborhood.

Let a b-vertex be a vertex with neighbors in all other colorings. Then, one can repeat the above procedure until a coloring is obtained where every color class contains a b-vertex, in which case none of the color classes can be eliminated with the same idea. So, one can define a b-coloring as a proper coloring where each color class has a b-vertex.

In the worst case, after successive applications of the above procedure, one get a proper coloring that uses a number of colors equal to the the b-chromatic number of $$G$$ (denoted $$\chi_b(G)$$): the maximum $$k$$ such that $$G$$ admits a b-coloring with $$k$$ colors.

A useful upper bound for calculating the b-chromatic number is the following. If $$G$$ admits a b-coloring with $$k$$ colors, then there are $$k$$ vertices of degree at least $$k - 1$$ (the b-vertices of each color class). So, if we set $$m(G) = \max \{k | \text{there are } k \text{ vertices of degree at least } k - 1 \}$$, we have that $$\chi_b(G) \leq m(G)$$.

Note

This method computes a b-coloring that uses at MOST $$k$$ colors. If this method returns a value equal to $$k$$, it cannot be assumed that $$k$$ is equal to $$\chi_b(G)$$. Meanwhile, if it returns any value $$k' < k$$, this is a certificate that the Grundy number of the given graph is $$k'$$.

As $$\chi_b(G)\leq m(G)$$, it can be assumed that $$\chi_b(G) = k$$ if b_coloring(g, k) returns $$k$$ when $$k = m(G)$$.

INPUT:

• k – integer; maximum number of colors

• value_only – boolean (default: True); when set to True, only the number of colors is returned. Otherwise, the pair (nb_colors, coloring) is returned, where coloring is a dictionary associating its color (integer) to each vertex of the graph.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

Integer Linear Program.

EXAMPLES:

The b-chromatic number of a $$P_5$$ is equal to 3:

sage: from sage.graphs.graph_coloring import b_coloring
sage: g = graphs.PathGraph(5)
sage: b_coloring(g, 5)
3

The b-chromatic number of the Petersen Graph is equal to 3:

sage: g = graphs.PetersenGraph()
sage: b_coloring(g, 5)
3

It would have been sufficient to set the value of k to 4 in this case, as $$4 = m(G)$$.

sage.graphs.graph_coloring.chromatic_number(G)

Return the chromatic number of the graph.

The chromatic number is the minimal number of colors needed to color the vertices of the graph $$G$$.

EXAMPLES:

sage: from sage.graphs.graph_coloring import chromatic_number
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: chromatic_number(G)
3

sage: G = graphs.PetersenGraph()
sage: G.chromatic_number()
3

sage.graphs.graph_coloring.edge_coloring(g, value_only=False, vizing=False, hex_colors=False, solver=None, verbose=0, integrality_tolerance=0.001)

Compute chromatic index and edge colorings.

INPUT:

• g – a graph.

• value_only – boolean (default: False):

• When set to True, only the chromatic index is returned

• When set to False, a partition of the edge set into matchings is returned if possible

• vizing – boolean (default: False):

• When set to True, tries to find a $$\Delta + 1$$-edge-coloring, where $$\Delta$$ is equal to the maximum degree in the graph

• When set to False, tries to find a $$\Delta$$-edge-coloring, where $$\Delta$$ is equal to the maximum degree in the graph. If impossible, tries to find and returns a $$\Delta + 1$$-edge-coloring. This implies that value_only=False

• hex_colors – boolean (default: False); when set to True, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting)

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

In the following, $$\Delta$$ is equal to the maximum degree in the graph g.

• If vizing=True and value_only=False, return a partition of the edge set into $$\Delta + 1$$ matchings.

• If vizing=False and value_only=True, return the chromatic index.

• If vizing=False and value_only=False, return a partition of the edge set into the minimum number of matchings.

• If vizing=True and value_only=True, should return something, but mainly you are just trying to compute the maximum degree of the graph, and this is not the easiest way. By Vizing’s theorem, a graph has a chromatic index equal to $$\Delta$$ or to $$\Delta + 1$$.

Note

In a few cases, it is possible to find very quickly the chromatic index of a graph, while it remains a tedious job to compute a corresponding coloring. For this reason, value_only = True can sometimes be much faster, and it is a bad idea to compute the whole coloring if you do not need it !

EXAMPLES:

The Petersen graph has chromatic index 4:

sage: from sage.graphs.graph_coloring import edge_coloring
sage: g = graphs.PetersenGraph()
sage: edge_coloring(g, value_only=True, solver='GLPK')
4
sage: edge_coloring(g, value_only=False, solver='GLPK')
[[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)],
[(0, 4), (1, 2), (3, 8), (6, 9)],
[(0, 5), (2, 7)],
[(1, 6), (3, 4), (5, 8), (7, 9)]]
sage: edge_coloring(g, value_only=False, hex_colors=True, solver='GLPK')
{'#00ffff': [(0, 5), (2, 7)],
'#7f00ff': [(1, 6), (3, 4), (5, 8), (7, 9)],
'#7fff00': [(0, 4), (1, 2), (3, 8), (6, 9)],
'#ff0000': [(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]}

Complete graphs are colored using the linear-time round-robin coloring:

sage: from sage.graphs.graph_coloring import edge_coloring
sage: len(edge_coloring(graphs.CompleteGraph(20)))
19

The chromatic index of a non connected graph is the maximum over its connected components:

sage: g = graphs.CompleteGraph(4) + graphs.CompleteGraph(10)
sage: edge_coloring(g, value_only=True)
9

sage.graphs.graph_coloring.first_coloring(G, n=0, hex_colors=False)

Return the first vertex coloring found.

If a natural number $$n$$ is provided, returns the first found coloring with at least $$n$$ colors.

INPUT:

• n – integer (default: 0); the minimal number of colors to try

• hex_colors – boolean (default: False); when set to True, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting)

EXAMPLES:

sage: from sage.graphs.graph_coloring import first_coloring
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: sorted(first_coloring(G, 3))
[[0], [1, 3], [2]]

sage.graphs.graph_coloring.fractional_chromatic_index(G, solver='PPL', verbose_constraints=False, verbose=0)

Return the fractional chromatic index of the graph.

The fractional chromatic index is a relaxed version of edge-coloring. An edge coloring of a graph being actually a covering of its edges into the smallest possible number of matchings, the fractional chromatic index of a graph $$G$$ is the smallest real value $$\chi_f(G)$$ such that there exists a list of matchings $$M_1, \ldots, M_k$$ of $$G$$ and coefficients $$\alpha_1, \ldots, \alpha_k$$ with the property that each edge is covered by the matchings in the following relaxed way

$\forall e \in E(G), \sum_{e \in M_i} \alpha_i \geq 1.$

For more information, see the Wikipedia article Fractional_coloring.

ALGORITHM:

The fractional chromatic index is computed through Linear Programming through its dual. The LP solved by sage is actually:

$\begin{split}\mbox{Maximize : }&\sum_{e\in E(G)} r_{e}\\ \mbox{Such that : }&\\ &\forall M\text{ matching }\subseteq G, \sum_{e\in M}r_{v}\leq 1\\\end{split}$

INPUT:

• G – a graph

• solver – (default: "PPL"); specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

Note

The default solver used here is "PPL" which provides exact results, i.e. a rational number, although this may be slower that using other solvers. Be aware that this method may loop endlessly when using some non exact solvers as reported in trac ticket #23658 and trac ticket #23798.

• verbose_constraints – boolean (default: False); whether to display which constraints are being generated

• verbose – integer (default: $$0$$); sets the level of verbosity of the LP solver

EXAMPLES:

The fractional chromatic index of a $$C_5$$ is $$5/2$$:

sage: g = graphs.CycleGraph(5)
sage: g.fractional_chromatic_index()
5/2

sage.graphs.graph_coloring.fractional_chromatic_number(G, solver='PPL', verbose=0, check_components=True, check_bipartite=True)

Return the fractional chromatic number of the graph.

Fractional coloring is a relaxed version of vertex coloring with several equivalent definitions, such as the optimum value in a linear relaxation of the integer program that gives the usual chromatic number. It is also equal to the fractional clique number by LP-duality.

ALGORITHM:

The fractional chromatic number is computed via the usual Linear Program. The LP solved by sage is essentially,

$\begin{split}\mbox{Minimize : }&\sum_{I\in \mathcal{I}(G)} x_{I}\\ \mbox{Such that : }&\\ &\forall v\in V(G), \sum_{I\in \mathcal{I}(G),\, v\in I}x_{v}\geq 1\\ &\forall I\in \mathcal{I}(G), x_{I} \geq 0\end{split}$

where $$\mathcal{I}(G)$$ is the set of maximal independent sets of $$G$$ (see Section 2.1 of [CFKPR2010] to know why it is sufficient to consider maximal independent sets). As optional optimisations, we construct the LP on each biconnected component of $$G$$ (and output the maximum value), and avoid using the LP if G is bipartite (as then the output must be 1 or 2).

Note

Computing the fractional chromatic number can be very slow. Since the variables of the LP are independent sets, in general the LP has size exponential in the order of the graph. In the current implementation a list of all maximal independent sets is created and stored, which can be both slow and memory-hungry.

INPUT:

• G – a graph

• solver – (default: "PPL"); specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

Note

The default solver used here is "PPL" which provides exact results, i.e. a rational number, although this may be slower that using other solvers.

• verbose – integer (default: $$0$$); sets the level of verbosity of the LP solver

• check_components – boolean (default: True); whether the method is called on each biconnected component of $$G$$

• check_bipartite – boolean (default: True); whether the graph is checked for bipartiteness. If the graph is bipartite then we can avoid creating and solving the LP.

EXAMPLES:

The fractional chromatic number of a $$C_5$$ is $$5/2$$:

sage: g = graphs.CycleGraph(5)
sage: g.fractional_chromatic_number()
5/2

sage.graphs.graph_coloring.grundy_coloring(g, k, value_only=True, solver=None, verbose=0, integrality_tolerance=0.001)

Compute Grundy numbers and Grundy colorings.

The method computes the worst-case of a first-fit coloring with less than $$k$$ colors.

Definition:

A first-fit coloring is obtained by sequentially coloring the vertices of a graph, assigning them the smallest color not already assigned to one of its neighbors. The result is clearly a proper coloring, which usually requires much more colors than an optimal vertex coloring of the graph, and heavily depends on the ordering of the vertices.

The number of colors required by the worst-case application of this algorithm on a graph $$G$$ is called the Grundy number, written $$\Gamma (G)$$.

Equivalent formulation:

Equivalently, a Grundy coloring is a proper vertex coloring such that any vertex colored with $$i$$ has, for every $$j < i$$, a neighbor colored with $$j$$. This can define a Linear Program, which is used here to compute the Grundy number of a graph.

Note

This method computes a grundy coloring using at MOST $$k$$ colors. If this method returns a value equal to $$k$$, it cannot be assumed that $$k$$ is equal to $$\Gamma(G)$$. Meanwhile, if it returns any value $$k' < k$$, this is a certificate that the Grundy number of the given graph is $$k'$$.

As $$\Gamma(G)\leq \Delta(G)+1$$, it can also be assumed that $$\Gamma(G) = k$$ if grundy_coloring(g, k) returns $$k$$ when $$k = \Delta(G) +1$$.

INPUT:

• k – integer; maximum number of colors

• value_only – boolean (default: True); when set to True, only the number of colors is returned. Otherwise, the pair (nb_colors, coloring) is returned, where coloring is a dictionary associating its color (integer) to each vertex of the graph.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

Integer Linear Program.

EXAMPLES:

The Grundy number of a $$P_4$$ is equal to 3:

sage: from sage.graphs.graph_coloring import grundy_coloring
sage: g = graphs.PathGraph(4)
sage: grundy_coloring(g, 4)
3

The Grundy number of the PetersenGraph is equal to 4:

sage: g = graphs.PetersenGraph()
sage: grundy_coloring(g, 5)
4

It would have been sufficient to set the value of k to 4 in this case, as $$4 = \Delta(G)+1$$.

sage.graphs.graph_coloring.linear_arboricity(g, plus_one=None, hex_colors=False, value_only=False, solver=None, verbose=0, integrality_tolerance=0.001)

Compute the linear arboricity of the given graph.

The linear arboricity of a graph $$G$$ is the least number $$la(G)$$ such that the edges of $$G$$ can be partitioned into linear forests (i.e. into forests of paths).

Obviously, $$la(G)\geq \left\lceil \frac{\Delta(G)}{2} \right\rceil$$.

It is conjectured in [Aki1980] that $$la(G)\leq \left\lceil \frac{\Delta(G)+1}{2} \right\rceil$$.

INPUT:

• plus_one – integer (default: None); whether to use $$\left\lceil \frac{\Delta(G)}{2} \right\rceil$$ or $$\left\lceil \frac{\Delta(G)+1}{2} \right\rceil$$ colors.

• If 0, computes a decomposition of $$G$$ into $$\left\lceil \frac{\Delta(G)}{2} \right\rceil$$ forests of paths

• If 1, computes a decomposition of $$G$$ into $$\left\lceil \frac{\Delta(G)+1}{2} \right\rceil$$ colors, which is the conjectured general bound.

• If plus_one = None (default), computes a decomposition using the least possible number of colors.

• hex_colors – boolean (default: False):

• If hex_colors = True, the function returns a dictionary associating to each color a list of edges (meant as an argument to the edge_colors keyword of the plot method).

• If hex_colors = False (default value), returns a list of graphs corresponding to each color class.

• value_only – boolean (default: False):

• If value_only = True, only returns the linear arboricity as an integer value.

• If value_only = False, returns the color classes according to the value of hex_colors

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

Linear Programming

COMPLEXITY:

NP-Hard

EXAMPLES:

Obviously, a square grid has a linear arboricity of 2, as the set of horizontal lines and the set of vertical lines are an admissible partition:

sage: from sage.graphs.graph_coloring import linear_arboricity
sage: g = graphs.Grid2dGraph(4, 4)
sage: g1,g2 = linear_arboricity(g)

Each graph is of course a forest:

sage: g1.is_forest() and g2.is_forest()
True

Of maximum degree 2:

sage: max(g1.degree()) <= 2 and max(g2.degree()) <= 2
True

Which constitutes a partition of the whole edge set:

sage: all((g1.has_edge(e) or g2.has_edge(e)) for e in g.edge_iterator(labels=None))
True

sage.graphs.graph_coloring.number_of_n_colorings(G, n)

Compute the number of $$n$$-colorings of a graph

INPUT:

• G – a graph

• n – a positive integer; the number of colors

EXAMPLES:

sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: number_of_n_colorings(G, 3)
12

sage.graphs.graph_coloring.numbers_of_colorings(G)

Compute the number of colorings of a graph.

Return the number of $$n$$-colorings of the graph $$G$$ for all $$n$$ from $$0$$ to $$|V|$$.

EXAMPLES:

sage: from sage.graphs.graph_coloring import numbers_of_colorings
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: numbers_of_colorings(G)
[0, 0, 0, 12, 72]

sage.graphs.graph_coloring.round_robin(n)

Compute a round-robin coloring of the complete graph on $$n$$ vertices.

A round-robin coloring of the complete graph $$G$$ on $$2n$$ vertices ($$V = [0, \dots, 2n - 1]$$) is a proper coloring of its edges such that the edges with color $$i$$ are all the $$(i + j, i - j)$$ plus the edge $$(2n - 1, i)$$.

If $$n$$ is odd, one obtain a round-robin coloring of the complete graph through the round-robin coloring of the graph with $$n + 1$$ vertices.

INPUT:

• n – the number of vertices in the complete graph

OUTPUT:

EXAMPLES:

sage: from sage.graphs.graph_coloring import round_robin
sage: round_robin(3).edges()
[(0, 1, 2), (0, 2, 1), (1, 2, 0)]

sage: round_robin(4).edges()
[(0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 2, 0), (1, 3, 1), (2, 3, 2)]

For higher orders, the coloring is still proper and uses the expected number of colors:

sage: g = round_robin(9)
sage: sum(Set(e[2] for e in g.edges_incident(v)).cardinality() for v in g) == 2 * g.size()
True
sage: Set(e[2] for e in g.edge_iterator()).cardinality()
9

sage: g = round_robin(10)
sage: sum(Set(e[2] for e in g.edges_incident(v)).cardinality() for v in g) == 2 * g.size()
True
sage: Set(e[2] for e in g.edge_iterator()).cardinality()
9

sage.graphs.graph_coloring.vertex_coloring(g, k=None, value_only=False, hex_colors=False, solver=None, verbose=0, integrality_tolerance=0.001)

Compute Vertex colorings and chromatic numbers.

This function can compute the chromatic number of the given graph or test its $$k$$-colorability.

See the Wikipedia article Graph_coloring for further details on graph coloring.

INPUT:

• g – a graph.

• k – integer (default: None); tests whether the graph is $$k$$-colorable. The function returns a partition of the vertex set in $$k$$ independent sets if possible and False otherwise.

• value_only – boolean (default: False):

• When set to True, only the chromatic number is returned.

• When set to False (default), a partition of the vertex set into independent sets is returned if possible.

• hex_colors – boolean (default: False); when set to True, the partition returned is a dictionary whose keys are colors and whose values are the color classes (ideal for plotting).

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

• If k=None and value_only=False, then return a partition of the vertex set into the minimum possible of independent sets.

• If k=None and value_only=True, return the chromatic number.

• If k is set and value_only=None, return False if the graph is not $$k$$-colorable, and a partition of the vertex set into $$k$$ independent sets otherwise.

• If k is set and value_only=True, test whether the graph is $$k$$-colorable, and return True or False accordingly.

EXAMPLES:

sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.PetersenGraph()
sage: vertex_coloring(g, value_only=True)
3


text:
Volume 19, issue 3 (2015)

 Recent Issues
 The Journal About the Journal Editorial Board Editorial Interests Editorial Procedure Subscriptions Submission Guidelines Submission Page Policies for Authors Ethics Statement ISSN (electronic): 1364-0380 ISSN (print): 1465-3060 Author Index To Appear Other MSP Journals

Vyacheslav Krushkal

Geometry & Topology 19 (2015) 1657–1683
Abstract

A link in the $3$–sphere is called (smoothly) slice if its components bound disjoint smoothly embedded disks in the $4$–ball. More generally, given a $4$–manifold $M$ with a distinguished circle in its boundary, a link in the $3$–sphere is called $M\phantom{\rule{0.3em}{0ex}}$–slice if its components bound in the $4$–ball disjoint embedded copies of $M$. A $4$–manifold $M$ is constructed such that the Borromean rings are not $M\phantom{\rule{0.3em}{0ex}}$–slice but the Hopf link is. This contrasts the classical link-slice setting where the Hopf link may be thought of as “the most nonslice” link. Further examples and an obstruction for a family of decompositions of the $4$–ball are discussed in the context of the A-B slice problem.

Keywords
Slice links, the Milnor group, the A-B slice problem
Mathematical Subject Classification 2010
Primary: 57N13
Secondary: 57M25, 57M27


text:
# Is $a$ bigger than $0$ or not?

Consider Goldbach's original conjecture (no need worry, because we don't talk about "Goldbach" itself):

every integer $$n> 2$$ could be detached as a sum of three primes. (In Goldbach's age, $$1$$ is regarded as a prime.)

For any $$n>2$$, we denote the statement above as $$p(n)$$. Then define

$$a_n:=\begin{cases} 0, &\text{if p(n) is true},\\ 1, &\text{otherwise}. \end{cases}$$

Note that $$a(n)$$ is definite, since every $$p(n)$$ could be verified, at least by machine, as long $$n$$ is given. However, consider the decimal number $$a:=0.00a_3a_4a_5\cdots.$$

What's $$a$$? Is it a real number?

If $$a$$ is a real number, then we can compare the magnitude of $$a$$ and $$0$$, since the real number field is ordered.

But we can't in fact. If $$a=0$$, then "Goldbach" is proven, and if not, then "Goldbach" is overturned. However, it's in suspense hitherto whether Goldbach is true or not.

Probably, we may say $$a$$ is indefinite, that's to say, we do not know what $$a$$ is yet. But a new question is coming about:

Why we know any digit but do not know the number itself ? In order to know the number, what else we need ?

Further, let's compare $$a$$ with another classic number $$\pi=3.1415926\cdots.$$

Indeed, we do not know all the digits of $$\pi$$ untill we compute every one. But we can safely say it's $$\pi$$. What's the exact difference between $$a$$ and $$\pi$$ on earth? Why we think we know $$\pi$$ but do not know $$a$$? In another word, what does "knowing a number" mean exactly? And in what sense can we say we know a number?

• What exactly do you mean by "we can know every digit of a"? – Yuriy S Jan 9 at 7:21
• There is no paradox here. You correctly observe that we can have a very well-defined - even explicitly computable - real number $a$, yet be unable to prove whether or not $a=0$. Why should this be problematic, though? – Noah Schweber Jan 9 at 7:24
• "Note that a(n) is definite, since every p(n) could be verified, at least by machine, as long n is given" . there are infinitely many $n$. We can only verify a finite many of them. We can potentially know any $n$ we want but we will only know the ones that we actually do verify and potentially being able to verify any of them is not the same as actually verifying everyone of them.... Consider that you could read any page, but only one page of Moby Dick. Since each one of every page can be read does that mean you can read every page. No, it does not. – fleablood Jan 9 at 8:05
• Just because we can verify any $a_k$ doesn't mean we will and we won't know what an $a_k$ is until we verify it. And we are NOT going to verify all off them. we only have enough time in the history of the universe and the lifetime of every human being to verify maybe $10$ trillion of them. And it's true we can verify any $10$ trillion but whichever ten trillion we do verify there will by infinitely more that we dont get around to verifying. – fleablood Jan 9 at 8:20
• It may help to distinguish between (1) properties that are satisfied by exactly one real number, and (2) properties that a number might satisfy. Those of type (1) can be used to define a real number, and those of type (2) are questions we could ask about a number. As an example, one can prove by calculus methods (rates of increase and intermediate value theorem) that "$x^2 + 1 = 2^x$ and $4 < x < 5$" is satisfied by exactly one real number. Let's give this number a name, say $B.$ We can now ask things like is $B$ rational, what is the $10$th digit to the right of the decimal point of $B,$ etc. – Dave L. Renfro Jan 9 at 11:24

What you have defined is a real number. Indeed, from the definition given it is also a computable number. Does $$a=0$$? Well, this is something we simply do not know. Of course, there is nothing wrong with not knowing a number from a definition. For example, the Ramsey number $$R(6,6)$$ is bounded between $$102$$ and $$165$$. However, we have no idea what this number is. Another example, define the number $$x$$ to be $$0$$ if the Riemann hypothesis is true and $$1$$ if it is false. This is a perfect definition, but I have no idea what $$x$$ is and if you can tell me you will get a million dollars.

To reiterate: One can write a perfectly sound mathematical definition and not know what that number actually is. This is not a paradox, but simply something that can arise naturally.

• Why we know every digit and do not know the number itself? In order to know the number, what else we need ? – mengdie1982 Jan 9 at 7:37
• Do you know every digit of $\pi$? No? But defining $\pi$ as the ratio of the circumference to the diameter is a perfectly reasonable definition. We can find as many finite digits as we like but we can never know an infinite number of digits unless something else is proved. Same with your number $a$. – QC_QAOA Jan 9 at 7:55
• I say your Riemann number is 0, and my spouse says it's 1. Please send 1 million dollars to our joint account. ;-) – Joffan Jan 11 at 14:30

You are confusing "we can verify any number of them" with "we can verify every one of them". yes, we can verify any of the ones we choose to but we can't verify any of the ones we don't choose to, and as there are infinitely many of them there will always be an infinitely number of them we don't choose.

So although we can know any $$a_i$$, we can't know every $$a_i$$.

• Sir, please compare $a$ with $\sqrt{2}$. What's the difference between them, on the point " know" ? Why we know $\sqrt{2}$ but do not know $a$? – mengdie1982 Jan 9 at 11:01
• @mengdie1982: One can prove with significant machinery (Intermediate Value Theorem) that there is a unique positive real number whose square is $=2$. That number is usually called $\sqrt 2$, and we can in principle compute any digit of it. Everything "extra" we know about it is that by definition, it is a number whose square is $2$. Often when dealing with it, it is actually only that information that one uses (and e.g. its negative in $\mathbb Q(\sqrt 2)$ can play the same role, or one of the two numbers in the $3$-adics $\mathbb Q_3$ whose square is $2$ ...). – Torsten Schoeneberg Jan 9 at 16:19
• [continued] Exercise: Define a real number $x$ where deciding whether the real number $\sqrt 2 \stackrel{?}= x$ or not is equivalent to some open conjecture. – Torsten Schoeneberg Jan 9 at 16:22
• We don't know all the digits of $\sqrt{2}$. Why did you think we did? We have methods to calculate them to whatever accuracy we want but we certainly don't know what they all are. – fleablood Jan 9 at 16:25
• Maybe more strikingly, mengdie1982, how well do you think we "know" $\sqrt 2$? Do you know if the digit $7$ occurs infinitely often in its decimal expansion? I don't, and I think it is not known. (Cf. the same question about $\pi$: math.stackexchange.com/q/2791/96384. If that is known about $\sqrt 2$, it would probably by some intricate argument via continued fractions. What really is not known, according to Wikipedia, is whether $0, ..., 9$ all have the same asymptotic density in $\sqrt 2$'s decimal expansion: en.wikipedia.org/wiki/Normal_number) – Torsten Schoeneberg Jan 9 at 16:51

$$a$$ is a real number, defined by the definition you have given above.

It is computable, in the sense that we can calculate it to arbitrary numerical precision via an algorithm.

However, it is not currently known whether $$a=0$$.

None of these statements are in conflict. In fact, there are many such cases in mathematics where there is some perfectly well-defined answer to a certain question, and where we could get successively better computational bounds that decide more and more of the digits of the number, but where we don't yet know whether those bounds will converge to a certain conjectural value.

The word "know" is doing a lot of work in this supposed paradox, and if you specify any particular notion of what it means to "know" what a number is you'll find that it is no longer an apparent contradiction.

• Sir, my question is the last sentence. – mengdie1982 Jan 9 at 7:32
• Why we know every digit and do not know the number itself? In order to know the number, what else we need ? – mengdie1982 Jan 9 at 7:34
• We don't know every digit! Every digit is knowable, in the sense that a computer program could in theory compute it. But we do not actually know, say, the $n$th digit where $n=\lfloor e^{e^{e^{1000}}}\rfloor$. – RavenclawPrefect Jan 9 at 7:39

We can know any digit of $$a$$ (after a possibly very long but finite computation), but we do not currently know every digit. There is a difference: if you wanted to know the $$n$$th digit of $$a$$, give me some long but finite time, and I can tell you. But that is not the same as saying that I can tell you, currently, off the back of my mind, every single digit of $$a$$, for arbitrary $$n$$.

There is no paradox, you just need to be precise about the meaning of "know". You could say, for instance, that we can know any digit of $$a$$, but do not currently know every digit.


text:
## Mohammad Ghomi and Joel Spruck settled the Cartan-Hadamard conjecture!

Greetings from Oberwolfach from a great conference on algebraic, geometric, and topological combinatorics. Stay tuned for more pictures and updates from Oberwolfach and CERN, and also in case you did not see it already here is the link to the previous post with the sunflower news.  And towards the end of this post a connection to Saint-Exupéry’s “Le Petit Prince”.

Or Hershkovich reported on FB group “diggings in mathematics” about the solution of the Cartan-Hadamard conjecture by Mohammad Ghomi and Joel Spruck. The conjecture, one of the most famous conjectures in Riemannian geometry, is a far reaching extension of the classic isoperimetric inequality for general Riemannian manifolds.

Here is the abstract: We prove that the total positive Gauss-Kronecker curvature of any closed hypersurface embedded in a complete simply connected manifold of nonpositive curvature $latex M^nn\ge 2$, is bounded below by the volume of the unit sphere in Euclidean space $latex R^n$. This yields the optimal isoperimetric inequality for bounded regions of finite perimeter in M, via Kleiner’s variational approach, and thus settles the Cartan-Hadamard conjecture. The proof employs a comparison formula for total curvature of level sets in Riemannian manifolds, and estimates for smooth approximation of the signed distance function. Immediate applications include sharp extensions of the Faber-Krahn and Sobolev inequalities to manifolds of nonpositive curvature.

The proof is quite involved (the paper is 80 pages long) and is based on extending Kleiner’s approch for the 3- and 4- dimensional case. Or Hershkovich raised on FB an even more general question related to isospectral relations based on higher homology.

We also note a 2013  paper by Benoît Kloeckner and Greg Kuperberg The Cartan-Hadamard conjecture and the little prince

A page from Kloeckner-Kuperberg’s paper, and related FB posts by Greg (below).

Advertisements
Posted in Geometry, Uncategorized | | 5 Comments

## Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture

WOW! The new paper https://arxiv.org/abs/1908.08483 improved bounds for the sunflower lemma gives the most dramatic progress on the sunflower conjecture since it was asked. Congratulations to Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang.

(Written on my smartphone will expand it when reconnected to my laptop.)  (Reconnected) Rather, I will write about it again in a few weeks. Let me mention now that while the old difficult and ingenious improvements stayed in the neighborhood of Erdos and Rado initial upper bound the new result is in the neighborhood of the conjecture! (And is tight for a certain robust version of the problem!)

Let me also mention that we discussed the sunflower conjecture here many times and polymath10 (wiki pagefirst post, last post) was devoted to the problem.)

Update: Let me mention an important progress on the sunflower conjecture from 2018 by Junichiro Fukuyama in his paper Improved Bound on Sets Including No Sunflower with Three Petals. I missed Fukuyama’s paper at the time and I thank Sasha Kostochka and Andrew Thomason for telling me about it now.

Posted in Combinatorics, Uncategorized | 6 Comments

## The Argument against Quantum Computers – a CERN Colloquium and a New Paper

Let me announce my CERN colloquium this Thursday, August 22, 2019, 16:30-17:30 entitled “The argument against quantum computers.” If you are at CERN or the neighborhood, please please come to the lecture. (Tea and coffee will be served at 16:00. ) If you are further away, there is a live broadcast.

A few weeks ago I uploaded to the arXive a new paper with the same title “The argument against quantum computers“. The paper will appear in the volume: Quantum, Probability, Logic: Itamar Pitowsky’s Work and Influence, Springer, Nature (2019), edited by Meir Hemmo and Orly Shenker. A short abstract for the lecture and the paper is:

We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction nor a demonstration of “quantum supremacy.”  Some general principles governing the behavior of noisy quantum systems are derived.

The new paper and lecture have the same title as my 2018 interview with Katia Moskvitch at Quanta Magazine (see also this post).  Note that Christopher Monroe has recently contributed a very interesting comment to the Quanta article. My paper is dedicated to the memory of Itamar Pitowsky, and for more on Itamar see the post Itamar Pitowsky: Probability in Physics, Where does it Come From? See also this previous post for two other quantum events in Jerusalem: a seminar in the first semester and a winter school on The Mathematics of Quantum Computation  on December 15 – December 19, 2019.

A slide from a lecture by Scott Aaronson where he explains why soap bubble computers cannot solve the NP-complete Steiner-tree problem. Noisy intermediate scale quantum (NISQ) circuits are computationally much more primitive than Scott’s soap bubble computers and this will prevent them from achieving neither “quantum supremacy” nor good quality quantum error correcting codes.  (source for the picture)

Low-entropy quantum states give probability distributions described by low degree polynomials, and very low-entropy quantum states give chaotic behavior. Higher entropy enables classical information.

| Tagged , | 8 Comments

## Equiangular lines with a fixed angle and other breakthroughs from Yufei Zhao’s blog

Today I would like to report about some breakthroughs in the area of combinatorics, and about blog posts in Yufei Zhao’s blog that describe these remarkable results (better than I can). Many of the coauthors in these breakthroughs are undergraduate students.

## Equiangular lines with a fixed angle

### by Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang and Yufei Zhao.

Paper ; blog post (end of July, 2019)

A collection of equiangular lines is a collection of lines so that the angles between every pair of lines in the same?

Here are two classical questions:

1. What is the maximum number of equiangular lines in $\mathbb R^d$?
2. Given an angle $\alpha$ what is the maximum number of equiangular lines in $\mathbb R^d$? so that the angle between every two lines is $\alpha?$

In 2000 Dom de Caen found for the first time an equiangular set of lines in $d$ space of size $cd^2$. (The crucial observation that one of the graphs in the Cameron–Seidel association scheme has a certain eigenvalue of large multiplicity.  Prior to this construction, the largest sets had sizes of order $d^{3/2}$.  In de Caen’s example the lines have angles approaching 90 degrees, and question 2 for a fixed value of $\alpha$ led to very different bounds. (For another result by Dom, see this post.)

There were some important progress on this problem by Igor Balla, Felix Dräxler, Peter Keevash, and Benny Sudakov, as featured in this  Quanta Magazine article written by Kevin Hartnett. Zilin, Jonathan, Yuan, Shengtong, and Yufei  finished off the problem in a clean and crisp manner, in a 10-page paper with a self-contained proof. On the way they proved the following very interesting theorem.

Theorem: A bounded degree graph must have sublinear second eigenvalue multiplicity.

## Impartial digraphs

### by Yufei Zhao and Yunkun Zhou.

Paper, blog post (end of June 2019)

Abstract: We prove a conjecture of Fox, Huang, and Lee that characterizes directed graphs $H$ that have constant density in all tournaments: they are disjoint unions of trees that are each constructed in a certain recursive way.

“Constant density in all tournaments” means that for some $n_0$ (and hence for all $n \ge n_0$, every tournament with $n$ vertices has the same number of copies of $H$. (On the nose!)

This result is related to the famous Sidorenko’s conjecture. Let me copy its description from the paper:

For undirected graphs, conjectures of Sidorenko and Erdős–Simonovits (commonly referred to as Sidorenko’s conjecture) say that for every bipartite graph $H$, the $H$-density in a graph of fixed density is minimized asymptotically by a random graph. Lately the conjecture has been proved for many families of $H$ though the conjecture remains open in general. In particular, the case $H = K_{5,5}\backslash C_{10}$ is open.

Yufei Zhao

## More

Let me describe briefly three additional posts on Yufei’s blog with two results from 2018 and one result from 2014.

### Ashwin Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao  A reverse Sidorenko inequality; (blog post) ; The number of independent sets in an irregular graph; blog post.

These are two remarkable papers by the same team of researchers. The paper  on the number of independent sets in a regular graph settled a famous 2001 conjecture by Jeff Kahn. An earlier breakthrough on the problem was made by Zhao in 2009 when he was an undergraduate student.

### Eyal Lubetzky and Yufei Zhao,  On the variational problem for upper tails of triangle counts in sparse random graphs. Blog post.

Recently  I wrote a post Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem describing a major breakthrough on the infamous upper tail problem. Over the years I heard a lot of lectures and private explanation on upper tails and the remarkable related mathematics. I remember lectures by Kim and Vu from the early 2000’s and by Varadhan from ICM 2010 describing (among other things) the fundamental paper by  Chatterjee and Varadhan,  and later works by  DeMarco and Kahn,  and by  Chatterjee and Dembo  and Lubetzky and Zhao and others. But when I wrote the post I realized my knowledge is too sparse for giving a thorough description, and I decided not to wait and write a short post. This post by Yufei describes some of the history very nicely as well as the major papers by Eyal and Yufei from 2012 and 2014.

Posted in Combinatorics | | Leave a comment

## Two Important Quantum Announcements!

I am very happy to announce two quantum events. First, I would like to announce a course “Computation, quantization, symplectic geometry, and information” in the first 2019/2020 semester  at the Hebrew University of Jerusalem (HUJI). The course will by on Sundays 14:00-16:00. Second, I would also like to announce The 4th Advanced School in Computer Science and Engineering on The Mathematics of Quantum Computation  on December 15 – December 19, 2019, at IIAS HUJI.

Emmy Noether (left) Grete Hermann (right)

## A quantum “Kazhdan’s seminar” at HUJI: Computation, quantization, symplectic geometry, and information.

“In the fall of 2019 Dorit Aharonov, Gil Kalai, Guy Kindler and Leonid Polterovich intend to run a new one semester course (as a Kazhdan seminar) attempting to connect questions about noise and complexity in quantum computation, with ideas and methods about “classical-quantum correspondence”.that are well studied in symplectic geometry. The course will be highly research-oriented, and will attempt to teach the basics in both areas, and define and clarify the interesting research questions related to the connections between these areas, with the hope that this will lead to interesting insights.  The course is oriented to grad students (and faculty), with reasonable background in mathematics, and with interest in the connections between mathematical and computational aspects of quantum mechanics. (See below for a full description.)”

The course will by on Sundays 14:00-16:00 in Ross building.

See also the post  Symplectic Geometry, Quantization, and Quantum Noise from January 2013. (The seminar was initially planned to 2014 but some bumps in the road delayed it to 2019.)

## A winter school at IIAS: The Mathematics of Quantum Computation

The Mathematics of Quantum Computation
The 4th Advanced School in Computer Science and Engineering
Event date: December 15 – December 19, 2019

“We will be organizing a math-oriented quantum computation school in the IIAS at the Hebrew university. No prior knowledge on quantum will be assumed.  The school will introduce TCS and math students and faculty, who are interested in the more mathematical side of the area, to the beautiful and fascinating mathematical open questions in quantum computation, starting from scratch. We hope to reach a point where participants gain initial tools and basic perspective to start working in this area. (See below for a full description.)

Organizers: Dorit Aharonov, Zvika Brakerski, Or Sattath, Amnon Ta-Shma,

Main (confirmed) Speakers: Sergey Bravyi, Matthias Christandl, Sandy Irani, Avishay Tal, Thomas Vidick, (1-2 additional speakers may be added later).

Additional (confirmed) lectures will be given by: Dorit Aharonov,  Zvika Brakerski,  and/ Or Sattath. (1-2 additional speakers may be added later).”

The Isreali Institute of Advanced Study hosted already a 2014 school about quantum information as part of its legendary physics series of schools, and also hosted QSTART in 2013.

## Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.)

The cover of Avi Wigderson’s book “Mathematics and computation” as was first exposed to the public in Avi’s Knuth Prize videotaped lecture. (I had trouble with 3 of the words: What is EGDE L WONK 0?  what is GCAAG?GTAACTC ?  TACGTTC ?  I only figured out the first one.)

Avi Wigderson’s book  “Mathematics and computation, a theory revolutionizing technology and science” is about to be published by Princeton University Press. The link is to a free copy of the book which will always be available on Avi’s homepage. (See also this re-blogged post here of Boaz Barak.)

One main theme of the book is the rich connection between the theory of computing and other areas (in fact, most areas) of mathematics. See also this self contained survey (based on Chapter 13 of the book) by Avi Interactions of Computational Complexity Theory and Mathematics, which in 27 pages overviews relations to number theory, Geometry, Operator Theory, Metric Geometry, Group Theory, Statistical Physics, Analysis and Probability, Lattice Theory and Invariant Theory. Of course,  over the last four decades,  Avi himself has been among the main heroes in finding many paths between mathematics and the theory of computing.

Another theme of the book and of several talks by Avi is that the theory of computing has revolutionary connections with many fields of science and technology. Again, this theme is present in the entire book and is emphasized in Chapter 20, which also appeared as a self contained paper  “On the nature of the Theory of Computation (ToC).”  Let me quote one sentence from Avi’s book that I propose for discussion. (For the complete quote see the end of the post.)

### The intrinsic study of computation transcends human-made artifacts, and its expanding connections and interactions with all sciences, integrating computational modeling, algorithms,  and complexity into theories of nature and society, marks a new scientific revolution!

Of course, similar ideas were also expressed by several other prominent scientists, and let me mention Bernard Chazelle’s essay: The Algorithm: Idiom of Modern Science. (Feel free to give further examples and links in the comment section.)

### Let’s discuss:  Integrating computational modeling, algorithms,  and complexity into theories of nature, marks a new scientific revolution!

I propose to discuss in the comment section the idea that the theory of computing offers a scientific revolution. Very nice cases to examine are the computational study of randomness and connections to statistics, connections with economy and connections with biology. Comments on the relations between the theory of computation and other areas of mathematics are also very welcome.

Avi’s concluding slide compared these three great theories of human understanding.

(Previous attempts of open discussions were made in the following posts on this blog: 10 Milestones in the History of Mathematics according to Nati and Me; Why is mathematics possible? (and a follow up post); When it rains it poursIs it Legitimate/Ethical for Google to close Google+?; An Open Discussion and Polls: Around Roth’s Theorem; Is Mathematics a Science?)

Avi promotes the idea of the central place of the theory of computing in his talks and writings Continue reading

## An interview with Noga Alon

Update: and here is a great interview of Noga in English and the interviewer is Narkis Alon, Noga’s youngest daughter and Amalya Duek.

I was very happy to interview my academic doctoral  twin and long-time friend Noga Alon.  The interview is an initiative of the Israel Academy of Sciences and Humanities. (This is my second interview of this kind. See here for an interview with Yisrael Aumann.) The interview is in Hebrew. (Update: Automatically-produced  English subtitles are available.)

For our English speaking readers here is a recent Numberphile video with Noga.

We agreed in advance that most of the interview would be about mathematics, and  most of the time  we courageously (and perhaps somewhat recklessly)  tried to explain to a large audience  (starting from scratch) some of Noga’s research directions and results. We hope that people will enjoy the beauty of it even with the missing details and background.

### Noga’s parents, family and childhood

In the first part of the  interview  Noga talked about his family, his parents, Dror and Hemda, his great uncle Yigal Alon, his early childhood, and his early interest in mathematics. Noga liked to solve mathematical riddles from a young age. One reason Noga was drawn to mathematics is that unlike other topics, in mathematics there are absolute truths, and a mathematical proof (when such exists)  is perhaps the only way you can settle a debate. Noga gave an amusing example from his youth regarding the Eurovision song context. Then he mentioned the Hebrew Reali school in Haifa, a mathematics teacher there, Yaakov Kaplan,  newly immigrated from the former Soviet Union, who greatly influenced Noga. Noga also talked about his participation in the Israeli Mathematical Olympiad where the two of us first met 45 years ago.  Next, the two of us met during our military service, and in parallel to his service, Noga finished his M. Sc. and Ph. D with Micha A. Perles, who was also my supervisor.

### An hour of mathematics

The mathematical part of the video starts with Noga’s  overview of combinatorics. Then we moved to specific topics.

(22:40- 33:30) Noga’s negative solution to Shannon’s conjecture about the capacity of two graphs (and a little about Claude Shannon and information theory)

(33:30- 40:25) The combinatorial nullstellensatz and the polynomial method and a little about the game SET

(40:25 – 46:50) The probabilistic method and a little on the history of probability and about Paul Erdos.

(46:50-  54:50)  Streaming algorithms, a topic introduced by Noga Alon, Yossi Matias, and Mario Szegedy, and more generally, about positive and negative results in computer science, and their practical applications.

(54:50 – 59:25)    Expander graphs and “spectroscopy of graphs”

59:25  -1:05:40 Ramsey theory

1:05:40-1:12:20 Factoring integers with quantum computers and with classical methods

1:12:00-1:20:00 Combinatorics, economics and game theory:  Noga’s theorem that large committees require a large budget!

### Going back from mathematics to life itself

After a full hour of mathematics, we returned to life itself. Memories from our years as postdocs at MIT, and our 1993 conference in Jerusalem. Noga talked a little about women in science and in society, about his three daughters, about  the possibility that science, like sport,  can bridge different groups and different peoples, and about politics and prospects for better relations with our Arab neighbors and Iran (Noga is somewhat optimistic and so am I),  prospects about getting old (we are hopeful about it), and advice to young researchers. Noga’s message at the end was that there are many paths to mathematical research and he encouraged young people that like mathematics to follow and enjoy them.

Ramsey theory and a conjecture by Erdos and Sos

Probability theory and the probabilistic method

| Tagged | 6 Comments

## TYI 39 : Can a coalition of children guarantees all being in the same class?

There is a class of children that have just finished elementary school. Now they all move from elementary school to high school and classes are reshuffled. Each child lists three friends, and the assignment of children into classes ensures that each child will have at least one of these three friends in his class.

One of the children heard from five of his schoolmates that they found that they can make their selections in a way that will ensure that all five will be assigned to the same class!

### Test your intuition: Is there a strategy for five of the children that will ensure that all five will be assigned to the same class?

Can a larger group of children coordinate their choices to ensure that they will all necessarily be assigned to the same class?

| Tagged | 3 Comments

## Matan Harel, Frank Mousset, and Wojciech Samotij and the “the infamous upper tail” problem

Let me report today on a major breakthrough in random graph theory and probabilistic combinatorics. Congratulations to Matan, Frank, and Vojtek!

Artist: Heidi Buck. “Catch a Dragon by the Tail 2”source )

Upper tails via high moments and entropic stability by Matan Harel, Frank Mousset, and Wojciech Samotij

Abstract:

Suppose that X is a bounded-degree polynomial with nonnegative coefficients on the p-biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper tail probability of X whenever an associated extremal problem satisfies a certain entropic stability property. We apply this result to solve two long-standing open problems in probabilistic combinatorics: the upper tail problem for the number of arithmetic progressions of a fixed length in the p-random subset of the integers and the upper tail problem for the number of cliques of a fixed size in the random graph $G_{n,p}$. We also make significant progress on the upper tail problem for the number of copies of a fixed regular graph H in $G_{n,p}.$ To accommodate readers who are interested in learning the basic method, we include a short, self-contained solution to the upper tail problem for the number of triangles in $G_{n,p}$ for all p=p(n) satisfying $\frac {\log n}{n}$ $\ll$ $p \ll 1$.

The introduction does a very nice job of presenting the rich history of the problem.  Here is a 2002 paper by Svante Janson and Andrzej Ruciński on the infamous upper tail.  (And a lot has happened since then with regard to this problem and on non linear large deviation theory). Following, there is a lovely section with a short solution for the case of triangles.

Forthcoming reference [48] talks about lower tails! Stay tuned!

Posted in Combinatorics, Probability | | 1 Comment

## Isabella Novik and Hailun Zheng: Neighborly centrally symmetric spheres exist in all dimensions!

A tweet-long summary: The cyclic polytope is wonderful and whenever we construct an analogous object we are happy. Examples: Neighborly cubic polytopes; The amplituhedron; and as of last week, the Novik-Zheng new construction of neighborly centrally symmetric spheres!

## At last: Neighborly CS spheres!

The news: Isabella Novik and Hailun Zheng’ paper  Highly neighborly centrally symmetric spheres, resolves an old standing problem in this field.

Here is the abstract:

In 1995, Jockusch constructed an infinite family of centrally symmetric 3-dimensional simplicial spheres that are cs-2-neighborly. Here we generalize his construction and show that for all d ≥ 4 and n ≥ d, there exists a centrally symmetric (d − 1)-dimensional simplicial sphere with 2n vertices that is cs-[d/2]-neighborly. This result combined with work of Adin and Stanley completely resolves the upper bound problem for centrally symmetric simplicial spheres.

Congratulations to Isabella and Hailun!

## Some background to the Novik and Zheng breakthrough

Centrally symmetric bodies: A centrally symmetric (cs) polytope convex body in $\mathbb R^d$ satisfies $x \in P$ implies $-x \in P$. Centrally symmetric bodies are the unit balls of normed spaces.

Centrally symmetric simplicial spheres: A triangulation $K$ of a  $(d-1)$-dimensional sphere with a set $V$ of vertices is centrally symmetric if there is an involution $\phi$ on $V$ that $\phi$ maps a face of $K$ to a face of $K$ and for every vertex $v$, $\phi(v) \ne v$ and $\{v , \phi (v)\}$ is not an edge of $K$.  The boundary complex of a cs $d$-polytopes is a cs triangulation of $S^{d-1}$.

Neighborliness. A simplicial complex $K$  is $m$-neighborly of every set of $m$ vertices of $P$ form a face.  (The definition was first considered  for simplicial $d$-polytopes $P$.) The cyclic $d$-polytope with $n$ vertices is $[d/2]$-neighborly. (The only ($[d/2]$+1)-neighborly simplicial $(d-1)$-sphere is the simplex. There are many other $[d/2]$-neighborly simplicial $d$-polytopes and $(d-1)$-spheres.

cs-Neighborliness. Let $K$ be a simplicial complex with an involution $\phi$ on its vertices which acts on $K$ (maps faces to faces) and has the property that $\phi(v)$ is not adjacent to $v$ (and $\phi (v) \ne v$). We will call $v$ and $\phi (v)$ antipodal. $K$ is cs-$m$-neighborly if every set of $m$ vertices that contains no pair of antipodal vertices is a face of $K$. The only cs-$m$-neighborly simplicial sphere is the boundary complex of the cross polytope.

The existence of cs-$[d/2]$-neighborly spheres. It was an important open question whether  cs $[d/2]$-neighborly simplicial spheres exist. (The only cs-$([d/2]+1)$-neighborly spheres is the boundary complex of the cross polytope.)  The first example (which is not a cross polytope) was given by Grünbaum in 1969 in his paper “The importance of being straight(?).” In 1995  Jockusch constructed an infinite family cs-2-neighborly centrally symmetric 3-dimensional simplicial spheres. This problem has now been solved by Novik and Zheng.

Neighborly centrally symmetric polytopes.  In the 1960s Grünbaum noted the big difference between neighborly centrally symmetric spheres and centrally symmetric polytopes. He proved (This is Theorem 4.1 in his book “Convex polytopes”) that no cs-2-neighborly 4 polytope with 12 vertices exists.  This is an example of the important themes of “straightening” or “linearizing” combimatorial objects and  of extending theorems from the “straight” or “linear” case to more general combinatorial settings.)

This result by Grünbaum was extended in various directions. Let me mention two major results in the field:

Theorem McMullen and Shephard (1968): A cs d-dimensional polytope with 2(d + 2) vertices cannot be more than cs-⌊(d + 1)/3⌋-neighborly.

Theorem Linial and Novik (2006): A cs-2-neighborly d-dimensional polytope has at most  $2^d$;

Novik (2017) constructed  cs-2-neighborly d polytopes with $2^{d-1}+1$ vertices. She used a 2017 breakthrough construction by Gerencsér–Harang of an acute set of size $2^{d-1}+1$ in $\mathbb R^d$. (A set S is acute if every three points from S determine an acute triangle.)

Face numbers of centrally-symmetric polytopes and spheres. As the abstract asserts the new construction is related to questions about face numbers of centrally symmetric polytopes, spheres and other cellular objects. In fact, this was the next item in our planned posts on algebraic combinatorics of cellular objects. (The first and only post so far is here.) Here is a recent survey by Isabella Novik  A tale on centrally symmetric  polytopes and spheres.

Upper bound theorems. Neighborly polytopes and spheres are the equality cases of the upper bound theorem (proved by McMullen for polytopes and by Stanley for spheres). A version of the upper bound inequality for centrally symmetric spheres was proved by Adin and Stanley and the new construction shows that the Adin-Stanley inequality is tight. For more on the upper bound theorem and neighborliness see Section 2 of my 2000 survey  Combinatorics with geometric flavor.  See also the post How the g-conjecture came about and  the post Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found.

Posted in Combinatorics, Convexity | Tagged , | Leave a comment